Вказівки до вирішення завдань лінійного програмування - студопедія

Завдання лінійного програмування були першими, детально вивченими завданнями пошуку екстремуму функцій при наявності обмежень типу нерівностей. Присутність в назві терміна «програмування» пояснюється тим, що перші дослідження і перші програми лінійних оптимізаційних задач були в сфері економіки. В англійській мові слово «programming» означає планування, складання планів або програм. Цілком природно, що термінологія відображає тісний зв'язок, який існує між математичною постановкою завдання і її економічної інтерпретацією (вивчення оптимальної економічної програми). Термін «лінійне програмування» був запропонований Дж. Данцигом в 1949 р для вивчення теоретичних та алгоритмічних задач, пов'язаних з оптимізацією лінійних функцій при лінійних обмеженнях.

Загальним завданням лінійного програмування (ЗЛП) називають завдання

і умова невід'ємності компонент

Тут - задані дійсні числа, функція називається цільовою. вектор - план завдання. План, який задовольняє системі обмежень (1.2), називається допустимим. Допустимий план, при якому цільова функція досягає найбільше або найменше значення, називається оптимальним. Можливі такі випадки:

1. Оптимальний план єдиний;

2. Оптимальних планів безліч;

3. Цільова функція необмежена на безлічі допустимих планів;

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

Приклад 1. Розглянемо наступну ЗЛП

Вирішимо цю задачу графічно. Для цього на площині побудуємо декартову систему координат. Кожне з нерівностей системи (1.3) задає на площині деяку полуплоскость. Перетин будь-якого числа напівплощин є опукле безліч.

Нагадаємо, що опуклим називається така безліч, будь-які дві точки якого можна з'єднати відрізком прямої, всі крапки якого належать даній безлічі. Прикладом опуклого безлічі є трикутник.

Побудуємо за двома точками кожну з граничних прямих

Вони зображені на рис. 1.

Тепер в довільній точці (наприклад, в точці O (0,0)) визначаємо, який знак нерівності виконується і вибираємо потрібну напівплощина. Перетином обраних напівплощин буде трикутник, безліч точок цього трикутника є допустима безліч рішень ЗЛП (1.3). На рис.1 трикутник зафарбований темним кольором.

Тепер побудуємо лінію рівня цільової функції

З початку координат побудуємо вектор-градієнт,

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

Будемо рухати лінію рівня в напрямку градієнта до перетину з многогранником допустимих рішень. Перша точка перетину M буде точкою мінімуму. Координати цієї точки M (2,1) визначаємо з системи

Таким чином, оптимальний план ЗЛП (1.3) є. Кінець завдання.

Симетричною формою записи ЗЛП називається задача

В економічній теорії завдання (1.4), (1.5) зустрічаються найбільш часто.

Нарешті, канонічної формойзапісі ЗЛП називають задачу

Система обмежень задачі (1.6) являє собою лінійну алгебраїчну систему. У матричної формі її можна записати так

Для того щоб ЗЛП мала рішення, її система обмежень має бути спільною. Це можливо, якщо ранг матриці збігається з рангом розширеної матриці. позначимо

Змінні ЗЛП, відповідні векторах базису, називаються базисними і позначаються БП. Решта змінних будуть вільними і позначаються СП. Якщо вільні змінні прирівняти нулю, а базисні змінні при цьому візьмуть невід'ємні значення, то отримане приватне рішення системи (1.7) називається опорним рішенням (планом).

Будемо говорити, що система обмежень (1.7) ЗЛП має кращий вигляд. якщо при невід'ємності правій частині ліва частина обмеження містить змінну, що входить з коефіцієнтом, рівним одиниці, а в інші обмеження-рівності - з коефіцієнтом, рівним нулю. Наприклад, в системі обмежень

перше і друге обмеження мають кращий вигляд, а третє - немає.

У 1820 р Ж.Фурье і потім в 1947 р Дж. Данциг запропонували метод спрямованого перебору суміжних вершин в напрямку зростання цільової функції - симплекс-метод. став основним при вирішенні задач лінійного програмування. Радянський академік, лауреат Нобелівської премії (1975 г.) Л.В. Канторович, сформулював ряд завдань лінійного програмування і запропонував (1939 г.) метод їх вирішення (метод дозволяють множників), незначно відрізняється від симплекс-методу.

Метод рішення ЗЛП, який називається симплексним. застосовується лише до канонічної формі записи. Перетворимо симетричну форму записи ЗЛП до канонічної. Нехай вихідна задача має вигляд (1.4). Введемо m додаткових змінних Для того щоб нерівності типу перетворити в рівність, додамо до лівих частинах додаткові змінні. У цільову функцію ці змінні входять з нульовими коефіцієнтами. Система обмежень в задачі (1.4) набуде вигляду

Тут - базисні змінні, - вільні. Отже, початковий опорний план набуде вигляду.

Розглянемо тепер задачу (1.5). Також введемо m додаткових змінних але для того, щоб нерівності типу перетворити в рівності, віднімемо з лівих частин додаткові змінні. (В цільову функцію ці змінні увійдуть з нульовими коефіцієнтами.)

Однак тепер система обмежень не має кращий вигляд, так як додаткові змінні входять в ліву частину (при) з коефіцієнтами, рівними -1. Тому, базисний план

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

Отримана задача називається M-завданням. відповідної вихідної. Вона завжди має кращий вигляд. Її початковий опорний план є

Нехай вихідна ЗЛП має вигляд

Причому жодна з обмежень не має кращою змінної. M-завдання запишеться так

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

Якщо деякі з системи обмежень мають кращий вигляд, то в них не слід вводити штучні змінні.

Приклад 2. Розглянемо наступну ЗЛП

Наведемо завдання до канонічного вигляду, для цього введемо додаткові змінні

Друге рівняння не містить базисної змінної, тому додамо в цьому рівнянні штучний базис. В результаті отримуємо M-завдання

Припустимо тепер, що ЗЛП має кращий вигляд

Завдання (1.9) запишемо в таблицю, яка називається симплексной

Тут в першому рядку стоять коефіцієнти цільової функції при відповідних змінних. У першому стовпці стоять коефіцієнти цільової функції при базисних змінних.

Наведемо тепер основні теореми симплексного методу.

Теорема 1. Нехай вихідна задача вирішується на максимум. Якщо для деякого опорного плану все оцінки невід'ємні, то такий план оптимальний.

Теорема 2. Нехай вихідна задача вирішується на мінімум і для деякого опорного плану все оцінки непозитивні, то такий план оптимальний.

Теорема 3. Якщо в індексному рядку останньої симплексного таблиці, яка містить оптимальний план, є хоча б одна нульова оцінка, відповідна вільної змінної, то ЗЛП має безліч оптимальних планів.

Теорема 4. Якщо в індексному рядку симплексной таблиці ЗЛП на максимум міститься негативна оцінка. а у відповідному стовпці змінної немає жодного позитивного елемента, то цільова функція на множині допустимих планів не обмежена зверху.

Теорема 5. Якщо в індексному рядку симплексной таблиці ЗЛП на мінімум міститься позитивна оцінка. а у відповідному стовпці змінної немає жодного позитивного елемента, то цільова функція на множині допустимих планів не обмежена знизу.

Теорема 6. Якщо в оптимальному плані M -завдання хоча б одна зі штучних змінних відмінна від нуля, то вихідна задача не має допустимих планів, тобто її система обмежень несумісна.