Симплек-метод у дробово-лінійному програмуванні

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

Ця подібність із задачею лінійного програмування дозволяє розв’язувати задачі дробово-лінійного програмування звичайним симплекс-методом зі зміненим критерієм оптимальності.

РОЗГЛЯНЕМО ЗАДАЧУ.

Знайти максимум функціоналу:

(3.1)

при обмеженнях

(3.2)

(3.3)

(3.4)

РОЗВ’ЯЗУВАННЯ.

1. Складаємо початкову симплекс-таблицю (Табл.1).

При чому, для F передбачаємо два рядка: у верхньому записуємо коефіцієнт чисельника p_j, в нижньому – знаменника q_j.

Табл.1

	-x₁ -x₂ -x _m	1
y₁= y₂= - y_m=	a ₁₁ a ₁₂ a _1n a ₂₁ a ₂₂ a _2n a _m1 a _m2 a _mn	a ₁ a ₂ a _m
F₁= F₂=	-p₁ -p₂ -p _m -q₁ -q₂ -q _m	0 0

2. План записаний в Табл. 1 не може бути опорним, так як F₂ = 0, отже серед b_і є від’ємні обов’язково.

Кроками МЖВ відшукуємо опорний план, перетворюючи коефіцієнти стрічок .

Нехай в результаті k – кроків отримаэмо таблицю (Табл.2).

Табл.2

	-y ₁-y ₂ -y_k -x_s -x _n	1
Х₁= Х₂= Х_k= Y_r= Y_m=	b ₁₁b ₁₂ b_1k b_1s b _1n b ₂₁b ₂₂ b_2k b_2s b _2n b _k1b _k2 b_kk b_ks b _kn b _r1b _r2 b_rk b_rs b _rn b _m1b _m2 b_mk b_ms b _mn	b ₁ b ₂ b _k b _r b _m
F₁= F₂=	- p_1‘-p₂‘ -p_k -p_s -p_n -q_1‘-q₂‘ -q_k -q_s -q_n

Тут вже всі b_j невід’ємні. В рядках F₁ і F₂ з’явились вільні члени P⁽^k⁾ і Q⁽^k⁾, Q⁽^k⁾ ¹ 0, .

Відшукання оптимального плану, тобто F_max

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

Рис.7.

Аналітично це означає зробити крок МЖВ з деяким b_rs. Задача полягає в тому, щоб встановити правило вибору b_rs (розв’язуючого елементу). Нехай ми вибрали b_rs. В новій (k+1) - ій таблиці замість P⁽^k⁾ буде стояти число:

(3.4)

Аналогічно замість i Q⁽^k⁾ буде стояти число:

(3.5)

Значення функціоналу на (k+1)- му кроці:

Далі знаходимо:

(3.6)

Позначимо:

(3.7)

З цими позначеннями отримаємо:

(3.8)

Дослідимо вираз (3.8)

1. Щоб не відірватися від многогранника розв’язків, симплексне відношення повинно бути і найменшим із всіх можливих

Звідки слідує, що , так як по умові допустимості плану . Отже, завжди.

2. Q⁽ⁱ⁾ завжди > 0, то Q⁽^k⁾×Q⁽^k⁺¹⁾ завжди > 0, тому знак F⁽^k⁺¹⁾ – F⁽^k⁾ залежить від знаку d_s. Коли d_s > 0, то F⁽^k⁺¹⁾ – F⁽^k⁾ < 0. Звідки F⁽^k⁺¹⁾ < F⁽^k⁾ або F⁽^k⁾ > F⁽^k⁺¹⁾.

Іншими словами, коли за розв’язуючий стовпчик взяти стовпчик з
d_s > 0, то після кроку МЖВ функціонал зменшується, а при виборі розв’язуючого стовпчика з d_s < 0, F⁽^k⁾ > F⁽^k⁺¹⁾ – функціонал збільшується.

При d_s = 0, F⁽^k⁺¹⁾=F⁽^k⁾ функціонал не змінюється.

Визначник d_s служить критерієм для вибору b_rs.

Алгоритм відшукання оптимального плану.

1. Після знаходження опорного плану обчислюються значення визначників:

значення яких заносяться в додатковий рядок таблиці.

В стовпчику вільних членів в цьому рядку записуємо значення функціоналу, рівне відношенню F₁ i F₂

В результаті приходимо до таблиці (Табл.3):

Табл.3

	-y ₁-y ₂ -x_s -x _n	1
х₁= х₂= y_m=	b ₁₁b ₁₂ b_1s b _1n b ₂₁b ₂₂ b_2s b _2n b _m1b _m2 b_ms b _mn	b ₁ b ₂ b _m
F₁= F₂=	p ₁p ₂ p_s p _n q ₁q ₂ q_s q _rn	0 0
d_j=	d ₁d ₂ d_s d _n

2. При розв’язуванні задачі на максимум функціоналу за розв’язуючий стовпчик вибираємо той, в якому d_j < 0. Коли таких стовпчиків декілька, то за розв’язуючий стовпчик краще брати той, в якому d_j найбільший по абсолютній величині.

3. Розв’язуючи елемент в стовпчику шукається по найменшому симплексному відношенню.

4. Із знайденим b_rs робимо один крок МЖВ при цьому коефіціенти стрічок F₁ і F₂ перетворюються за загальним правилом, а останній рядок не перетворюється і не записується.

5. Далі для кожного стовпчика обчислюємо визначники d_j, а для плану - значення функціоналу F^(k+1). Якщо серед d_j є хоча б один від’ємний, то робимо новий крок МЖВ і т. д.

6. Оптимальний розв’язок буде досягнуто, коли після чергового кроку всі визначники d_j стануть невід’ємними.

7. При розв’язуванні задачі на мінімум, за розв’язуючий приймається стовпчик з d_j > 0. Критерієм оптимальності служить недодатність d_j.

ПРИКЛАД.

Знайти максимум та мінімум функціоналу:

При виконанні обмежень:

РОЗВ’ЯЗАННЯ.

Складаємо початкову жорданову таблицю, заповнюючи коефіцієнтами функціоналу для чисельника та знаменника окремо два рядки F₁ F₂ (Табл.4).

Табл.4

1	-x ₁-х ₂ -x₃
y₁= y₂= y₃=	-3 6 1 -1 7 2 -2 4 -1	-1
F₁= F₂=	1 2 -1 3 1 5

Так як b₃ = -1 < 0, то план х₁ = х₂ = х₃ = 0 не є опорним.

Знайдемо опорний план. Відшукавши такий план, додаємо до таблиці ще один рядок, в який записуємо значення d_j і функціоналу F (Табл.5).

Табл.5

2	-x ₁-х ₂ -y₃
y₁= y₂= x₃=	-5 10 1 -5 15 2 2 -4 -1
F₁= F₂=	-3 2 1 7 -21 -5	-1
d_j	-8 -11 0	-1/5

Оскільки всі визначники d_j недодатні, робимо висновок, що функціонал досягає мінімуму у вершині

x₁ = 0, x₂ = 0, x₃ = 1

Для знаходження максимуму вибираємо за розв’язуючий другий стовпчик. Розв’язуючий елемент b_rs = 10. З цим елементом робимо крок МЖВ, перетворюючи всю таблицю, крім останнього рядка d_j. В результаті отримаємо таблицю виду (Табл.6).

Табл.6

3	-x ₂-y ₁ -y₃
x₂= y₂= x₃=	-1/2 1/10 1/10 5/2 -3/2 ½ 0 2/5 -3/5	1/10 17/2 7/5
F₁= F₂=	-2 -1/5 4/5 -7/2 21/10 -29/10	28/5 7/5
d_j=	-92/5 11/10 11/5	-12/71

Елемент від’ємний – це означає, що максимум ще не досягнуто.

В першому стовпчику вибираємо за розв’язуючий елемент з ним робимо наступний крок МЖВ і отримаємо нову таблицю (Табл.7).

Табл.7

4	-y ₂-y ₁ -y₃
x₁= x₂= x₃=	1/5 -1/5 1/5 2/5 -3/5 1/5 0 2/5 -3/5	9/5 17/5 7/5
F₁= F₂=	4/5 -7/5 6/5 7/5 0 -11/5	28/5 19
d_j=	184/25 -133/5 878/25	28/15

Обчисливши в новій таблиці всі знову знаходимо один від’ємний, а тому робимо ще один крок МЖВ з елементом . В результаті отримали таблицю (Табл.8).

Табл.8

5	-y ₂-y ₁ -x₃
x₁= x₂= y₃=	1/5 1/2 -1/10 2/5 3/2 -7/10 0 5/2 -3/2	5/2 11/2 7/2
F₁= F₂=	4/5 -7/2 -9/10 7/5 0 -11/5	21/2
d_j=

В Табл.8 всі визначники d_j невід’ємні. Це свідчить про те, що при значеннях невідомих функціонал досягає максимального значення . Задача розв’язана.