Сформулюйте правила побудови двоїстих задач
Для побудови двоїстої задачі необхідно звести пряму задачу до стандартного виду. Вважають, що задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності її системи обмежень приведені до виду « 
», а для задачі на відшукання мінімального значення — до виду « 
».
Двоїста задача утворюється за такими правилами:
1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.
2. Кожній змінній прямої задачі відповідає обмеження двоїстої задачі, причому кількість обмежень двоїстої задачі дорівнює кількості невідомих прямої задачі.
3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.
4. Коефіцієнтами при змінних у цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.
5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних у цільовій функції прямої задачі.
6. Матриця, що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів у системі обмежень двоїстої задачі утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.
Процес побудови двоїстої задачі зручно зобразити схематично:
|
|
|
Які задачі лінійного програмування можна розв’язати графічним методом
Для розв’язування двовимірних задач лінійного програмування, тобто задач із двома змінними, а також деяких тривимірних задач застосовують графічний метод, що ґрунтується на геометричній інтерпретації та аналітичних властивостях задач лінійного програмування. Обмежене використання графічного методу зумовлене складністю побудови багатогранника розв’язків у тривимірному просторі (для задач з трьома змінними), а графічне зображення задачі з кількістю змінних більше трьох взагалі неможливе.
Алгоритм графічного методу розв’язування задачі лінійного програмування складається з таких кроків:
1. Будуємо прямі, рівняння яких дістаємо заміною в обмеженнях задачі знаків нерівностей на знаки рівностей.
2. Визначаємо півплощини, що відповідають кожному обмеженню задачі.
3. Знаходимо багатокутник розв’язків задачі лінійного програмування.
4. Будуємо вектор , що задає напрям зростання значення цільової функції задачі.
5. Будуємо пряму с1х1 + с2х2 = const, перпендикулярну до вектора .
6. Рухаючи пряму с1х1 + с2х2 = const в напрямку вектора (для задачі максимізації) або в протилежному напрямі (для задачі мінімізації), знаходимо вершину багатокутника розв’язків, де цільова функція набирає екстремального значення.
|
|
|
7. Визначаємо координати точки, в якій цільова функція набирає максимального (мінімального) значення, і обчислюємо екстремальне значення цільової функції в цій точці.
Дата добавления: 2018-02-18; просмотров: 1322; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!