Розв'язок задачі лінійного програмування (стр. 4 из 4)

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

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани

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

.

Більш очевидно взаємозв’язок між оптимальними планами прямої та двоїстої задач встановлює наслідок другої теореми двоїстості.

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

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

Побудуємо двоїсту:

Побудуємо симплекс таблиці для прямої задачі:

1	3	0	0	0
x1	x2	x3	x4	x5	B	T
x3	4	3	1	0	0	12	4
x4	-1	2	0	1	0	4	2	**
x5	2	-1	0	0	1	4	###
F	-1	-3	0	0	0	0	0
**
1	3	0	0	0
x1	x2	x3	x4	x5	B	T
x3	5,5	0	1	-1,5	0	6	1,09	**
x2	-0,5	1	0	0,5	0	2	###
x5	1,5	0	0	0,5	1	6	4
F	-2,5	0	0	1,5	0	6	0
**
1	3	0	0	0
x1	x2	x3	x4	x5	B	T
x1	1	0	0,18	-0,27	0	1,09	1,09
x2	0	1	0,09	0,36	0	2,55	###
x5	0	0	-0,27	0,91	1	4,36	4
F	0	0	0,45	0,82	0	8,73	0

Отже, максимум F дорівнює 8,73 в точці (1,09, 2,55).

Тоді мінімум К(у) дорівнює також 8,73. у* = (0, 2,33, 1,67)Т.

Задача 4

Методом потенціалів розв’язати ТЗ.

Розв’язання:

Q1	Q2	Q3	Q4	Q5	a
P1	7	3	1	5	4	30
P2	7	5	8	3	2	25
P3	6	4	8	3	2	45
P4	3	1	7	6	2	20
b	10	35	15	25	35

10 +35+15+25+35 = 120

30+ 25+ 45+ 20 = 120.

Отже, ТЗ є закритою.

Знайдемо початковий план методом пн-зх кута.

Q1		Q2		Q3		Q4		Q5		a
P1	7	3	1	5	4	5
	10	20
P2	7	5	8	2	2	25
	15	10
P3	6	4	8	2	2	10
	5	25	15
P4	3	1	7	2	2	20
	20
b	10		10		15		25		10

Поетапно проведемо методом потенціалів розв’язок задачі:

Q1		Q2		Q3		Q4		Q5		u
P1	7	3	-	1	+	5	4	4
	10	20	-5	5	4
P2	7	5	+	8	-	2	2	6
	-2	15	10	0	0
P3	6	4	8	2	2	6
	-3	-1	5	25	15
P4	3	1	7	2	2
	0	2	5	6	20
v	3		-1		2		-4		-4
Q1		Q2		Q3		Q4		Q5		u
P1	7	-	3	1	+	5	4	4
	10	10	10	10	9
P2	7	5	8	2	2	6
	-2	25	5	5	5
P3	6	4	8	-	2	2	+	11
	-8	-6	5	25	15
P4	3	+	1	7	2	2	-	11
	-11	-9	-1	0	20
v	3		-1		-3		-9		-9
Q1		Q2		Q3		Q4		Q5		u
P1	7	3	1	5	4	5
	5	10	15	7	7
P2	7	5	8	2	2	7
	2	25	7	7	7
P3	6	4	8	2	2	1
	7	7	7	25	20
P4	3	1	7	2	2	1
	5	7	7	7	15
v	2		-2		-4		1		1

Всі оцінки Сij – vi – uj на 3 етапі невід’ємні, тому оптимальний розв’язок знайдено.

5	10	15	0	0
X =	0	25	0	0	0
	0	0	0	25	20
5	0	0	0	15

Вартість перевезень дорівнює: 7 * 5 + 3 * 10 + 1 * 15 + 5 * 25 + 3 * 5 + 2 * 25 + 2 * 20 + 2 * 15 = 340.

Список використаних джерел

1. Бурий В.В., Шевченко І.В. Математичне програмування. — К.: НАУ, 2007. — 168с.

2. Єгоршин О.О., Малярець Л.М. Математичне програмування. — Х.: ВД "ІНЖЕК", 2006. — 383с.

3. Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). — К.: МАУП, 2006. — 184с.

4. Зеленський К.Х. Математичне програмування. — К.: Університет "Україна", 2007. — 241c.

5. Лебідь М.Т., Синявіна ЮВ. Математичне програмування. — Х., 2007. — 72с.