Метод штучного базису

Нехай З.Л.П. не приведена до канонічного виду, а має загальний вид

(43)

(44)

Де

У цьому випадку для рішення З.Л.П. застосовується метод штучного базису.

Для одержання базисних змінних до кожного з m рівностей обмежень (44) додамо по однієї змінної X_n + i ≥ 0 , що назвемо штучними і розглянемо розширену задачу.

Min =C₁X₁+…+C_nX_n+M(X_n+1+…+X_n+m) (45)

(46)

де М – досить велике позитивне число.

(45) – (46) називається М – задачею, перемінні X_n+1,…, X_n+m -штучні базисні змінні.

Верна теорема 7. Якщо в оптимальному плані М – задачі X=(X⁰₁,X⁰₂,-X⁰_m,0,…,0) усі штучні змінні X_n+1=0 (i=1,..,m), те вихідна задача (43-44) має рішення і її оптимальний план X⁰=(X⁰₁,…,X⁰_m)

З теореми 7 випливає, що якщо в оптимальному плані М-задачі є хоча б одна Xn+I>0 те вихідна задача не сумісна, тобто не має рішення.

Зауваження 10. Якщо вихідна задача розв’язується на max Z, то функція мети М-задачі має вид Z=C₁X₁+C₂X₂+…+C_nX_n-M(X_n+1+…+X_n+m)

При рішенні М-задачі оцінки змінних .

Тому ці оцінки записуються не в один рядок, а в двох. У m+1 – рядку коштують ∆'j (без М), а в m+2 – рядку коштують коефіцієнти при М ∆''j (рядок з М). При цьому по m+2 – рядку визначається перемінна, що вводиться в базис. Перерахування симплексів-таблиць у такий спосіб виробляється по m+2 – рядку до виключення з базису всіх штучних перемінних, а потім процес відшукання оптимального плану продовжується по оцінках ∆'j коштує в m+1 – рядку. Розглянемо і вирішимо З.Л.П. методом штучного базису, приведену в прикладі.

Складемо з вихідної задачі М-задачу. В 2-ому рівнянні є базисна перемінна X₅, тому туди не додаємо штучну перемінну.

MinZ=3X₁-X₃+X₄-2X₅+M(X₆+X₇)

X₁-X₂+2X₃+4X₄+X₆=11

X₁-X₂+3X₃+6X₄+X₅=19

2X₁-3X₂+5X₃+11X₄+X₇=26

Xj≥0

Запишемо дані в симплекс-таблицю і заповнимо оцінні рядки 4 і 5 по формулах

					-1		-2	М	М
Xb	Cb	(Xb)i	X1	X2	X3	X4	X5	X6	X7	Θ
X6	M			-1						11/4
X5	-2			-1						19/6
X7	M			-3						26/11
БезM	Z	-38	-5		-5	-13
СМ	Z			-4
Х6	M	17/11	3/11	1/11	2/11				-4/11	17/3
X5	-2	53/11	-1/11	7/11	3/11				-6/11
X4		26/11	2/11	-3/11	5/11				1/11	26/2
БезM	Z	80/11	-29/11	-17/11	10/11				13/11
CM	Z	17/11	3/11	1/11	2/11				-15/11
X1		17/3		1/3	2/3			11/3	-4/3	17/2
X5	-2	16/3		2/3	1/3			1/3	-2/3
X4		4/3		-1/3	1/3			-2/3	-1/3
БезM	Z=	23/2		-2/3	8/3			29/3	7/3
CM	Z=0
X1						-2				3/1
X5	-2					-1				4/1
X3	-1			-1						-
Z	=	-3				-8
X2						-2
X5	-2		-1
X3
Z		-9	-2			-4

У 5-ої (m+2) рядку є оцінки ∆''j >0 (∆₁=3;∆₃=7;∆₅=15)

Тому опорний план М-задачі не оптимальний. Тому що ∆₅=15 (оцінка з М) найбільша, то X₄ введемо в базис. Знайдемо для X₄ симплексне відношення Θ₀=min(11/4;19/6;26/11)=26/11

Тому дозволяє елемент =11 і X₇ виводимо з базису. Для цього перераховуємо таблицю, застосовуючи (41) – (42), і так далі.

Після двох перерахувань чи таблиці двох ітерацій у базисі не залишиться штучних змінних, базисні перемінні X1,X4,X5 m+2 (п'яту) рядок відкидаємо й аналіз проводимо по 4 рядку. Тому що ∆3=8/3>0, то отриманий опорний план не оптимальний і в базис уводимо переменнуюX3 (вектори ₃) замість X4, Θ₀=min(17/2;16;4)=4

Елемент, дорівнює 1/3. Після перерахування таблиці одержуємо, що опорний план з базисними перемінними неоптимальний, тому що ∆₂=2>0. Тому X₂ вводимо, як нову базисну змінну замість X₁, тому що Θ₀=min(3/1;4/1)=3

У результаті перерахування симплекса-таблиці одержали оптимальний план X⁰=( ⁰₁=0; X⁰₂=3; X⁰₃=7; X⁰₄=0; X⁰₅=1), тому що всі ∆j≤0, що забезпечує min=Z(X⁰)=-9

5. Двоїсті задачі лінійного програмування. Економічна інтерпретація цих задач і їхніх рішень.

5.1. Поняття подвійності.

З кожною З.Л.П. тісно зв'язана інша задача лінійного програмування, звана двоїстою. Первісна задача називається вихідної. Їхній зв'язок полягає в тому, що рішення однієї з них може бути отримане з рішення іншої, так і використання отриманого рішення однієї для проведення економічного аналізу іншої задачі.

Як приклад, розглянемо задачу розподілу ресурсів, записану в загальному виді.

Постановка задачі

Підприємство має m видів ресурсів у кількості одиниць, з яких виробляється n видів продукції. Для виробництва одиниці j-ої продукції витрачається a_ij одиниць i-го ресурсу, а вартість одиниці j-ої продукції - C_j.

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

Змоделюємо задачу. Для цього позначимо за X_j кількість одиниць j-ой продукції, планованої для виробництва. Тоді математична модель: знайти X=(X₁,X₂,..,X_n), дозволяючий

(47)

і що доставляє

(48)

Двоїста задача.

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

Змоделюємо двоїсту задачу.

Позначимо через y_i (i=1,…,m) вартість одиниці i-го виду ресурсів. Тоді вартість усіх ресурсів дорівнює , а вартість усіх ресурсів, що йдуть на виготовлення одиниці j-го виду продукції, дорівнює

Тоді двоїста задача формулюється: знайти , що задовольняє

(49)

і що доставляє

(50)

Перемінні називаються чи оцінками обліковими, неявними цінами.

5.2. Види двоїстих задач. Теореми подвійності.

Двоїсті задачі бувають несиметричні і симетричні. Представимо ці види задач у матричній формі.

Несиметричні задачі

Вихідна задача Двоїста задача

(51)

(52)

Симетричні задачі

(53)

(54)

(55)

Зв'язок між оптимальними планами пари двоїстих задач установлює

Теорема 8. Якщо з пари двоїстих задач одна має оптимальний план, то й інша має рішення, причому min Z = max f чи min f = max Z. Якщо функція мети однієї з задач не обмежена, то друга задача не має рішення.

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

Більш конкретно зв'язують оптимальні рішення пари симетричних двоїстих задач наступні тотожності, зазначені в теоремі 9.