2 x3 ; В
а) Х = (8/7; 3/7, 0), б) Х = (0; 1/5; 8/5), в) Х = (1/3, 0, 1/ 3).
Розв'язання . Принцип розв'язування задач такого типу грунтується на вікорістанні Другої теореми двоїстості. Звітність, побудуваті двоїсту задачу та, допускаючи, что відповідній план Х є оптимальним, візначіті оптимальний розв'язок двоїстої задачі. Если при цьом Екстремальні Значення цільовіх функцій будут однаково за величиною, то припущені правильне. Протилежних можна вісновуваті в таких випадка:
1. Если запропонованій план Х неприпустимо, тоб НЕ задовольняє систему обмежень прямої задачі.
2. Если визначеня план двоїстої задачі неприпустимо, тоб НЕ задовольняє ВСІ обмеження двоїстої задачі.
3. Если визначеня план двоїстої задачі допустимого, альо для нього Єкстремальний Значення цільової Функції F НЕ дорівнює значень Функції Z , тоб НЕ віконується Умова Першої теореми двоїстості.
Запішемо двоїсту задачу до прямої задачі лінійного програмування:
max F = y1 + 2 y2 ;
В В
Перевірімо запропоновані плани на оптімальність.
1. Х = (8/7; 3/7, 0). Підставімо его в систему обмежень прямої задачі:
В
Обидва обмеження віконуються, и того Х = (8/7; 3/7, 0) є допустимим планом прямої задачі. Припустиме тепер, что зазначеній план є оптимальним планом прямої задачі. Тоді розрахуємо для нього величину цільової Функції: Z = 12 х 8/7 - 4 х 3/7 + 2 х 0 = 12. p> Скорістаємося другою теореми двоїстості та візначімо відповідній план двоїстої задачі. Оскількі x1 = 8/7> 0; x2 = 3/7> 0, те згідно з другою Частинами Другої теореми двоїстості можна записатися перше та друге обмеження як рівняння и візначіті у1 та у2 :
В
Підставімо ці Значення в Третє обмеження системи двоїстої задачі:
;
.
Для визначених значень у1 = 4; у2 = 4 це обмеження НЕ віконується, и того відповідній план у = (4, 4) є неприпустимим планом двоїстої задачі. Внаслідок цього наше припущення, что Х = (8/7; 3/7, 0) є оптимальним планом прямої задачі, виявило помилковості.
2. Х = (0; 1/5; 8/5). Підставімо цею план у систему обмежень прямої задачі:
В
План допустимих, и для нього Z = 12 х 0 - 4 х 1/5 + 2 х 8/5 = 12/5.
Візначімо відповідній план двоїстої задачі. Оскількі компоненти x 2 та x 3 додатні, то друга и Третє обмеження двоїстої задачі можна записатися як рівняння:
В
Перевірімо, чі віконується перше обмеження двоїстої задачі для визначених значень у1 та у2 : 2 х 8/5 + 2/5 = 18/5 <12. Отже, перше обмеження віконується, и того у = (8/5; 2/5) є допустимим планом двоїстої задачі. Для нього
F = 8/5 + 2 х 2/5 = 12/5 = Z .
З Огляду на викладеня можна вісновуваті, что Y * = (8/5, 2/5) є оптимальним планом двоїстої задачі, а X * = (0; 1/5; 8/5) - оптимальний планом прямої задачі.
Наше припущені відносно запропонованого планом виявило правильним.
3. Х = (1/3, 0, 1/3). Для цього плану обмеження прямої задачі віконуються так:
В
Оскількі Х = (1/3, 0, 1/3) є неприпустимим планом, то ВІН НЕ может буті такоже оптимальним планом прямої задачі.
Отже, перевірка запропонованіх планів на оптімальність дала Такі результати: а) ні; б) так, Х * = (0; 1/5; 8/5), min Z = 12/5; в) ні.
Список використаних джерел
В
1. Абрамов Л.М., Капустін В.Ф. Математичне програмування. Л., Вид-во Ленінград. ун-ту, 1976. - 184 с. p> 2. Акуліч І.Л. Математичне програмування у прикладах і задачах. - М.: Вища. шк., 1985.
3. Ашманов С.А. Лінійне програмування. - М.: Наука, 1981. p> 4. Белман Р. Динамічне програмування. - М.: Вид-во іноземної літератури, 1960. p> 5. Белман Р., Дрейфус С. Прикладні задачі динамічного програмування. - М.: Наука, 1965. p> 6. Вагнер Г. Основи дослідження операцій. - Т. 1-3. - М.: Мир, 1972. p> 7. Вентцель Є.С. Дослідження операцій. М.: В«Рад. радіо В», 1972. - 552 с. p> 8. Вентцель Є.С. Елементи динамічного програмування. - М.: Наука, 1964. p> 9. Гольштейн Є.Г., Юдін Д.Б. Нові напрямки в лінійному програмуванні. - М.: Радянське радіо, 1966.
10. Гольштейн Є.Г., Юдін Д.Б. Завдання лінійного програмування транспортної типу. - М.: Наука, 1969. p> 11. Данциг Дж. Лінійне програмування, його узагальнення і додатки. - М.: Прогрес, 1966. p> 12. Зайченко Ю.П. Дослідження операцій: Підручник. - 4-ті вигляд., Перероб. і допов. - К., 2000. - 688 с. p> 13. Зангвілл У. Нелінійне програмування. Єдиний підхід. М.: В«Сов.радіоВ», 1973. - 312 с. p> 14. Єрмольєв Ю.М., Ястремський О.І. Стохастичні моделі і методи в економічному плануванні. М....
