• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Дробово-лінійне програмування

Як було зазначено вище, нелінійність задачі МП визначається нелінійністю цільової функції, або нелінійністю системи обмежень або і тим і другим. Задачі НП, в яких цільова функція є раціональною, а система обмежень — лін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 останньої симплексної таблиці виписуємо оптимальний розв'язок: і Тоді розв'язок поставленої задачі:

, , і .

Читайте також:

1. Алгебраїчне та інсерційне програмування
2. Безпосереднє програмування відеопам'яті
3. Виконання програми - реалізація мови програмування
4. Використання пакету Maple для розв’язування задач лінійного програмування
5. Вступ до мови програмування
6. Геометрична інтерпретація задачі лінійного програмування
7. Геометрична інтерпретація задачі нелінійного програмування
8. Геометрична інтерпретація розв’язків цілочислових задач лінійного програмування на площині
9. Графічний метод розв’язування задач лінійного програмування
10. Державне регулювання суспільного відтворення та його форми. Планування та програмування
11. Динамічне програмування.
12. Динамічного програмування

Переглядів: 1520