Симплекс-таблиці та способи роботи з ними

Розглянемо правила роботи з симплекс-таблицями на при­кладі.

Для виготовлення двох видів продукції А і В використову­ють три види сировини ,  та .

На виробництво одинці продукції А знадобиться витратити:

сировини I виду – 15 кг,

сировини II виду – 12 кг,

сировини III виду – 3 кг.

На виробництво одинці продукції В знадобиться витратити:

сировини I виду – 2 кг,

сировини II виду – 6 кг,

сировини III виду – 12 кг.

Запаси сировини:

I виду – 300 кг,

II виду – 306 кг,

III виду – 360 кг

Прибуток від реалізації оди­ниці продукції виду А становить 6 грн., виду В – 9 грн.

Скласти план виробництва продукції, який забезпечить максимальний прибуток від реалізації при наявності даних запасів сировини.

Розв'язування

Позначимо кількість виготовленої продукції першого виду А через х₁, другого – х₂. Враховуючи витрати сировини I, II та III виду на виготовлення одиниці продукції видів А та В, а також обмежені запаси сировини, запишемо систему обмежень (4.3). Прибуток, одержаний з виготовлення продукції у вигляді функції мети (4.4).

(4.3)

(4.4)

Зведемо задачу лінійного програмування (4.3, 4.3) до ка­нонічної форми додавши невідомі х₃, х₄ та х₅ до лівої сторони двох нерівностей відповідно:

(4.5)

;

.

Розв'яжемо систему рівнянь методом Гаусса-Джордана, то­му запишемо систему обмежень (4.5) у вигляді початкової розра­хункової таблиці 1, яку назвемо ітерацією 1.

Для знаходження початкового базового плану розділимо змінні на дві групи – базові і вільні. Для вибору базових змінних доцільно скористатися таким правилом: в якості базових змінних ітерації симплекс-таблиці необхідно вибрати такі змінні (їх кіль­кість визначається числом основних обмежень), кожна з яких тіль­ки раз входить у рівняння основних обмежень. Решту змінних бу­демо вважати вільними.

Запишемо цільову форму f у вигляді рівняння

Таблиця заповнюється формально за вибраною канонічною формою.

1. Заповнюємо базові стовпчики: на перетині однойменних ряд­ків і стовпчиків ставимо 1, а в усіх інших клітинках будуть нулі.

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

Ітерація 1

f 0		0	-9	-6	0	0	0
Базові невідомі	№ рядка	План (опорний розв'язок)	x1	x2	x3	x4	x5
x3	1	300	15	2	1	0	0
x4	2	306	12	6	0	1	0
x5	3	360	3	12	0	0	1

Критерій оптимальності. Якщо задача максимізується і в нульовому рядку відсутні від'ємні числа (за винятком хіба що сто­впчика "опорний розв'язок (план)"), то опорний план є оптималь­ним (при мінімізації задачі для оптимальності плану достатньо відсутності додатних чисел у нульовому рядку, за винятком, мож­ливо, опорного розв'язку).

Коефіцієнт рядка "0" можна інтерпретувати як приріст фун­кції f при збільшенні вільної невідомої на одиницю. Приріст буде додатним, якщо коефіцієнт від'ємний, і від'ємним – якщо коефіці­єнт додатний.

В нашому випадку є два від'ємні числа (–9), (–6), беремо най­більше за модулем від'ємне число (–9) (при мінімізації задачі – найбільше додатне), тоді стовпчик "х₁" будемо називати ключовим стовпчиком.

Для вибору ключового елемента складаємо відношення ві­льних членів (чисел стовпчика "опорний розв'язок") до відповід­них додатних чисел ключового стовпчика (усі інші відношення будемо вважати рівними нескінченності):

.

Перше відношення менше, тому число (15) першого рядка буде ключовим елементом. Ключовий елемент в таблиці позначаємо рамкою і переходимо до другої ітерації.