85767 (597827), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Базисне припустиме рішення задачі лінійного програмування відповідає одній з вершин або граней множини розв’язків.

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

Геометрична інтерпретація множини допустимих розв’язків задачі лінійного програмування та графічний метод її розв’язування. /2/ стор. 165.

Розглянемо задачу лінійного програмування у формі стандартної задачі – з обмеженнями у вигляді нерівностей. З метою наочності розглянемо простіший випадок з двома невідомими змінними. Пригадаємо задачу про планування випуску продукції малим підприємством.

Z = 10 x₁ + 20 x₂ ; Z max;

х₁ + 3,5 х₂ 350;

2 х₁ + 0,5 х₂ 240;

х₁ + х₂ 150;

х₁ + х₂ 110;

10 х₁ + 20 х₂ 1400;

х₁ 0;

х₂ 0.

Нерівність – обмеження графічно відображається півплощіною, а границя – граничною прямою, рівняння якої утворюється перетворенням нерівності на рівняння.

l₁ x₁ + 3,5x₂ = 350 ;

x₁ = 0, x₂ = 350 / 3,5 = 100 ; x₂ = 0, x₁ = 350.

Щоб з’ясувати, яка напівплощіна задовольняє нерівності, перевіримо, наприклад, чи включає точку (0,0) 0 + 3,5 0 350 напівплощіна нижче граничної прямої – нерівність виконується – напівплощіна нижче границі.

Таким же чином перевіримо та побудуємо інші нерівності:

l₂ 2x₁ + 0,5x₂ = 240 ;

x₁ = 0, x₂ = 240 / 0,5 = 480 ; x₂ = 0, x₁ = 240 / 2 = 120 ;

l₃ x₁ + x₂ = 150; x₁ = 0; x₂ = 150; x₂ = 0, x₁ = 150;

l₄ x₁ + x₂ = 110; x₁ = 0; x₂ = 110; x₂ = 0, x₁ = 110;

l₅ 10x₁ + 20x₂ = 1400;

x₁ = 0, x₂ = 1400 / 20 = 70; x₂ = 0, x₁ = 1400 / 10 = 140;

але точка (0,0) 10 0 + 20 0 = 0 1400 не відповідає нерівності, тому нам потрібна півплощіна вище граничної прямої.

Таким чином отриманий многокутник розв’язків, до речі – опуклий, як завжди.

З метою знаходження максимуму цільової функції

Z = 10 x₁ + 20 x₂ побудуємо лінію рівня цільової функції, поклавши Z = 0 ,

10 x₁ + 20 x₂ = 10; x₁ = 0, x₂ = 40; x₂ = 0; x₁ = 80;

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

Ця точка відповідає перетину прямих

х₁ + 3,5 х₂ = 350; - l₁ ( ) C (70; 80)

х₁ + х₂ = 250; - l₃

х₁ = 70, х₂ = 80,

Z_max (x) = 10 x₁ + 20 x₂ = 10 70 + 20 80 = 23000 грн.

Слушне зауваження у підручнику – якщо було б потрібно знайти мінімальне значення цільової функції, так лінію рівня потрібно зміщувати униз, доки остання крапка вийде на границю многокутника розв’язків – це l₅ , усі крапки якої є розв’язком задачі – нескінченна множина рішень.

У розглянутому випадку многокутник розв’язків не тільки опуклий, а ще і є замкненим. Можливі варіанти опуклого многокутника розв’язків, який є необмеженим.

У першому випадку можливо знайти максимальне значення цільової функції, а у другому випадку – мінімальне значення. На наступному малюнку наведений приклад многокутника розв’язків несумісної системи обмежень – розв’язок задачі математичного програмування відсутній.

Малюнок. Многокутник розв’язків несумісної системи обмежень

задачі лінійного програмування

Тема 3. Симплексний метод розв’язання задач лінійного програмування

Перша праця по лінійному програмуванню була надрукована Канторовичем у 1939 році, але лише після відкриття Данцігом у 1949 році симплекс-метода розв'язання задачі лінійного програмування до цього класу задач виникла зацікавленість. Симплекс-метод дає аналітичний розв’язок лінійної задачі математичного програмування.

Симплексний метод розв’язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином, що кожного разу значення цільової функції зростає (за умов, що задача має оптимальний план, та кожний з опорних планів не є надмірним). Під опорним планом мають на увазі невід’ємний базисний розв’язок задачі лінійного програмування. Нагадаємо – базисний план (розв’язок) – рішення системи обмежень. у якому усі вільні змінні дорівнюють нулеві, тобто геометрично базисний план відповідає одній з вершин або граней многокутника розв’язків.

Розглянемо використання симплекс-методу для вирішення задачі лінійного програмування на прикладі задачі про планування випуску продукції малим підприємством. У зв’язку з тим, що ця задача була розв’язана раніше, і ми з’ясували, що функціональні планові обмеження виконуються автоматично, а також з метою спрощення пошуку, розглянемо тільки функціональні обмеження ресурсів.

х₁ + 3,5 х₂ 350;

2 х₁ + 0,5 х₂ 240;

х₁ + х₂ 150;

х₁ 0;

х₂ 0.

Z = f (x) = 10 x₁ + 20 x₂ ; Z max;

( -Z = - f (x) = - 10 x₁ - 20 x₂ - 0 x₄ - 0 x₅; min ).

Розв’язок задачі. Перетворимо функціональні обмеження-нерівності на обмеження-рівності шляхом введення у обмеження-нерівності невід’ємних вільних невідомих y₁, y₂, y₃ (хоча можливо було б і х₃, х₄, х₅ ).

х ₁ + 3,5 х₂ + у₁ = 350; (1)

2 х₁ + 0,5 х₂ + у₂ = 240; (2)

х₁ + х₂ + у₃ = 150; (3)

х₁ 0; х₂ 0; у₁ 0; у₂ 0; у₃ 0.

Перед початком виробництва х₁ = х₂ = 0 , тоді

у ₁ = 350; наявність ресурсу – шерсть;

у₂ = 240; наявність ресурсу – шовк;

у₃ = 150; наявність ресурсу – трудомісткість.

Прибуток на початок справи Z = 10 0 + 20 0 = 0;

Кількість рівнянь-обмежень m = 3; кількість невідомих – х₁, х₂, у₁, у₂, у₃ n = 5; кількість вільних змінних – (n – m) = 5 – 3 = 2;

базисне припустиме рішення задачі – це таке, у якому усі вільні змінні дорівнюють нулеві (вершина або грань многокутника розв’язків). Тому початковий опорний план складає

х (1) = (0; 0; 350; 240; 150) ; Z ( х(1) ) = 0;

де : х₁ = 0; х₂ = 0 – вільні змінні, відповідає рішенню задачі, коли продукція не виробляється. Надамо цю інформацію у вигляді симплекс-таблиці

Таблиця

Z = 10х₁ + 20х₂ = 10 0 + 20 0 = 0; - Z = 0;

Виробництво чоловічих костюмів х₂ дає більший дохід, так почнемо його збільшувати, залишаючи х₁ = 0, але існують обмеження. З першої строки симплекс-таблиці (першого рівняння-обмеження на наявність шерстяної тканини) чоловічих костюмів можливо виготовити 350 / 3,5 = 100; з другої строки симплекс-таблиці (другого рівняння-обмеження на наявність шовкової тканини) чоловічих костюмів можливо виготовити 240 / 0,5 = 480 штук; з третьої строки симплекс-таблиці (третього рівняння-обмеження на наявність ресурсів праці) чоловічих костюмів можливо виготовити 150 / 1 = 150 одиниць. Визначальним є обмеження на шерстяну тканину, тобто найбільша кількість чоловічих костюмів (за умов відсутності жіночих – х₁ = 0) дорівнює найменшому з трьох значень 100; 480; 150; х₂ = 110. Визначальний елемент симплекс-таблиці – коефіцієнт у першому рівнянні при другій вільній змінній (х₂), який дорівнює3,5; та має назву центру (ключового елемента).

Як буде виготовлено 100 чоловічих костюмів, так х₂ = 100 і з першого рівняння-обмеження отримаємо (х₁ = 0)

у ₁ = 350 – 3,5х₂ – х₁; (1)

у₂ = 240 – 0,5х₂ – 2х₁; (2)

у₃ = 150 – х₂ – х₁; (3)

що у₁ = 0, тобто ресурсів шерстяної тканини не буде; з другого рівняння-обмеження отримаємо у₂ = 240 – 0,5 100 – 2 0 = = 190 м шовкової тканини у запасах; з третього рівняння-обмеження отримаємо у₃ = 150 – 100 – 0 = 50 людино - тижнів трудомісткості у запасах.

Прибуток складає Z = 10 0 + 20 100 = 2000 грн.; - Z = - 2000.

Цільова функція Z = 10 х₁ + 20 х₂ через нові вільні змінні (х₁ = 0; у₂ = 0) має вираз

40 40 40 30

Z = 10 х₁ + 20 х₂ = 10 х₁ + 2000 - у₁ - х₁ = 2000 - у₁ + х₁,

7 7 7 7

бо (з першого рівняння-обмеження) маємо:

х₂ = 100 – у₁ / 3,5 – х₁ / 3,5.

Перетворимо систему рівнянь-обмежень, замінюючи х₂ на його вираз:

х ₁ + 3,5 (100 – у₁ / 3,5 – х₁ / 3,5) + у₁ = 350; (1)

2 х₁ + 0,5 (100 – у₁ / 3,5 – х₁ / 3,50) + у₂ = 240; (2)

х₁ + (100 – у₁ / 3,5 – х₁ / 3,50) + у₃ = 150; (3)

х₂ + у₁ / 3,5 + х₁ / 3,5 = 100 (4)

Другий опорний план задачи таким чином складає

х(2) = (0; 100; 0; 190; 50; 100); Z (х(2) ) = 2000;

де: х₁ = 0; у₁= 0 – вільні змінні, відповідає розв’язку задачі, якщо виробляються виключно чоловічі костюми (х₂ = 100). Знов надамо цю інформацію у вигляді симплекс-таблиці.

Таблиця

Кожен з елементів симплекс-таблиці має своє значення:

• у першому стовпці (х₁) 13 / 7 – потрібна кількість шовкової тканини, потрібної на один жіночий костюм; 5 / 7 – потрібна кількість праці на один жіночий костюм; 30 / 7 – прибуток від одного жіночого костюма;

Дивлячись на цільову функцію

30 40

Z = 2000 + х₁ - у₁ ,

1. 7

бачимо, що збільшення виготовлення жіночих костюмів може збільшити прибуток, бо х₁ 0 , а також 30 / 7 0.

Пригадуючи, що у₁ = 0, знайдемо значення нової вільної змінної, яка задовольняє систему рівнянь-обмежень (2), (3), (1), а також у₂ 0 , у₃ 0 , х₂ 0 .

(2) дає, якщо у₂ = 0, х₁ 102;

(3) дає, якщо у₃ = 0, х₁ = 70;

(1) дає, якщо х₂ = 0, х₁ =350;

Визначальними є обмеження на ресурси праці: , х₁ = 70, у₃ = 0 з рівняння (3).

Характеристики

Список файлов книги