Реферат: Математичне програмування в економіці
У першому випадку можливо знайти максимальне значення цільової функції, а у другому випадку – мінімальне значення. На наступному малюнку наведений приклад многокутника розв’язків несумісної системи обмежень – розв’язок задачі математичного програмування відсутній.
 |
Малюнок. Многокутник розв’язків несумісної системи обмежень
задачі лінійного програмування
Тема 3. Симплексний метод розв’язання задач лінійного програмування
Перша праця по лінійному програмуванню була надрукована Канторовичем у 1939 році, але лише після відкриття Данцігом у 1949 році симплекс-метода розв'язання задачі лінійного програмування до цього класу задач виникла зацікавленість. Симплекс-метод дає аналітичний розв’язок лінійної задачі математичного програмування.
Симплексний метод розв’язання задачі лінійного програмування ґрунтується на переході від одного опорного плану до іншого таким чином, що кожного разу значення цільової функції зростає (за умов, що задача має оптимальний план, та кожний з опорних планів не є надмірним ). Під опорним планом мають на увазі невід’ємний базисний розв’язок задачі лінійного програмування. Нагадаємо – базисний план (розв’язок) – рішення системи обмежень. у якому усі вільні змінні дорівнюють нулеві, тобто геометрично базисний план відповідає одній з вершин або граней многокутника розв’язків.
Розглянемо використання симплекс-методу для вирішення задачі лінійного програмування на прикладі задачі про планування випуску продукції малим підприємством. У зв’язку з тим, що ця задача була розв’язана раніше, і ми з’ясували, що функціональні планові обмеження виконуються автоматично, а також з метою спрощення пошуку, розглянемо тільки функціональні обмеження ресурсів.
х1 + 3,5 х2 £ 350;
2 х1 + 0,5 х2 £ 240;
х1 + х2 £ 150;
х1 ³ 0;
х2 ³ 0.
Z = f (x) = 10 x1 + 20 x2 ; Z ® max;
( -Z = - f (x) = - 10 x1 - 20 x2 - 0 × x4 - 0 × x5 ; ® min ).
Розв’язок задачі. Перетворимо функціональні обмеження-нерівності на обмеження-рівності шляхом введення у обмеження-нерівності невід’ємних вільних невідомих y1 , y2 , y3 (хоча можливо було б і х3 , х4 , х5 ).
х1 + 3,5 х2 + у1 = 350; (1)
2 х1 + 0,5 х2 + у2 = 240; (2)
х1 + х2 + у3 = 150; (3)
х1 ³ 0; х2 ³ 0; у1 ³ 0; у2 ³ 0; у3 ³ 0.
Перед початком виробництва х1 = х2 = 0 , тоді
у1 = 350; наявність ресурсу – шерсть;
у2 = 240; наявність ресурсу – шовк;
у3 = 150; наявність ресурсу – трудомісткість.
Прибуток на початок справи Z = 10 × 0 + 20 × 0 = 0;
Кількість рівнянь-обмежень m = 3; кількість невідомих – х1 , х2 , у1 , у2 , у3 n = 5; кількість вільних змінних – (n – m) = 5 – 3 = 2;
базисне припустиме рішення задачі – це таке, у якому усі вільні змінні дорівнюють нулеві (вершина або грань многокутника розв’язків). Тому початковий опорний план складає
х (1) = (0; 0; 350; 240; 150) ; Z ( х(1) ) = 0;
де : х1 = 0; х2 = 0 – вільні змінні, відповідає рішенню задачі, коли продукція не виробляється. Надамо цю інформацію у вигляді симплекс-таблиці
Таблиця
|
х1 |
х2 |
х3 |
|
К-во Просмотров: 492
Бесплатно скачать Реферат: Математичне програмування в економіці
|