Двоїстість лінійного програмування.

Лекція №1

 

Література:

1. Таха Х.А. Введение в исследование операций. – М.:Мир, 1985. – 496 с.

2. Мину М. Математическое программитование и алгоритмы.– М.:Наука, 1990.– 448 с.

3. Вентцель Е. С. “Исследование операций”, М. 1972 г.

4. Зайченко Ю.П. Дослідження операцій.Підручник. – К. «Слово»,2006. – 816с.

5. Зайченко О.Ю., Зайченко Ю.П. Дослідження операцій. Збірник задач. – К.: «Слово»,2007. – 472 с.

6. Заславский В.С. “Исследование операций. Сборник задач”, М.1980. – 275с.

7. Юдин Д. Б., Гольштейн Е. Г. “Линейное программирование. Задачи и методы линейного программирования ”, М. 1994, 344с.

 

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

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

Ціль ДСО – кількісне обгрунтування приймаємих рішень стосовно керування організацією.

Основні етапи ДСО:

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

2. Побудова математичної моделі.

3. Знаходження розв”язків.

4. Перевірка і корегування моделі.

5. Реалізація знайденого рішення на практиці.

(1). Задача ставиться замовником, а операційна група конкретизує її.

(2). Формалізація задачі.

Цільова функція задачі (показник якості, чи ефективності системи):

max E = f (x, y) (1.1)

при обмеженнях g_i (x, y) £ b_i, i = 1, m (1.2), де

х- вектор керованих змінних;

у – вектор некерованих змінних;

g_i – функція споживання і-го ресурсу;

b_i – величина і-го ресурсу.

(3). Для знаходження оптимального рішення задачі (1.1, 1.2) в залежності від виду і структури цільової функції та обмежень використовують відповідні методи теорії оптимальних рішень:

- лінійне програмування (якщо f (x, y), g_i (x, y) – лінійні функції відносно змінної х);

- нелінійне програмування (якщо f (x, y), g_i (x, y) – не лінійні функції відносно змінної х);

- динамічне програмування (якщо цільова функція має визначену структуру (адитивна, чи мультиплікативна відносно х);

- стахостичне програмування (якщо вектор у – випадковий);

- дискретне програмування (якщо на змінну х накладена умова дискретності);

- евристичне програмування (якщо точний оптимум знайти алгоритмічним шляхом неможливо через велику кількість варіантів).

 

Класи задач ДСО (за своєю постановкою):

1. Задача керування запасами.

2. Задача розподілення ресурсів.

3. Задача ремонту і заміни обладнання.

4. Задача масового обслуговування.

5. Задача теорії розкладів.

6. Задача вибору маршруту.

7. Задача планування і розміщення.

 

Приклади задач.

1. Транспортна задача.

Маємо m пунктів виробництва. Нехай виробництво однієї продукції з обсягами виробництва за даний період часу а₁, а₂, …, а_m. Маємо n споживачів з потребами в₁, в₂, …, в_n. Сумарний обсяг виробництва співпадає з потребами. Вартість перевезень одиниці продукції з і-го пункту виробництва в j–й пункт споживання с_{і j}.

Завдання: скласти такий план перевезень від постачальників до споживачів, щоб всі потреби були задоволені, а сумарні витрати на перевезення – мінімальними.

Розв”язок:

Вводимо невідомі х _іj (обсяг перевезень з і-го пункту виробництва в j–й пункт споживання.

Визначаємо цільову функцію:

Визначаємо умови обмеження:

Тоді повинні виконуватись такі умови:

(3.1)

(j = 1, 2, …, n) (3.2)

(i = 1, 2, …, m) (3.3)

X_ij ≥ 0; (3.4)

 

 

Умова (3.3) гарантує повне вивезення продукту з усіх пунктів виробництва, а умова (3.2) – повне задоволення попиту в усіх пунктах споживання.

 

Матрицю

Х =	║xij║mn =	x11 x12... x1n x21 x22... x2n .............. xm1 xm2... xmn

називають планом перевезень Т-задачі, а змінні x_ij – перевезеннями.

 

 

2. Задача про дієту.

Для людини необхідно скласти харчовий раціон, який повинен включати:

- білків не менше а1 гр.,

- вуглеводів не менше а2 гр.,

- мінеральних солей не менше а3 гр.,

- вітамінів не менше а4 гр. за добу.

Нехай:

- добова потреба в цих елементах – m;

- маємо n видів харчових продуктів;

- а _іj – кількість елемента і в одиниці продукту j;

- с_j – ціна одиниці продукту j.

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

Розв”язок:

Вводимо невідомі х _j (кількість j–го продукту).

Визначаємо цільову функцію:

Визначаємо умови обмеження:

а _іj х _j ³ а ₁

 

3. Задача про рюкзак.

Маємо рюкзак визначеного розміру. Нехай місткість рюкзака дорівнює d. Маємо n предметів з обсягами а₁, а₂, …, а_n. Ступінь важливості кожного продукту – с _j. Виконуються умови.

Завдання: вирішити які предмети покласти в рюкзак, щоб сумарна цінність була максимальна.

.

 

 

Висновки:

- функція, яка максимізується (мінімізується) називається цільовою;

- умови, яким підпорядковуються змінні, називаються обмеженнями задачі;

- любий набір значень невідомих х₁, х₂, …, х_n, х_і³ 0, задовольняє всім обмеженням над допустимим розвязком задачі (сукупність всіх допустимих розвязків складає допустиму множину);

- допустиме рішення, яке дає цільовій функції максимум (мінімум), називають оптимальним рішенням задачі, а саме значення цільової функції при цьому розвязкі – оптимумом.

Лекція №2

 

Приклад:

Дані розв’язки:

х¹= (4, 0, 8, 1, 0);

х²= (0, 1, 10, 0, 0);

х³= (,,,,).

Завдання: перевірити допустимість розвязків.

Відповідь: х¹ , х² - допустимі розвязки, х³ - недопустимий розв’язок.

Знайти значення цільової функції:

f (х¹) = 2 – оптимальний розв’язок;

f (х²) = -7– оптимальний розв’язок.

 

Задачі лінійного програмування (ЗЛП).

Форми ЗЛП.

1. ЗЛП з обмеженнями – рівностями (основна ЗЛП).

Канонічна форма ЗЛП.

Маємо: х₁, х₂, …, х_n.

Необхідно знайти такі невідємні значення цих змінних, яких би задовольняли системи лінійних рівнянь (3)

і, крім цього, обертали б в мінімум лінійну функцію:

L = c₁x₁ + c₂x₂ + … c_nx_n ® min.

 

2. Симетрична форма.

L = c₁x₁ + c₂x₂ + … + c_nx_n ® min (4.1);

 

(4.2)

 

Будемо вважати, що всі ці нерівності лінійно – незалежні, тобто жодне з них неможливо представити в вигляді лінійної комбінації інших.

Перехід від однієї форми ЗЛП в іншу.

Від задачі з обмеженнями легко перейти до ОЗЛП. Будемо вважати, що ЗЛП задана в вигляді

 

(4.3).

 

Будемо називати змінні у₁, у₂, …, у_м додатковими змінними.

Припустимо, що ЗЛП задана в вигляді

 

 

Таким чином виникає ЗЛП.

Знайти всі відємні значення n+m змінних х₁, …, х_n, у₁, …, у_m, щоби вони задовольняли систему (4.3) і перетворювали в максимум, або в мінімум функцію (4.1). Отже, отримали ОЗЛП.

Можливий і зворотній перехід.

Нехай дана ЗЛП в канонічній формі, або стандартній. Введемо позначення

 

- матриця ЗЛП,

- вектор вільних членів,

с = (с₁, с₂, …, с_n) – вектор коефіцієнтів ЦФ,

- вектор невідомих.

Тоді задача прийме вигляд

(c, x) ® max;

A₁x₁ + A₂x₂ + … + A_nx_n ³ b, де

А – вектори умов задачі при Х.

 

Геометричний зміст ЗЛП.

Розглянемо випадок, коли число змінних (n) на два більше ніж число незалежних рівняннь (m), тобто (n – m) = 2.

В такому випадку можна дві змінних, наприклад х₁ та х₂, обрати в якості вільних, а інші зробити базисними і виразити їх через вільні. Припустимо, що це зроблено. Отже, маємо ОЗЛП:

 

(5.1)

 

Дамо задачі лінійного програмування геометричну інтерпритацію:

По віссям ОХ₁ та ОХ₂ бкдемо відкладувати значення вільних змінних х₁ та х₂. Візьмемо перше рівняння:

х₃ = a₃₁х₁ + a₃₂х₂ +b₃ ³ 0

і припустимо, що х₃ = 0. Тоді a₃₁х₁ + a₃₂х₂ +b₃ = 0. Розвязуємо це рівняння і отримуємо рівняння кривої. Візьмемо цю криву х₃ і відмітимо рисками ту сторону, де х₃ > 0.

Наступні криві будуємо аналогічно наведеному принципу.

В результаті ми отримали (m – 2) прямих, кожна з яких визначає припустиму півплощину.

Частину площини Х₁ОХ₂, яка належить одночасно всім цим півплощинам, утворює ОПР (область припустимих розвязків).

Не важко переконатися, що ОПР утворює завжди опуклий многокутник.

 

Визначення:

Множина точок n – вимірного євклідового простору називається опуклим, якщо разом з будь – якими двома точками цього простору воно містить також відрізок, з цими точками на кінцях.

Лекція №3

 

Задача.

Знайти з числа припустимих оптимальний розвязок, тобто таке яке перетворює в мінімум ЦФ

L = c₁x₁ + c₂x₂ + … + c_nx_n (5.2).

Підставимо вираз (5.1) в формулу (5.2) і виразимо L як ЦФ лише вільних змінних х₁ та х₂. Отримаємо

L = g₀ + g₁x₁ + g₂x₂ (5.3).

Як бачимо, рівняння (5.3) досягає мінімума при тих самих х₁ та х₂, що і функція

L¢ = g₁x₁ + g₂x₂ (5.4).

Знайдемо ці значення. Нехай L¢ = с, тоді отримаємо рівняння прямої на площині Х₁ОХ₂. Кутовий коефіцієнт цієї прямої дорівнює (g₁ / g₂), а відрізок, відрізаємий від віссі ОХ₂ буде дорівнювати.

Нехай маємо ОПР і пряму L¢ = 0. При переміщенні L¢ = 0 лінійна форма L* буде спадати. Отже, найменше значення вона досягне в точці А. Нехай х*₁ та х*₂ визначають оптимальний розвязок ЗЛП. Можна підставити їх в (5.1), знайти значення базисних змінних х*₃, х*₄, …, х*_n, а також значення функції

Lmin = g₀ + g₁x*₁ + g₂x*₂.

Основні властивості ЗЛП.

1. Розвязок ОЗЛП, якщо воно існує, не може лежати внутри, а лише на її кордонах.

2. Розвязок ОЗЛП може бути не єдиним.

3. ОЗЛП може не мати навіть в випадку, коли ОПР не обмежена.

4. Розвязок ОЗЛП, мінімізуючий функцію L завжди досягається в одній з вершин многокутника припустимих розвязків. Розвязки,які лежать в одній з вершин ОПР, називається опорним, а сама вершина – опорною точкою.

5. Для того, щоб знайти оптимальний розвязок, достатньо перебрати всі вершини ОПР і обрати з них ту, де L досягає мінімума.

6. Необхідною і достатньою умовою існування розвязку ЗЛП є обмеженість ЦФ на припустимій множині.

 

 

Симплекс – метод розвязку ЗЛП.

Алгоритм симплекс – методу:

1. Нехай відома деяка вершина допустимої множини.

2. Первіряємо належність цієї вершини до оптимального розвязку. Якщо так, то задача розвязана, інакше – переходимо до пункта 3.

3. Знаходиться вершина за визначеним правилом, яка краще попередньої. Переходимо до п. 2.

Так як число вершин обмежено, то через кінцеве число кроків знаходимо оптимальне рішення.

Симплекс – метод завжди застосовується в ЗЛП канонічної форми.

Зробимо припущення:

1. Система обмежень сумісна.

2. Ранг системи дорівнює кількості рівняннь.

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

(1)

В такому випадку задачу можна поставити так: знайти розташування вектора b за векторами А1, А2, …, Аn з невідємним коефіцієнтом, щоб ЦФ досягла максимуму.

Визначення: допустимий розвязок задачі (1) будемо називати опорниим, якщо вектори Аj, які відповідають додатнім його координатам, лінійно незалежні.

Нульовий опорний вектор будемо вважати опорним.

Базисом порного розвязку називається будь – який набір з m лінійно незалежних векторів Аj.

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

Визначення: опорний розвязок називається невиродженим, якщо він рішення містить точно m додатніх координат, інакше, розвязок – вироджений.

Теорема про звязок між вершинами і опорними розвязками: вектор тоді і лише тоді є опорним розвязком ЗЛП, коли точка (вектор) є вершиною її допустимого многокутника.

 

Основна лема симплекс – методу.

Нехай маємо m – вимірні вектори А1, А2, …, Аl, l ³ m. Ранг цієї системи дорівнює їх розмірності m і нехай вектор А_i1, А_i2, …, А_im складає базис системи векторів А₁, А₂, …, А_m.

Замінимо один з базисних векторів А_ік вектором А_s. Тоді нова система векторів буде знову базисом тоді і лише тоді, коли в розкладі

A_s = x_1sA_i1 + x_2sA_i2 + …+ x_ksA_ik + …+ x_msA_im, x_ks ¹ 0 (6.1).

 

 

Лекція № 4

Доведення.

Необхідність:

Нехай вектори з рівності (6.1) А_i1, А_i2, …, А_im знову базис і нехай вектори x_ks = 0 (доведення від противного). Тоді рівність (6.1) означає, що ці вектори лінійно незалежні. Маємо протиріччя.

Достатність:

Нехай дано x_ks ¹ 0. Доведемо, що вектори А_i1, А_i2, …, А_im лінійно незалежні.

Припустимо, що вони лінійно залежні, тобто a₁А_i1+a₂А_i2+…+a_mА_im= 0, де не всі a_і дорівнюють нулю. Тоді, a_к¹0, інакше б вектори А_i1, А_i2, …, А_im були б лінійно залежні. Виразимо звідси А_s:

(6.2).

Тоді для вектора А_s маємо два розкладення (6.1) та (6.2), причому в (6.1) коефіцієнт при А_ік не дорівнює 0, а в іншому – дорівнює. Отримали протиріччя. Лема доведена.

 

Основні формули симплекс – методу.

Нехай маємо систему векторів А1, А2, …, Аl і нехай вектори А_i1, А_i2, …, А_im складають базис.

Задача: які коефіцієнти А_s будуть в новому базисі.

З відношення (6.1) отримаємо

(6.3).

Таким чином, для вектора, який виводиться, отримаємо координати

(6.4).

Розглянемо координати довільного вектора Aj з розкладенням

A_j = x_1jA_i1 + x_2jA_i2 + …+ x_rjA_ir + …+ x_mjA_im (6.5).

Підставимо в (6.5) для Air його вираз з (6.3) і отримаємо:

(6.6).

Отже, коефіцієнти нового базиса:

(6.7)

Звідси маємо, що система (6.7) – основна формула симплекс – методу, де

x_kj – стара координата,

x¢_kj – нова координата,

x_ks – координата вводимого вектора,

x_rs – ведучий елемент.

 

Записуємо отримані дані в вигляді таблиці.

 

	А1	А2	…	Аs	…	An
Ai1	X11	^X12	^…	^X1s	^…	^X1n
…
Air	Xr1	^Xr2	^…	^Xrs	^…	^Xrn
…
Aim	Xm1	^Xm2	^…	^Xms	^…	^Xmn

 

Виділимо x_rs – ведучий елемент. Тоді As – ведучій стовпчик, а Air – ведуча стрічка. Нові елементи вираховуються за правилом хрест – на – хрест:

.

Основна теорема симплекс – методу.

Нехай дана канонічна невироджена ЗЛП з слідуючою правою частиною:

.

Нехай дано опорний розвязок цієї задачі:

`х = (`х₁, `х<sub>2</sub>, …, `х_m, 0,…, 0)

і нехай А1, А2, …, Аm – базис цього розвязку.

Тоді ЦФ буде дорівнювати

f(`х) = c<sub>1</sub>`х₁+ c₂`х<sub>2</sub>+ …+ c<sub>m</sub>`х_m.

Розклад за базисом:

А0= А₁`х<sub>1</sub>+ А<sub>2</sub>`х₂+ …+ А_m`х_m.

Нехай ми вирішили вектор Аs внести до базису, а Аr – вивести. Тоді:

1. Xrs ¹ 0 (за лемою);

2. Новий розвязок повинен бути допустимим.

 

Лекція №5

 

Знайдемо за основними формулами координати нового опорного розвязку в новому базисі А1, А2, …, Аm. Нехай

х_к0 (к = `1, `m) – координати А0 в старому базисі,

х¢_к0 (к = `1, `m) - координати А0 в новому базисі.

(7.1).

Для того, щоб новий розвязок був допустимим, необхідно щоби х¢_к > 0, х_r0 >0 Þ х_rs > 0.

Для відємних х_ks в формулі умова х¢_к > 0 виконується автоматично. Якщо х¢_к > 0, то

(7.2).

Для того, щоб новий розвязок був допустимим і опорним необхідне виконання двох умов:

1. х_rs > 0,

2. .

Обираємо r, s таким чином, щоб при виконанні умов (1) і (2) новий опорний розвязок був би кращим ніж попередній.

Запишемо новий опорний розвязок:

.

Якщо s таке, що z_s – c_s = ∆s < 0, то z¢_s > z_s, де ∆s – оцінка відповідного вектора.

 

Теорема 1 (про можливість отримання опорного розвязку).

Якщо даний опорний розвязок такий, що серед оцінок ∆s є відємні і така, що серед х_rs є х_rs > 0, то ми отримаємо найкраще опорний розвязок, або замінимо вектором As такий вектор Air старого базису, для якого .

Домовимось, що дані, повязані з опорним розвязком, зводити до таблиці.

Повна симплекс – таблиця.

№ п/п	Базис	Cj		C1	…	Cs	…	Cn
A0	A1	…	As	…	An
	Ai1	Ci1	X10	X11		X1s		X1n
	Ai2	Ci2	X20	X21		X2s		X2n
…	…	…	…	…		…		…
m	Aim	Cim	Xm0	Xm1		Xms		Xmn
				∆1		∆s		∆n
			Zj-Cj

 

В стовпчику А0 знаходяться значення невідомих даного опорного розвязку (m невідомих), інші – дорівнюють 0.

 

Теорема 2 (про умови оптимального опорного розвязку).

Якщо для даного опорного розвязку всі оцінки ∆j ³ 0, то ций опорний розвязок - оптимальний.

 

Теорема 3 (про признак необмеженості ЦФ).

Якщо для даного опорного розвязку існувала хоча б одна така відємна оцінка ∆s<0, для який всі Xks £0, то це означає, що ЦФ даної ЗЛП не обмежена зверху на допустимій множині.

 

Висновки: таким чином, в невиродженій задачі для будь – якого даного опорного розвязку виконуються або умови теореми 1, або теореми 2, або 3. Якщо конкретно виконуються умови теореми 2, чи 3, то задача розвязана. Якщо має місце умова теореми 1, то переходимо до кращого опорного розвязку. Для нього знову виконується теореми 1, 2, чи 3. Кількість різноманітних базисів обмежена. Базиси не можуть повторюватись. Таким чином, якщо задача не вироджена, то через обмежену кількість переходів (ітерацій) до кращого розвязку процес закінчиться.

 

Лекція № 6

Алгоритм симплекс – методу для невиродженої задачі.

Дана канонічна ЗЛП:

.

Відомий опорний розвязок `х = (`х₁, `х<sub>2</sub>, …, `х_n) і його базис А_i1, А_i2, …, А_im. Для розвязку задачі необхідно розкласти за початковим базисом вектора А₁, А₂, …, А_n.

Примітка: числа Хіо відомі.

Базисні вектори розкладаються за формулою:

, де

В = (А_і1, …, А_ім).

Для кожного j обчислюються оцінки

.

Оцінки базисних векторів завжди дорівнюють 0. Якщо всі Dj³0, то процес зупиняється. Відповідно до теореми 1, розвязок оптимальний при відємному Dj. Визначаємо присутність в такому стовпчику всіх відємних Xkj. Якщо така оцінка існує, то процес завершується.

В іншому випадку, обираємо одну з відємних Dj, як правило мінімальну, і називаємо її DS. Розраховуємо відношення q_к, яке дорівнює

для Ñ x_ks > 0.

Обираємо найменшу з них.

Здійснюємо перехід до нового опорного розвязку, базис якого утворюється заміною вектора Air вектором As. Для цього обчислюємо координати всіх векторів А₁, А₂, …, А_n за основними формулами

.

Блок – схема алгоритму.

1. Обчислення x_kj та Dj для початкового опорного розвязку.

2. Чи є Dj<0? (ні– (3А), так – (3Б))

3. А) Кінець: даний опорний розвязок – оптимальний.

Б) Чи є такі Dj<0, що всі x_kj<0? (так – (4А), ні – (4Б))

4. А) Кінець: задача не має розвязків.

Б) Вибір вводимого в базис і виводимого вектора, тобто s i r.

5. Розрахунок нових значень x_kj та Dj за основними формулами.

Примітка:

Теореми (2) і (3) підходять і для виродженого випадку, але там qmin=0. Через це, оцінки q розраховуються іншим способом: відповідні значенням нульові координати x_rs роблять ненульовими.

 

 

Пошук початкового опорного розвязку.

Простіше за все починати симплекс процес з одиничного базису. Існують спеціальні прийоми, які дозволяють звести задачу до задачі з повним одиничним базисом. Але це повязано з введенням додаткових змінних:

1) розвязок додаткової задачі;

2) метод штучного базису М.

Нехай маємо канонічну ЗЛП і нехай невідомий її опорний розвязок.

Змінимо її наступним чином:

 

де xj ³ 0, j=`1,`m;

x _n+1, …, x _n+m – штучні змінні, а вектори А _n+1, …, А _n+m утворюють штучний одиничний базис;

М – деяке додатнє досить велике число (вводиться для того, щоб штучні вектори вивести з базису за допомогою оцінок Dj).

Ця задача називається М – задачею. Вона має явнеий опорний розвязок з одиничним базисом і до неї можна застосувати симплес метод.

Припустимо, що ми розвязали М – задачу. Можливі випадки:

1. М – задача має розвязок.

Нехай х*₀ - її оптимальний розвязок

x*₀ = (х₁⁰, х₂⁰, …, х_n⁰, x _n+1⁰, …, x _n+m⁰),

тоді розглянемо варіант

a) x _n+1⁰ = …= x _n+m⁰ =0, тобто всі штучні змінні рівні. Доведемо, що вектор х*₀ – оптимальний розвязок рівняння початкової задачі.

Припустимо, що це не так і що вектор `х = (`х₁, `х<sub>2</sub>, …,`х_n) надає значення ЦФ більше, тобто (с,`х<sub>1</sub>)> (с, х*<sub>0</sub>). Звісно, що `х = (`х<sub>1</sub>, `х₂, …,`х_n, 0, …, 0) припустимий розвязок М – задачі

(`с,`х) = (с, `х) > (c, х*<sub>0</sub>) = (`c, х*₀),

так як x _n+1⁰, …, x _n+m⁰=0.

Отримана нерівність протирвічить тому, що вектор x*₀ буде оптимальним розвязком М – задачі. Звідси x*₀ буде оптимальним розвязком початкової задачі.

б) Серед x _n+1⁰, …, x _n+m⁰ є не нульові. Доведемо, що у цьому випадку початкова задача недопустима.

Нехай це не так і вектор `х = (`х₁, `х<sub>2</sub>, …,`х_n) – певне допустимий розвязок початкової задачі.

Розглянемо вектор `х = (`х₁, `х<sub>2</sub>, …,`х_n, 0, …, 0) – допустимий розвязок М – задачі і побудуємо для нього ланцюг

(`с,`х) = (с, `х) > (`c, х*₀) = (c, х*₀) - МS x _n+і⁰ > 0

М – як завгодно велике число, тобто маємо протиріччя, що вектор х*₀ – оптимальний розвязок.

М – задача не має розвязку, тобто ЦФ не обмежене зверху.

У цьому випадку можна довести, що початкова задача, або недопустима, або має не обмежену ЦФ.

 

Розвязок М – задачі при невизначеному достатньо великому М.

В М – задачі на кожній іттерації від М залежить лише оцінки Dj (Dj' М + Dj").

Так як М достатньо велике, то знак Dj співпадає зі знаком при Dj'. Звідси, не знаючи конкретного значення М ми знаємо знаки всіх оцінок Dj і можемо (різними способами) будувати симплекс – процес.

Лекція №7

Примітка:

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

2. Якщо при розвязку М – задачи будьякий штучний вектор вийшов з базису, то недоцідьно цей вектор в подальшому знову вводити в базис. Через це відповідний стовпчик в таблиці можна опустити.

 

Модифікований симплекс-метод.

В симплекс-методі істотну роль на кожній іттерації грають оцінки

 

В результаті для оцінок D будемо мати

Dj = с_баз В^-1 А_j - c_j , де

В – базисна матриця, B = (A_i1, A_i2, …, A_im).

Будемо тепер Dj обчислюємо в такій послідовності:

L = с_баз В^-1.

Нехай L = (λ₁, λ₂, …, λ_m). Ці числа λі називаються симплекс – множниками для данного опорного розвязку.

Припустимо, що ми знайшли всі оцінки Dj. Припустимо, що В^-1 – відомо. Якщо, всі Dj ³0, то процес скінчено і розвязок – оптимальний; якщо є Dj <, то беремо з них мінімальну, нехай це буде Ds. І лише для цієї оцінки знаходимо x_ks

 

Якщо всі x_ks £ 0, то процес закінчується. (ЦФ – не обмежена).

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

Знайшли новий базис. Якщо для нього вважаємо відому матрицю В^-1, то повторюємо ці міркування.

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

Таким чяином не потрібно обчислювати x_kj для всіх a_j, але для кожного опорного розвязку необхідно знати В^-1

Розрахунок оберненої матриці для достатньо великої матриці досить складно.

Можно обійтися без безпосереднього розвязку оберненої матриці на кожній операцій, а саме елементи зворотньої матриці для кожного опорного розвяку можно розрахувати за оберненою матрицію попереднього розвязку за основними формулами.

Лекція 8

Для того, щоб впевнитись в цьому покажемо, що стовпці зворотньої матриці для данного базиса – це стовпці координат векторів Е₁, Е₂, …, Е_м у відповідному базисі

 

Нехай Аі1, Аі2, …, Аім – це черговий базис і утворена матриця для даного базису дорівнює

 

 

Знайти координати вектора Еj в нашому базисі:

 

 

Так як j – довільна, то це ми довели для будьякого вектора матерь божья e₁, e₂, …, e_m

Таким чином приходимо до слідуючої матриці симплекс-методу.

 

2 алгоритм симплекс-методу.

1. Oбчислюємо матрицю зворотню до данної базисної матриці.

2. Oбчислюємо вектор L = с_баз В^-1.

3. Oбчислюємо оцінки Dj

Dj = LAj-Cj.

Для базисних векторів вони дорівнюють 0. Якщо всі Dj ³ 0, то опорний розвязок - оптимальний. Якщо є Dj < 0, то обираємо з них найменшу. Припустемо. Що Ds обрана.

4. Oбчислюємо x_ks за формулою

Якщо всі x_ks £ 0 і Ds < 0, то процес зупиняється (ЦФ – необмежена звеху), в іншому випадку переходимо до 5.

5. Oбчислюємо

6. За основними формулами обчислюємо новий опорний розвязок

і матрицю, обернену до нової базисної

Поветаємося до 2, маючи на увазі новий опорний розвязок.

Примітка: недоліком 2 алгоритму в порівнянні з 1 є те, що необмеженість ЦФ (вона може зявитися на більш пізній іттерації при 1 алгоритмі).

 

Для А₀ - аналогічно.

Починаємо перелік за правилом критий -накритий.

Отримуємо першу ітерацію.

Nп/п	Баз.	С баз.	А0	Е1	Е2	Е3	А3 ¯	Q
	A1		7/4	3/8	1/4		-1	7/8
	A4		¼	1/8	-1/4			-11/8
	A7		¾	-13/8	-3/4			7/8
			4/W				-4

 

Друга ітерація.

 

Nп/п	Баз.	С баз.	А0	Е1	Е2	Е3	А5
	A1					-1
	A4		10/7	-17/7	-10/7	11/7	-17/7
	A3		6/7	-13/7	6/7	8/7	-13/7
			52/7	-45/7	-24/7	32/7	-45/7

 

Третя ітерація.

 

Nп/п	Баз.	С баз.	А0	Е1	Е2	Е3
	A5		1/2		1/2	-1/2
	A4		37/14		-3/14	5/14
	A3		25/14		1/14	3/14
			119/14		-3/14	19/14

 

 

ПРИКЛАД

Побудувати двоїсту задачу до наступної.

Чи в матричному вигляді:

Майже допустиме рішення будемо називати майже допустимим опорним рішенням (м.д.о.р.), якщо вектори а_ij відповідні до його ненульових координат лінійно - незалежні.

Базисом м.д.о.р. будемо називати будь-який упорядочений набір із m лінійно - незалежних векторів А_j серд яких знаходяться всі вектори А_j,відповідні до всіх ненульових координат даного м.д.о.р.

В основі алгоритму двоїстого симплекс методу лежать 3 теореми:

Будемо розглядати тільки такі м.д.о.р. для котрих оцінки векторів А_j невід'ємна, тобто

де i_1, i_2, i₃…i_m - номери базисних векторів м.д.о.р. (це відповідає тому, що вектор С_баз В^-1 є допустимим рішенням двоїстої задачі.)

 

СИМЕТРИЧНІ ДВОЇСТІ ЗАДАЧІ.

Задача ІІ

Двоїста для неї форма:

 

Отже для задачі ІІ двоїста задача ІІ^":

 

Задачі ІІ і ІІ^" складають симетричну пару двоїстих задач.

Лемма та обидві теореми двоїстості є вірними і для симетричних задач, але при цьому запис другої теореми дещо змінюється. А саме, нехай дано дві задачі ІІ і ІІ^" `х допустиме рішення ІІ, `y - задачі ІІ^" .

`x,`y - тоді і тільки тоді будуть оптимальним рішенням, коли виконуються дві групи умов:

 

ДВОЇСТИЙ СИМПЛЕКС - МЕТОД.

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

На відміну від симплекс методу тут послідовні вектори не мають бути допустимі, але як тільки отримуємо допустимі - вони же і оптимальні.

Виявляється, що для задачі І^” (якщо її привести до еквівалентної канонічної форми) двоїстою буде задача, еквівалентна до задачі І.

Розв’язок задачі:

В задачі на мінімум все так само, але z ' =z-Θ∆j

∆j - вибираємо максимум із додатних, тоді значення ц. ф. зменшиться. Таким чином задача І і І^” складають з точністю до еквівалентності пару взаємо двоїстих задач (несиметричну пару). В матричному вигляді:

Від задачі І^/ перейшли до задачі І.

Лемма.

Нехай - будь-який допустимий розв’язок задачі І, а - будь-яке. Тоді виконується нерівність (с, )≤ (b, ) при любому допустимому розв’язку.

Якщо для будь-яких , виконується (с, )= (b, ), то ,