Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи icon

Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи




Скачати 304.04 Kb.
НазваЛабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи
Сторінка1/3
Дата конвертації22.05.2013
Розмір304.04 Kb.
ТипЛабораторна робота
  1   2   3

Лабораторна робота №1

Постановка задачі лінійного програмування та її розв’язання

графічним методом


Мета роботи: Набуття навиків побудови математичної моделі задачі лінійного програмування, вивчення графічного методу для знаходження розв’язку можливостей та оволодіння навичками побудови таблиць і діаграм в Еxcel

Порядок роботи:

Записати математичну модель задачі оптимального планування виробництва згідно заданого варіанта.

Використовуючи засоби роботи із прогресією Еxcel (AutoFill), заповнити таблицю, що відповідає обмеженням задачі лінійного програмування.

Використовуючи засоби створення діаграм Еxcel, намалювати відповідну таблиці діаграму.

Знайти максимальне та мінімальне значення цільової функції на побудованій діаграмі.

Проінтерпретувати отримані результати для вихідної задачі.

Оформити звіт для захисту лабораторної роботи за зразком:

назва роботи;

мета роботи;

порядок роботи;

короткі теоретичні відомості;

алгоритм розв’язку задачі;

малюнки відповідних таблиць та діаграм;

аналіз отриманих результатів та висновки.


Задача знаходження розв'язку системи лінійних нерівностей відіграє важливу роль у розв'язуванні багатьох задач математичного програмування, а не лише лінійного. Ця задача має і самостійний інтерес.

Розглянемо спочатку такий приклад. Нехай дано систему нерівностей:

(2)


Геометрично кожну нерівність системи (2) можна тлумачити як деяку півплощину, обмежену прямою, рівняння якої можна дістати з відповідної нерівності, змінивши знак нерівності знаком рівності. Через di(x1, x2) (і =1, 2, ..., 6) позначено відхилення довільної точки з координатами x1, x2 від відповідної прямої. Так, відхилення точки з координатами х1=3, х2 = 8 від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 становить d1(3, 8) = -1*3 - 1*8 + 11 = 0, тобто точка (3; 8) лежить на цій прямій; аналогічно знаходимо відхилення точки (3; 8) від прямої d2(x1, x2), яке становить -3; від прямої d3(x1, x2) становить 15 і т.д.

У точці з координатами (x1; x2) нерівність, наприклад, d1(x1, x2) = -1х1 - 1х2 + 11 = 0, виконується, якщо відхилення такої точки від прямої d1(x1, x2) = -1х1 - 1х2 + 11 = 0 невід'ємне.

Рис.1.

На Рис. 1 зображено множину точок W (її заштриховано), у кожній точці якої винонуються всі нерівності системи (2). Отже, множина W є множиною розв'язків системи нерівностей (2). Якщо точка х належить множині W розв'язків системи нерівностей (2), то відхилення цієї точки від усіх прямих, які обмежують множину W, будуть невід'ємними. А якщо точка не належить W, то принаймі одна з нерівностей не справджуватиметься і координати цієї точки не задовольнятимуть систему нерівностей, які визначають множину W. Очевидно, W є опуклим многокутником.

Отже, якщо всі відхилення деякої точки від прямих, що обмежують множину W, невід'ємні, то набір координат такої точки є одним із розв'язків даної системи нерівностей. Такий розв'язок називатимемо допустимим. Точку, що відповідає допустимому розв'язку, називатимемо допустимою.

Як бачимо, у двовимірному просторі задачу можна розв'язати графічним способом, побудувавши множину розв'язків для кожної нерівності і взявши переріз таких множин. Якщо цим перерізом є порожня множина, то система нерівностей несумісна.

Зауважимо, що в n-вимірному (навіть в тривимірному) просторі графічно розв'язати довільну систему нерівностей вже неможливо. Проте за допомогою жорданових виключень досить легко розв'язати таку задачу.

Нехай задано систему лінійних нерівностей


di(x) * (ai, x) + bi = 0 (i =1, 2, ..., m), (3)


де x = (x1; x2; ...; xn)  Rn, ai = (ai1; ai2; ...; ain)  Rn, bi - дійсні числа.

Розв'язком системи неріностей (3) називається будь-яка точка xRn, яка задовольняє всі нерівності (3). У геометричному тлумаченні розв'язком системи (3) є будь-яка точка xRn , що має невід'ємні відхилення від усіх m площин di(x) = 0.

Припустимо спочатку, що ранг матриці кеофіцієнтів системи (3) дорівнює n.

Запишемо систему (3) у вигляді таблиці.


Таблиця 1



x1

x2

...

xn

1

d1

a11

a12

...

a1n

b1

d2

a21

a22

...

a2n

b2

...

...

...

...

...

...

dm

am1

am2

...

amn

bm


Очевидно, що коли всі bi = 0, то x=(0; 0; ...; 0) є розв'язком системи нерівностей. Припустимо, що серед чисел bi є від'ємні. Нехай, наприклад, b1 < 0. За допомогою кроку жорданового виключення замість якоїсь із змінних xj введемо до числа незалажних змінну d1. Нехай після кроку жорданового виключення дістанемо таблицю


Таблиця 2




d1

x2

...

xn

1

x1





...





d2





...





...

...

...

...

...

...

dm





...






Якщо серед чисел b(1)i немає від'ємних, то, поклавши d1 = 0, x2 = 0, ..., xn = 0, дістанемо: x1 = b(1)1, d2 = b(1)2, ..., dm = b(1)m. Точка x = (b(1)1; 0; ...; 0), очевидно, буде розв'язком системи (3), бо в цій точці d1 = 0, d2 = 0, ..., dm = 0. Нехай серед чисел b(1)i є від'ємні, наприклад, b(1)2 < 0. Тоді замість якоїсь з решти зміних xj вводимо змінну d2. Якщо таким чином вдається виключити всі змінні xj, то через n кроків жорданових виключень дістанемо таблицю.

Таблиця 3




d1

d2

...

dn

1

x1





...





...

...

...

...

...

...

xn





...





dn+1





...





...

...

...

...

...

...

dm





...






Поклавши d1 = 0, d2 = 0, ..., dn = 0, дістанемо: x1= b(n)1; x2 = b(n)2; ...; xn = b(n)n; xn+1 = b(n)n+1 ; ...; xm = b(n)m.

Вирази для змінниx xi надалі з розрахункових таблиць можна вилучити. Визначивши потрібні значення змінних d1, d2, ..., dn, можна легко знайти відповідні значення змінних x1, x2, ..., хn за таблицею 3.

Якщо серед чисел b(n)n+1, ..., b(n)m немає від'ємних, то точка x = (b(n)1; b(n)2; ...; b(n)n) є розв'язком системи нерівностей (3). Ця точка належить до площин d1(х) = 0, d2(х)= 0 ,..., dn(х) = 0, оскільки має нульові відхилення від цих площин. Від площин dn+1(х) = 0, ..., dm(х) = 0 точка x = (b(n)1; b(n)2; ...; b(n)n) має відповідно невід'ємні відхилення b(n)n+1 = 0, ..., b(n)m = 0. Нехай серед вільних членів b(n)n+1, ..., b(n)m є від'ємні, наприклад, b(n)n+1 < 0. Серед коефіцієнтів d-рядка з від'ємним вільним членом знайдемо додатній. Якщо додатніх коефіцієнтів в d-рядку з від'ємним вільним членом немає, то система нерівності (3) несумісна, а тому і вся система (3) не має розв'язку.

На Рис. 2 показано сумісні системи нерівностей для двовимірного (Рис. 2, в) та тривимірного (Рис. 2, г) випадків і несумісні системи для двовимірного (Рис. 2, а) та тривимірного (Рис. 2, б) випадку.




Рис. 2.


Нехай серед коефіцієнтів d-рядка з від'ємним вільним членом є додатні, наприклад b(n)n+1 < 0, a(n)n+1,1 > 0. Тоді, збільшуючи відхилення d1(x), тобто віддаляючись від площини d1(x) = 0 в напрямі збільшення d1(x), збільшуватимемо і від'ємне відхилення dn+1(x) за умови, що при цьому відбуватиметься рух по ребру d2(x) = 0, ..., dn(x) = 0 у напрямі збільшення d1(x) i dn+1(x). По ребру d2(x) = 0, ..., dn(x) = 0 рухатимeмось у вказаному напрямі до найпершої із площин dn+1(x) = 0, dn+2(x) = 0, ..., dm(x) = 0. Якщо d2(x) = 0, ..., dn(x) = 0, точка х досягне площини dn+1(x) = 0 за умови, що dn+1(x) = a(n)n+1,1 * d1(x) + b(n)n+1 = 0, тобто коли d1(x) набуде значення - b(n)n+1 / a(n)n+1,1 , очевидно, додатнього.

Площини dm(x) = 0 точка x, рухаючись по ребру d2(x) = 0, ..., dm(x) = 0, досягне при умові dm(x) = a(n)m1 * d1(x) + b(n)m = 0, тобто при d1(x) = - b(n)m / a(n)m1. Зауважимо, що коли відношення b(n)i / a(n)i1 > 0 для деякого i  {n+1, ..., m}, то площини di(x) = 0 із збільшенням d1(x) досягти неможливо. Справді, якщо b(n)i > 0 і a(n)i1 > 0, то із збільшенням d1(x) значення di(x) = a(n)i1 d1(x) + b(n)i збільшується, тобто із збільшенням d1(x) відповідна точка х не наближатиметься до площини di(x) = 0, а, навпаки, віддалятиметься. А коли b(n)i < 0 і a(n)i1 < 0, то із збільшенням d1(x) значення di(x) = a(n)i1 d1(x) + b(n)i лише зменшується (від'ємне й збільшується за модулем), відповідна точка x знову віддалятиметься від площини d1(x) = 0.

Отже, рухаючись по ребру d2(x) = 0, ..., dn(x) = 0 в напрямі збільшення d1(x), точка x може досягти лише тих площин dі(x) = 0 (і=n+1, ..., m), для яких b(n)i / a(n)i1 < 0. При цьому d1(x) набуватиме значень відповідно d1(x) = - b(n)i / a(n)i1 > 0. Першрю серед площин dn+1(x) = 0, ..., dm(x) = 0, очевидно, буде досягнуто ту площину, для якої відношення b(n)i / a(n)i1 за модулем буде найменше. Нехай таке найменше відношення досягнеться при i = n+1. Тоді дістанемо dn+1(x) = 0, d1(x) = - b(n)n+1 / a(n)n+1,1. Виключемо змінну d1 із незалежних, ввівши замість неї змінну dn+1. Після кроку жорданового виключення матимемо таблицю:


Таблиця 4




d1

d2

...

dn

1

x1





...





...

...

...

...

...

...

xn





...





d1





...





dn+1





...





...

...

...

...

...

...

dm





...






Точка x = (b(n+1)1; b(n+1)2; ...; b(n+1)n) тепер уже належить площинам dn+1(x) = 0, d2(x) = 0, d3(x) = 0, ..., dn(x) = 0. Точку x  Rn, яка належить деяким n площинам di1(x) = 0, ..., din(x) = 0, i,j  {1, 2, ..., m}, називатимемо вершиною. Площини di(x) = 0, яким належить вершина, називатимемо базовими. Вершину, яка є розв'язком системи (3), називатимемо допустимою.

Переходячи за допомогою жорданових виключень від однієї вершини до іншої, за скінченну кількість кроків знайдемо допустиму вершину або з'ясуємо, що система (3) несумісна.

Отже, можна сформулювати правила знаходження допустимої вершини системи нерівностей (3):

1. Виключаємо всі змінні xj (j = 1, 2, ..., n) з незалежних.

2. Якщо всі вільні члени d-рядків невід'ємні, то точка х, що належить базовим площинам di(x) = 0, допустима.

3. Якщо серед вільних членів d-рядків є від'ємні і є d-рядок з від'ємним вільним членом, де всі коефіцієнти недодатні, то система нерівностей (3) несумісна.

4. Якщо в кожному d-рядку з від'ємним вільним членом є принаймні один додатний коефіцієнт, то, вибравши будь-який з таких коефіцієнтів, візьмемо стовпчик, в якому міститься цей коефіцієнт, за основний.

5. Знайдемо від'ємні відношення вільних членів, d-рядків до відповідних коефіцієнтів основного стовпчика. Рядок, на який припадає найменше за модулем відношення, візьмемо за основний.

6. З визначеним таким чином основним елементом виконаємо крок жорданового виключення. Діставши нову таблицю, знову повернемось до правила 2.

Слід зазначити, що коли є стовпчик, всі елементи d-рядків у якому додатні, відповідну незалежну змінну d можна необмежено збільшувати, в результаті чого зрештою всі залежні змінні d стануть додатними. Множина розв'язків у цьому випадку виявляється необмеженою.

Зауваження. Коли найменше відношення, визначене в п. 5, дорівнює нулю, то ми не виходимо з попередньої точки х, оскільки крок вздовж відповідного ребра буде нульовим. При цьому змінюється лише набір базових площин. У такому разі можливе так зване зациклювання, коли через певну кількість кроків повторюватимуться ті самі таблиці. Є спеціальні засоби, щоб подолати зациклювання, на яких ми тут не зупиняємося.

У наведених щойно міркуваннях ми припускали, що ранг матриці (aij) {і = 1, 2, ..., n; j = 1, 2, ..., m) дорівнює n. Якщо ранг цієї матриці менший за n, то виключити всі xj (j = 1, 2, ..., n) з незалежних не вдається.


Нехай ранг матриці (aij) (і = 1, … ,m; j = 1, …, n) дорівнює s (s < n), тоді через s кроків жорданових виключень дістанемо таблицю 5.


Таблиця 5.




d1

...

ds

xs+1

...

xn

1

x1



...





...





...

...

...

...

...

...

...

...

xs



...





...





ds+1



...



0

...

0



...

...

...

...

...

...

...

...

dm



...



0

...

0




Змінним xj (j = s+1, ..., n), що залишається серед незалежних, можна надавати довільних значень. Якщо при цьому незалежні змінні di (i = 1, … , s) покласти рівними нулю, то всі залежні змінні di (i = s+1, ..., m) не змінюватимуться при зміні незалежних змінних xj (j = s+1, ..., n). Змінюватимуться лише залежні змінні x1, ..., xs. При цьому відбуватиметься рух по (n-s)-вимірному "ребру", тобто по множині точок, що належать одночасно площинам d1(х) = 0, ..., ds(x) = 0. Площини ds+1(x) = 0, ..., dm(x) = 0 виявляються паралельними такому "ребру".

Правила розв'язування системи (3) при цьому залишаться назмінними. Геометричне тлумачення таке саме з тією лише відмінністю, що тепер зручно перейти до s-вимірного підпростору Rn, оскільки в усіх перерізах, ортогональних до згаданого s-вимірного підпростору, картина залишається однаковою. Отже, фактично задача лише спрощується.


Перший крок при використанні графічного методу полягає в поданні області допустимих розв’язків, у якій водночас задовольняються всі обмеження моделі. Шукана область (простір) розв’язків задачі показана на Рис. 3. Умови невід’ємності змінних обмежують область їх допустимих значень першим квадрантом координатної площини (частина площини над віссю x1 і справа від осі x2). Інші межі простору розв’язків зображені прямими лініями, побудованими по рівняннях, що отримані заміною знака “≤” знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності ( в нашому випадку - нерівності із знаком “≤”), указуються стрілками, спрямованими вбік допустимих значень змінних. Отриманий простір розв’язків задачі - багатокутник АВСDЕF (рис. 2.1). У кожній точці, що належить внутрішній області або межам багатокутника розв’язків АВСDЕF, всі обмеження виконуються, тому розв’язки, що відповідають цим точкам, є допустимими. Серед нескінечного числа таких точок можна знайти точку оптимальнного розв’язку, якщо з'ясувати, в якому напрямку зростає цільова функція.  



Рис. 3. Простір допустимих розв’язків ЗЛП .

Рис. 4. Знаходження оптимального розв’язку ЗЛП графічним методом.


На рис. 4   показано, як здійснюється така операція. 

На графік наносять лінію рівня цільової функції c1x1+c2x2=z0, де z0 - довільне значення z. Будують вектор N(c1,c2), що є нормальним до ліній рівня цільової функції й визначає напрямок оптимізації z. Лінію рівня зрушують паралельно самій собі вздовж вектора N доти, поки вона не вийде за межі області допустимих розв’язків. Остання точка цієї області й буде точкою оптимуму. 


Індивідуальне завдання


(для визначення числових значень коефіцієнтів використовується N – порядковий номер студента в групі)


Розглянемо діяльність деякого виробничого об’єкта. Нехай у його розпорядженні є 5 типів сировинних ресурсів у розмірі bj =N+j*5 (bj число одиниць ресурсу j = 1, …, 5). З цих ресурсів виробничий об’єкт виготовляє k видів продукції у ціні ci=(-1)N*(N+i) за одиницю, і = 1, …, k. Задано матрицю A з елементами aij - число одиниць ресурсу j необхідних для виготовлення однієї одиниці продукції і, причому, aij = N*2+(-1)i(i*j + N), якщо N  15; aij = N+(-1)i(i*j + N), якщо N > 15. . Визначити оптимальний план виробництва. Число k будується з номера групи так: якщо номер групи n = 10l + m , то k =l - m.


  1   2   3



Схожі:

Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconЛабораторна робота. Робота в інтегрованому середовищі turbo сі. Базові конструкції, програмування з використанням умовного оператора. Мета роботи
Мета роботи: навчитися складати алгоритми розв’язку задач у вигляді блок-схем,ознайомитися з простими типами даних та базовими конструкціями...
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconУрок 18/31 Лабораторна робота №9 «Визначення густини тіла гідростатичним методом» Мета уроку : виміряти густину речовини, з якого складається тверде тіло, методом гідростатичного зважування
Урок 18/31 Лабораторна робота №9 «Визначення густини тіла гідростатичним методом»
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconУрок 6/40. Розв’язання задач Мета уроку: з’ясувати рівень засвоєння учнями вивченого матеріалу; перевірити їхнє вміння застосовувати отримані знання до розв’язання конкретних задач
Самостійна робота №18 «Коефіцієнт корисної дії» (робота дається наприкінці уроку)
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconЗадача механіки та способи її розв’язання в кінематиці
Мета уроку: дати визначення механічного руху, познайомити з двома найпростішими видами механічного руху, основною задачею механіки...
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconЛабораторна робота №1
Мета роботи: Вивчення основних опцій та можливостей меню для створення проектів у середовищі програмування Delphi
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconУрок алгебри для 9 класу Шпакова Тетяна Леонідівна вчитель математики Миколаївської гімназії №4
Тема: Розв'язування квадратичних нерівностей методом інтервалів. Мета: ознайомити учнів з розв'язанням квадратичних нерівностей методом...
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconУрок 6/19. Лабораторна робота №6 «Вимірювання ваги динамометром» Мета уроку: навчитися за допомогою динамометра вимірювати вагу тіла. Тип уроку: урок контролю й оцінювання знань
На виконання цієї роботи бажано затратити 15 хвилин. Решту часу на уроці можна використати для розв’язання якісних і розрахункових...
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconОсновні задачі і поняття лінійного програмування
Необхідно із усіх можливих варіантів вибрати найкращий. З цією метою використовуються математичні методи
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconПрактичне заняття 1
Мета: Розглянути методи розв‘язання транспортної задачі із використанням Mathcad і Excel
Лабораторна робота №1 Постановка задачі лінійного програмування та її розв’язання графічним методом Мета роботи iconЛабораторна робота № І мета роботи : Ознайомлення з програмним забезпеченням для програмування мікропроцесорних контролерів Mitsubishi а-серії Завдання Завантажити програму c :\
Мета роботи: Ознайомлення з програмним забезпеченням для програмування мікропроцесорних контролерів Mitsubishi а-серії
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©te.zavantag.com 2000-2017
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи