Застосування симплекс-таблиць

Розглянемо задачу лінійного програмування на знаходження мінімуму лінійної функції F = c₁x₁ + c₂x₂ +... + c_nx_n за системою обмежень

(2.23)

Систему обмежень запишемо у векторному вигляді

A₁x₁ + A₂x₂ +... + A_mx_m + A_m+1x_m+1 +...+A_nx_n = A₀, X 0, (2.24)

де

, ,..., ,

,

,

Початковий опорний план X₀ = (x₁ = b₁;...; x_m = b_m; 0;...; 0) задачі, (2.23) визначається системою m -вимірних одиничних векторів A₁, A₂,..., A_m. Щоб дослідити його на оптимальність, треба вектори A_j (j = 1, 2 ,..., n) системи (2.24) описати лінійною комбінацією базисних векторів і обчислити значення оцінок f_j - c_j.

Оскільки базис системи (2.23) – одиничний, то коефіцієнтами у виразі вектора через базисні будуть його компоненти, тобто x_ij = a_ij (i = 1, 2 ,..., m; j = 1, 2 ,..., n). Обчислення наступного опорного плану та перевірку його оптимальності зручно виконувати, записавши умову задачі і дані, знайдені після побудови початкового опорного плану у симплексну таблицю. У першому її стовпці записано номери рядків таблиці. Стовпець базису містить базисні вектори. У стовпці C базису записано коефіцієнти даної лінійної функції, які відповідають базисним векторам. У стовпці A₀ - початковий опорний план. У цьому самому стовпці в результаті обчислень знаходять оптимальний план.

Стовпці A_j (j = 1, 2 ,..., n) заповнено коефіцієнтами вектора A_j через базисні вектори. У (m+ 1)-му рядку стовпця A₀ записано значення лінійної функції F (X₀), якого вона набуває при початковому опорному плані, а в стовпцях A_j – значення оцінок f_j - c_j. Оцінки можна обчислити, якщо від добутків елементів стовпця A_j на відповідні елементи стовпця C базису відняти відповідні коефіцієнти c_j. Далі обчислення симплекс-методом слід здійснювати за таким алгоритмом.

1. Розглянути оцінку плану (m+ 1)-го рядка. Якщо всі оцінки недо­дат­ні, то опорний план X₀ оптимальний і мінімум лінійної функції дорівнює F (X₀). Якщо серед оцінок є хоча б одна додатна, то перейти до п.2.

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

Коментар. Якщо у кожному стовпці A_j, що відповідають додат­ним оцінкам плану, є додатні коефіцієнти, то план X₀ неоптимальний і можна побудувати новий опорний план, який надасть лінійній функції значення, менше від попереднього. Задача полягає в тому, щоб один з базисних векторів замінити новим. Вектор, який вводять у базис, вибирають в п.3, а вектор, який виводять з базису – в п.5.

3. Вибрати вектор з найбільшою додатною оцінкою. Нехай це буде вектор A_k. Перейти до п.4.

4. Обчислити відношення елементів стовпця A₀ до відповідних додатних елементів стовпця A_k, результати записати у відповідних рядках стовпця q і перейти до п.5.

5. Серед векторів базису вибрати той, який відповідає найменшому з відношень, обчислених у п.4. Нехай це буде вектор A_l. Перейти до п.6.

Коментар. Елемент x_lk називається головним, рядок і стовпець, на перетині яких він міститься, називаються головними. Після визначення ведучого елемента заповнюють нову симплексну таблицю. Перші три стовпці нової таблиці відрізнятимуться від старої тільки рядком з номером l. У ньому замість елементів l, A_i, c_i будуть записані елементи l, A_k, c_k. Інші клітинки нової таблиці заповнюють згідно з пп.6 і 7.

6. Поділити елементи l -го рядка, які відповідають векторам A_j (j = 1, 2, ..., n), на головний елемент і результати записати у відповідні клітинки l -го рядка нової таблиці. Перейти до п.7.

7. Для знаходження елементів і -го (i = 1, 2, ..., l- 1, l+ 1, ..., m+ 1) рядка нової таблиці треба від елементів і -го рядка старої таблиці відняти відповідні елементи l -го рядка нової таблиці, помножені на x_ik (i ¹ l). Після заповнення нової таблиці перейти до п.1.

Відзначимо, що коли у таблиці є кілька додатних оцінок плану, то під час обчислення у базис вводять вектор, якому відповідає максимальна оцінка. Завдяки такому вибору вектора можна досягти оптимального пла­ну за мінімум ітерацій. Якщо ж є кілька рівних найбільших значень q_0j (f_j - c_j), то з відповідних їм векторів вибирають той, якому відповідає min c_j.

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

Задачу знаходження максимального значення лінійної функції можна розв’язати, не зводячи її до задачі мінімізації. План задачі знаходження максимуму буде оптимальним тільки тоді, коли його оцінки бу­дуть не­від’єм­ними. Якщо ж умова оптимальності не виконується, то під час обчислень в базис вводять вектор, якому відповідає min [ q_0j(f_j - c_j) ], де мінімум береться серед тих j, для яких f_j - c_j < 0. Якщо мінімальних оцінок кілька, то в базис вводять вектор, якому відповідає min c_j.

Приклад 2.6. Знайти мінімум функції F=x₁+x₂+x₃ за обмежень:

Розв’язання. Запишемо систему обмежень у векторному вигляді

x₁A₁ + x₂A₂ +... + x₆A₆ = A₀,

де ; ; ; ; ; ; .

Дана система обмежень у явному вигляді містить одиничний базис A₁ , A₂ , A₃. Тому змінні x₁ , x₂ , x₃ - базисні, а x₄ , x₅ , x₆ - вільні змінні. Поклавши x₄ = x₅ = x₆ = 0, знайдемо початковий опорний план X₀ =(x₁= 0; x₂= 0; x₃= 0; x₄= 0; x₅= 0; x₆= 0), якому відповідає комбінація x₁A₁ + + x₂A₂ + x₃A₃ = A₀ і значення функції F(X₀) = 1×5 +1×3 + 1×5 = 13.

Для перевірки плану X₀ на оптимальність заповнимо першу симплексну таблицю (табл. 2.4) і обчислимо значення оцінок:

f₄ - c₄ = 1×(-1) + 1×2 + 1×2 - 0 = 3;

f₅ - c₅ = 1×0 + 1×(-3) + 1×(-5) - 0 = -8;

f₆ - c₆ = 1×(-2) + 1×1 + 1×6 - 0 = 5.

Для базисних векторів значення оцінок нульові. Серед обчислених оцінок є дві додатні. Більша з них f₆ - с₆ = 5 відповідає вектору А₆, який і введемо в базис. Для визначення вектора, який треба вивести з базису, обчислимо q₀₆ . Мінімальне відношення відповідає вектору А₃ базису. Отже, його треба замінити вектором А₆. Головним елементом у першій симплексній таблиці є число 6, яке стоїть на перетині третього рядка і стовпця А₆. Виконаємо одну ітерацію симплексних перетворень і заповнимо другу симплекс-таблицю. Нові елементи головного рядка знайдемо, поділивши елементи ведучого рядка початкової симплекс-таблиці на головний елемент (число 6). За допомогою обчисленого рядка знайдемо елементи інших рядків другої таблиці методом симплексних перетворень: помножимо його елементи на 2 і додамо до відповідних елементів першого рядка початкової симплекс-таблиці; віднімемо його елементи від відповідних елементів другого рядка; помножимо його на мінус 5 і додамо до четвертого рядка. В результаті дістанемо заповнену другу таблицю.

Таблиця 2.4

Ітерація

Рядок

Базис

С базису

A0

c1 = 1

c2 = 1

c3 = 1

c4 = 0

с5 = 0

c6 = 0

A1

A2

A3

A4

A5

A6

S

q

A1

-1

-2

A2

-3

A3

-5

5/6

fj -

cj

-8

A1

20/3

1/3

-1/3

-5/33

A2

13/10

-1/6

5/3

-8/ 6

5/2

13/10

A3

5/6

1/6

1/3

-5/6

3/2

5/2

fj -

cj

53/6

-5/6

4/3

-38/6

11/2

A1

71/10

1/5

3/10

-21/10

13/2

A2

13/10

3/5

-1/10

-13/10

3/2

A3

2/5

-1/5

1/5

-2/5

fj -

cj

71/10

-4/ 5

-7/10

-21/10

7/2

Для базисних векторів значення оцінок нульові. Серед обчислених оцінок є дві додатні. Більша з них f₆ - с₆ = 5 відповідає вектора А₆, який і введемо в базис. Для визначення вектора, який треба вивести з базису, обчислимо q₀₆ . Мінімальне відношення відповідає вектора А₃ базису. Отже, його треба замінити вектором А₆. Головним елементом у першій симплексній таблиці є число 6, яке стоїть на перетині третього рядка і стовпця А₆. Виконаємо одну ітерацію симплексних перетворень і заповнимо другу симплекс-таблицю. Нові елементи головного рядка знайдемо, поділивши елементи головного рядка початкової симплекс-таблиці на головний елемент (число 6). За допомогою обчисленого рядка знайдемо елементи інших рядків другої таблиці методом симплексних перетворень: помножимо його елементи на 2 і додамо до відповідних елементів першого рядка початкової симплекс-таблиці; віднімемо його елементи від відповідних елементів другого рядка; помножимо його на мінус 5 і додамо до четвертого рядка. В результаті дістанемо заповнену другу таблицю.

Правильність проведених обчислень контролюємо за допомогою стовпця S, кожний елемент якого обчислюється двома способами: за допомогою симплексних перетворень та додаванням елементів відповідних рядків. У другій симплексній таблиці маємо новий опорний план Х₁ =(20/3, 13/6, 0, 0, 0, 5/6), якому відповідає значення лінійної функції F (X₁)=53/6 < F(X₀) =13. У четвертому рядку таблиці маємо додатну оцінку f₄ - с₄ = 4/3.

Отже, вектор А₄ вводимо до базису. Знайшовши q₀₄ , побачимо, що вектор А₂ треба вивести із базису. Головний елемент стоїть на перетині другого рядка і стовпця А₄. Виконаємо один крок симплексних перетворень. У результаті дістанемо план Х₂ =(71/10,0,0, 13/10, 2/5). У четвертому рядку останньої симплекс-таблиці усі оцінки не додатні. Отже, план Х₂ – оптимальний. Він надав лінійній функції значення F(X₂) =71/10. На основі оцінок цього плану робимо висновок, що оптимальний план є єдиним, оскільки нульові оцінки відповідають тільки базисним векторам.

Приклад 2.7. Знайти максимум лінійної функції F = 40 x₁ + 30 x₂ за обмежень

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

Запишемо систему у векторній формі

x₁A₁ + x₂A₂ +... + x₅A₅ = A₀,

де ; ; ; ; ; . Одиничні вектори A₃, A₄, A₅ утворюють базис і задають опорний план Х₀= (0;0;30;24;20).

Значення лінійної функції F (X₀) = 40×0+30×0=0. Для перевірки плану X₀ на оптимальність складаємо симплекс-таблицю (табл. 2.5). Обчислимо значення оцінок плану f₁ =0×5+0×2+0×4=0, f₂ =0×6+0×6+0×2=0, f₁ - c₁ = = -40, f₂ - c₂ =-30.

Таблиця 2.5

Ітерація	Рядок	Базис	С базису		c1 = 1	c2 = 1	с3 = 1	c4 = 0	c5 = 0
A0	A1	A2	A3	A4	A5	S	q
		A3
	A4
	A5
	fj -	cj		-40	-30				-70
		A3				7/2			-5/ 4	33/4	10/7
	A4							-1/2	39/2	14/5
	A1				1/2			1/4	27/4
	fj -	cj			-10
		A3		10/7			2/7		-5/14	33/14
	A4		48/7			-10/7		9/7	54/7
	A1		30/7			-1/ 7		3/7	39/7
	fj -	cj	1500/7			20/7		45/7	1565/7

Для векторів базису оцінки дорівнюють нулю. Серед обчислених оцінок дві від’ємні: f₁ - c₁ = -40, f₂ - c₂ = -30. Отже, опорний план Х₀ не є оптимальним. Найменша оцінка відповідає вектору А₁, який введемо в базис. Визначимо вектор, виключений з базису. Для цього обчислимо q₀₁ = = min (30/5, 24/2, 20/4). Найменше з відношень відповідає вектору А₅, тому його замінюємо вектором А₁. Головним елементом є число 4, яке стоїть на перетині третього рядка і стовпця А₁. Складаємо другу симплекс-таблицю. Обчислимо нові значення головного рядка. Для цього елементи головного рядка поділимо на 4 і запишемо в третьому рядку другої таблиці. Тепер за допомогою цього рядка виконаємо одну ітерацію симплексних перетворень, тобто помножимо його елементи на 5 і віднімемо від першого рядка першої ітерації, потім помножимо його елементи на 2 і віднімемо від другого рядка першої ітерації, помножимо його на 40 і додамо до четвертого рядка першої ітерації. Правильність проведених обчислень контролюємо за допомогою стовпця S, кожний елемент якого обчислюється двома способами: за допомогою симплексних перетворень і підсумовуванням елементів відповідних рядків.

Після завершення другої ітерації дістали план Х₁ =(5; 0; 5; 14; 0), якому відповідає значення лінійної функції F (Х₁) = 200. У четвертому рядку f₂-c ₂=-10 < 0, тому план Х₁ не є оптимальним і вектор А₂ слід ввести в базис. Обчислимо q₀₂ = min (10/7, 14/5, 10)=10/7. Число 7/2 стоїть на перетині першого рядка і стовпця А₂, є головним. Вектор А₃ вилучаємо з базису. Виконавши третю ітерацію симплексних перетворень, дістанемо нову таблицю. Оскільки в четвертому рядку всі оцінки плану Х₂ = (30/7; 10/7; 0; 48/7; 0) невід’ємні, то опорний план Х₂ - оптимальний, йому відповідає значення лінійної функції F(Х₂) =1500/7.

Зазначимо, що кожне число, записане в таблиці, має не тільки математичний, а й певний економічний зміст. Так, у четвертому рядку першої ітерації симплексної таблиці 5 є дві від’ємні оцінки: f₁-с₁ =-40, f₂-c₂ =-30. Число 40 означає, що від включення до плану виробництва одиниці продукції Р₁ прибуток збільшиться на 40 у.о. Якщо включити до плану виробництва одиницю продукції Р₂, то прибуток збільшиться на 30 у.о. Тому з економічного погляду доцільніше включати до плану продукцію Р₁. Цей висновок цілком узгоджується із формальним критерієм оптимальності опорного плану симплексного методу, оскільки найменша оцінка відповідає вектору А₁. Число q₀₁ =5 означає, що максимальна кількість продукції, яку можна включити до плану виробництва, дорівнює п’яти одиницям. При цьому сировину третього виду буде використано повністю.

Після завершення другої ітерації у колонці А₀ дістали опорний план Х₁ =(5; 0; 5; 14; 0). Згідно з цим планом виробляється 5 одиниць продукції Р₁ і залишається невикористаною 5 одиниць сировини S₁ і 14 одиниць сировини S₂. Прибуток від реалізації виробленої продукції становить 200 у.о. В результаті симплексних перетворень змінилася не тільки колонка А₀, а й інші колонки таблиці. Їх економічний зміст став ще складнішим. Розглянемо, наприклад, колонку А₂. Число Ѕ в третьому рядку показує, на скільки одиниць треба зменшити виробництво продукції Р₁, якщо запланувати випуск продукції Р₂. Числа 7/2 і 5 у першому і другому рядках колонки А₂ означають, скільки треба витратити одиниць сировини S₁ і S₂, відповідно, якщо запланувати виготовлення одиниці продукції Р₂. Число 10 у четвертому рядку означає, що прибуток, який буде одержано від реалізації одиниці продукції Р₂, становитиме 10 у.о. Інакше кажучи, включення до плану виробництва одиниці продукції Р₂ зумовлює зменшення випуску продукції Р₁ на Ѕ одиниць і додаткові затрати 7/2 одиниць сировини S₁ і 5 одиниць сировини S₂, а загальний прибуток від реалізації продукції відповідно до нового плану зросте на 10 у.о. Дещо інший економічний зміст мають числа, записані в колонці А₅. Число 1/4 в третьому рядку цієї колонки означає, що збільшення обсягу сировини S₃ на 1 одиницю дасть змогу збільшити випуск продукції Р₂ на 1/4 одиниці. Одночасно треба буде додатково взяти 5/4 одиниці сировини S₁ і 1/2 одиниці сировини S₂. Збільшення випуску продукції Р₂ на 1/4 одиниці забезпечить збільшення при­бут­ку на 10 у.о. З економічного аналізу даних таблиці після другої ітерації випливає, що план Х₁ не є оптимальним. Це видно і з четвертого рядка симплекс-таблиці, оскільки у колонці А₂ – від’ємна оцінка плану.

Після третьої ітерації знайшли оптимальний план Х₂ =(30/7, 10/7, 0, 48/7, 0) випуску продукції, який включає виробництво 30/7 одиниць продукції Р₁ і 10/7 одиниць продукції Р₂. При такому плані випуску продукції буде повністю використано сировину першого і третього видів і залишиться невикористаною 48/7 одиниць сировини другого виду. Прибуток від реалізації запланованої продукції становитиме 1500/7 у.о.