Як було зазначено вище, нелінійність задачі МП визначається нелінійністю цільової функції, або нелінійністю системи обмежень або і тим і другим. Задачі НП, в яких цільова функція є раціональною, а система обмежень — лінiйна, складають основу ДЛП. Вони шляхом нескладних перетворень зводяться до ЗЛП.
Розглянемо наступну задачу ДЛП: знайти екстремум функції
(4.15)
при обмеженнях
(4.16)
Розглянемо лише випадок, коли на допустимій множині планів задачі . Якщо , то задача (4.15)–(4.16) не має оптимального розв'язку, оскільки цільова функція необмежена на множині допустимих розв'язків.
Позначивши , задачу (4.15) — (4.16) запишемо у вигляді: знайти найбільше значення функції
(4.17)
при обмеженнях
(4.18)
(4.19)
Задача (4.17) – (4.19) є ЗЛП, яку ми можемо розв'язати СМ. Знайшовши її оптимальний розв'язок, , випишемо оптимальний розв'язок задачі (4.15) – (4.16) , де і .
Приклад 4.5. Знайти найбільше значення функції при обмеженнях
Розв'язок. Виходячи зі змісту задачі, змінні і не можуть бути одночасно рівними нулю, а це означає, що величина додатна. Позначивши , початкову задачу перепишемо так: знайти найбільше значення функції при обмеженнях
Запишемо задачу в канонічній формі: знайти найбільше значення функції при обмеженнях
і запишемо у вигляді, зручному для запису у симплексну таблицю:
Тоді перша симплексна таблиця буде мати вигляд:
–4
–15
–3
–1
Реалізуючи послідовно алгоритм СМ для ЗЛП, записаних в загальному вигляді, отримаємо
–4
4/5
–15/5
–18/5
–5
–7
1/5
–1
–7/5
–1
–1
–4/5
15/5
23/5
–12
12/5
–45/5
–59/5
–5/25
5/15
5/15
–5/25
5/15
–4/5
5/15
23/5
5/15
–4/5
23/5
5/15
36/5
36/5
3 останньої симплексної таблиці виписуємо оптимальний розв'язок: і Тоді розв'язок поставленої задачі: