Розв’язування задач на мінімум цільової функції

Розглянемо задачу:

Z = C ∙ X " min

AX ≤ B

X ≥ 0

 

Позначимо F = - Z.

Тоді max F= -min Z, і можна розв’язувати задачу (3.1)-(3.3)

3. Розглянемо пари симетричних задач.

F = C ∙ X"max (3.1) Z = Y ∙ B " min (3.4) (3.4)

A ∙ X ≤ B (3.2) Y∙A ≥ C (3.5) (3.5)

X ≥ 0 (3.3) Y ≥ 0 (3.6) (3.6)

де

Кожна задача називається двоїстою стосовно іншої. Якщо вихідна задача (3.1)-(3.3) є задачею про оптимальний план випуску продукції, то двоїста (3.4)-(3.6) є задача про використання ресурсів.

y_i- ціна (оцінка) відповідного ресурсу, а Z=Y∙ В - вартість усіх ресурсів.

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

Двоїста задача: якою повинна бути ціна кожного з ресурсів, щоб за даних обсягів ресурсів і цінах на продукцію забезпечити мінімум усіх витрат.

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

Якщо цільова функція однієї з задач не обмежена, то й інша не має розв’язку.

Теорема справедлива і для пари несиметричних задач:

F = С ∙ X ® max Z = Y ∙ У ® min

А ∙ X = В Y ∙ A ³ C

X 0

Умова невід’ємності для другої задачі відсутня.

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

 

4. Приклад

Z = x₁ + 2x₂ + 3x₃ ®min

x_j ³ 0; j = 1,2,3.

 

Складемо і розв’яжемо двоїсту задачу.

F = 2y₁ + 3у₂ + 6у₃ + 3у₄ ® max

у_i ³ 0; i = 1,2,3,4

 

Уводимо додаткові змінні.

 

F = 2y₁ + 3у₂ + 6у₃ + 3у₄ +0×у₅+0×у₆+0×у₇® max

 

	Базис	Сбаз	В	А1	А2	А3	А4	А5	А6	А7
	А5 А6 А7			-1	-1	-2	-2
	Fj - Cj		-2	-3	-6 ­	-3
	А3				-1
	А6						-1	-1
	А7
	Fj - Cj			-9 ­
	А3		3/2				3/2	1/2	1/2
	А2		½				-1/2	-1/2	1/2
	А7								-1
	Fj - Cj	10,5				4,5	1,5	4,5

 

План не є оптимальним F (Y₀) = 0.

План не є оптимальним F (Y₁) = 6.

План оптимальний F (Y₂) = 10,5.

Одержали розв’язок двоїстої задачі.

; F_max = F (Y^*) = 10,5.

Для вихідної задачі Z_min = 10,5.

 

Оптимальний план вихідної задачі знаходимо у рядку оцінок останньої таблиці в стовпцях векторів, що входили в первісний базис: х_j = F_j.

х₁ = 1,5+0 = 1,5

х₂ = 4,5+0 = 4,5

х₃ = 0+0 = 0 Z_min = Z (X^*) = 10,5

Контрольні запитання

1. Як перетворити неканонічну ЗЛП у канонічну за допомогою додаткових змінних?

2. Яким є алгоритм розв’язування задач ЛП на мінімум цільової функції?

3. Що таке симетричні задачі ЛП?

4. Як виявляється двоїстість при розв’язуванні пари несиметричних задач ЛП?

 

Лекція 4

Цілочисельне програмування

1. Постановка задачі цілочисельного програмування (ЗЦП)
2. Метод Гоморі
3. Приклад розв’язування ЗЦП
4. Задача придбання устаткування

1.У багатьох реальних задачах на змінні величини накладаються додаткові умови: вони повинні бути цілими. Округлення результатів розв’язку, отриманого звичайним симплекс-методом може привести до результату, далекому від оптимального. Необхідний спеціальний метод, що враховує цілочисельність.

Розглянемо найпростішу задачу:

(4.1) (7.1)

i = 1, 2, 3...m (4.2)(7.2)

(4.3) (7.3)

цілі (4.4) (7.4)

Метод Гоморі

1. Вихідна задача вирішується симплекс-методом без умови (4.4); одержуємо деякий оптимальний план.

2. Якщо всі координати цього плану цілі – задача розв’язана.

3. Якщо ні – додаються додаткові обмеження.

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

 

Після розв’язування отримуємо оптимальний цілочисельний план або доводимо, що цілочисельного плану задача не має. Недоліки методу: вимога цілочисельності для всіх змінних задачі (як основних так і додаткових). Будемо вважати, що результатом пункту 1 розв’язування задачі (7.1)-(7.3) є такий план

Припустимо, що x_i - дробове число. Позначимо через [ x_i ] його цілу частину, через q_i=x_i-[x_i]={x_i} - його дробову частину. Розглянемо рядок i останньої симплекс-таблиці

 

 

Якщо в цьому рядку дробових елементів не має, то задача (4.1)-(4.4) не має розв’язків. Припустимо, що x_ij – дробові, j=m+1,…n...

Позначимо - дробові частини цих чисел. Уведемо додаткове обмеження

–q_im+1∙ x_m+1 - q_im+2∙ x_m+2-...-q_inx_n+q_i≤ 0 (4.5)

Додамо змінну x_m+1 і перетворимо (4.5) у рівність:

–q_im+1x_m+1-q_im+2x_m+2-…-q_inx_n+x_n+1=-q_i+1

Розв’яжемо отриману задачу двоїстим симплексом-методом.

3.Приклад

x_j>0, цілі, j=1,2,3.

 

Приведемо задачу до канонічного вигляду і розв’яжемо симплекс-методом без умови цілочисельності змінних

 

				-1
	Базиз	Сбаз	B	A1	A2	A3	A4	A5	A6
	А4				-1	1
	А5			-4		-1
	А6
	Fj – Cj			-1	-3
	A3				-1
	A5			-2	1
	A6				1		-1
	Fj – Cj			-4
	A3
	A2			-2
	A6			3			-2	-1
	Fj – Cj		-1
	A3
	A2		11/3				- 1/3	1/3	2/3
	A1	-1	1/3				- 2/3	- 1/3	1/3
	Fj – Cj	46/3				19/3	11/3	1/3

 

 

План не оптимальний

План не оптимальний

План не оптимальний

План оптимальний

; F^* = 46/3

Тому що х₁ =1/3 і х₂= 11/3 не цілі, необхідно доповнити задачу обмеженням. Будемо працювати з другим рядком q₂ =2/3; q₂₅ =1/3; q₂₆ =2/3

-2/3x₄-1/3x₅-2/3x₆+x₇=-2/3

- план умовно припустимий.

 

				-1
	Базиз	Сбаз	B	A1	A2	A3	A4	A5	A6	А7
	А3
	А2		11/3				-1/3	1/3	2/3
	А1	-1	1/3				-2/3	-1/3	1/3
	А7		-2/3"				-2/3	-1/3	-2/3
	Fj – Cj					19/3	11/3	1/3
	A3
	A2						-1
	A1	-1					-1	-1/2		1/2
	А6							1/2		-3/2
	Fj – Cj						3,5		0,5

 

Одержали цілочисельний план

F(Х₅)=15

Залишаючи вихідні змінні, одержуємо F(Х^*)=15

Тому що 15< , точка максимуму з умовою цілочисельності координат знаходиться усередині припустимої множини.