1.4.2. Зведення задачі дробово-лінійного програмування до лінійного виду

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

Початкова задача має такий вигляд:

(1.98)

(1.99)

(1.100)

Припустимо, що і здійснимо таку заміну змінних:

(1.101)

(1.102)

Після підстановки нових змінних y₀, у_j в початкову задачу прийдемо до такої лінійної задачі:

(1.103)

(1.104)

(1.105)

(1.106)

Знайшовши оптимальний розв’язок лінійної задачі у₀*,у_j* з очевидністю отримаємо оптимальний розв’язок початкової задачі:

х_j*=у_j*/у₀*.

Приклад 6. Знаходження компромісного розв’язку

Основна задача має вигляд:

f₁(x) = 3x₁+4x₂  max,

f₂(x) = x₁+5x₂  max

3x₁+x₂  75

x₁+x₂  30

x₁+4x₂  84

x₁,x₂  0.

Оптимальними будуть розв’язки:

Х₁*= (12;18), Х₂*= (0;21),

У₁*= 108 , У₂* = 105.

Доповнена задача, побудована за принципом справедливого компромісу, набере такого вигляду:

Z  min

3x₁ + x₂  75

x₁ + x₂  30

x₁ + 4x₂  84

3x₁ + 4x₂ + 108 Z 108

x₁ + 5x₂+ 105 Z  105

x₁, x₂ , Z  0.

Компромісний розв’язок характеризується такими даними:

Х₃*=(10,63;18,34), f₁(Х₃*)=105,25108; f₂(Х₃*)=102,33105.

Z=max{(108-105.25)/108; (105-102.33)/105}=max{0.0255; 0.0254}=0.0255

Тобто відносне погіршення оптимального значення кожної ФМ не перевищить 2,55%.

При формуванні доповненої задачі слід звертати увагу на напрям оптимізації. Якщо певна функція мети мінімізується, то відповідне додаткове обмеження набере такого вигляду:

Приклад 7. Зведення задачі ДЛП до лінійного виду

Зведемо задачу дробово-лінійного програмування

f(x)=2x₁+3x₂(5x₁+6x₂)max

x₁+2x₂  6

3x₁+2x₂ 14

3x₁+4x₂ 12

x₁; x₂  0

до лінійного виду.

Зробимо заміну змінних величин:

Після підстановки в початкову задачу отримаємо лінійну задачу:

2у₁ + 3у₂  max,

у₁ + 2у₂ - 6у₀  0,

3у₁ + 2у₂ - 14у₀  0,

3у₁ + 4x₂ - 12у₀  0

5у₁ + 6у₂ = 1,

у₀0; у₁,у₂0.

Оптимальним розв’язком лінійної задачі буде такий:

у₁* = 0; у₂* = 0,1667; у₀* = 0,0556.

Звідси отримуємо оптимальний розв’язок задачі ДЛП:

Якщо під функцією мети розуміти рентабельність продукції, то отриманий результат має таке тлумачення. Оптимальним планом виробництва продукції, який забезпечує максимальну рентабельність на рівні 50%, буде х₁*=0, х₂*=3.

Тема 1.5. Нелінійні статичні моделі

1.5.1. Загальні поняття про нелінійну модель

Якщо зв’язок між змінними величинами, які входять у модель, або функція мети є нелінійними, то модель належить до класу нелінійних.

Можливі такі випадки:

а)

б)

в)

У випадку а) функція мети є лінійною, а обмеження нелінійними. У випадку б) функція мети є нелінійною, а обмеження - лінійними. У випадку в) і функція мети, і обмеження є нелінійними.

Нелінійна модель на відміну від лінійної має такі особливості:

• область допустимих розв’язків може бути неопуклою, складатися з відокремлених підмножин;

• функція мети може бути неопуклою;

• точки екстремуму функції мети можуть знаходитися як на границі області допустимих розв’язків, так і в середині області.

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