Методичні вказівки до виконання практичного заняття на тему «Дробово-лінійне програмування»

Розв’язок:

Візьмемо цільову функцію задачі. Поділимо почленно чисельник на знаменник.

Введемо нові змінні:

; ; .

Тоді цільова функція набуде вигляду:

Z^`=3y₁+y₂

За умовою задачі х₁³0; х₂³0. Значить знаменник дробу буде невід’ємним числом (але при цьому він не повинен дорівнювати 0),а значить у₀. А отже, саме цей дріб, а значить і змінна у₀ , може бути лише додатнім: >0, тому, якщо, під час розв’язку задачі, змінна у₀ виявиться рівна 0, то це означатиме, що вихідна задача розв’язку немає.

Очевидно, що змінні у₁ та у₂ також будуть невід’ємними, оскільки чисельник і знаменник цих змінних невід’ємні.

Розглянемо систему обмежень: поділимо обидві частини першої нерівності на вираз (х₁+х₂).

х₁+2х₂£4 \:(х₁+х₂)

Тоді ми можемо ввести нові змінні, та отримати нову нерівність:

у₁+2у₂ £ 4у₀;

у₁+2у₂-4у₀ £ 0

Розглянемо другу нерівність:

5х₁+3х₂£15 \:(х₁+х₂)

;

5у₁+3у₂-15у₀£0

Таким чином, математична модель даної задачі набуває вигляду:

max Z=3y₁+y₂

у₁+2y₂-4y₀ £ 0;

5у₁+3у₂-15у₀ £ 0;

у₁³0; у₂³0; у₀0

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

Остаточно математична модель набуває вигляду:

maxZ^`=3y₁+y₂

у₁+2y₂-4y₀ £ 0;

5у₁+3у₂-15у₀ £ 0;

у₁+у₂ = 1;

у₁³0; у₂³0; у₀³0

Дана задача є задачею лінійного програмування і тому її можна розв’язати симплексним методом. Зведемо цю задачу до канонічного вигляду: Таблиця 1

БЗ	С_б	А_о	у₁	у₂	у₀	у₃	у₄	w₁
3	1	0	0	0	-М
у₃	0	0	1	2	-4	1	0	0
у₄	0	0	5	3	-15	0	1	0
w₁	-М	1	1	1	0	0	0	1
Z_j-C_j	0	-3	-1	0	0	0	0
-М	-М	-М	0	0	0	0
у₁	3	1	1	1	0	0	0	6/15
у₀	0	8/23	0	2/15	1	0	7/35	1/15
у₃	0	1/3	0	23/15	0	1	-4/15	7/15
Z_j-C_j	3	0	2	0	0	0	3
0	0	0	0	0	0	М