Решение задач 1 страница. Если на первом этапе решение ВЗ закончилось случаем 1 или 2, то можно перейти ко второму этапу – решению исходной задачи

ВТОРОЙ ЭТАП – РЕШЕНИЕ ИСХОДНОЙ ЗАДАЧИ

Если на первом этапе решение ВЗ закончилось случаем 1 или 2, то можно перейти ко второму этапу – решению исходной задачи.

(3.81)

(3.82)

, (3.83)

так как расширенная матрица системы линейных уравнений (3.82) является К-матрицей.

Вернемся к решению задачи из примера в начале темы. Для задачи (3.51)–(3.53) запишем ВЗ:

-(U₁+U₂+U₃) max (3.84)

2X₁ + 2X₃ + 4X₄ + X₅ + U₁ = 150

X₁ + X₂ + 2X₅ + U₂ = 200 (3.85)

X₁ + X₃ + 2X₆ + U₃ = 300

X_j ≥ 0; U_i ≥ 0; j = ; I = . (3.86)

Результаты первого этапа представлены в табл. 3.5.

Таблица 3.5

											-1	-1	-1
S	i
			-1												37,5
			-1												-
			-1												-
				-650	-2	-3	-3	-4	-3	-2
				37,5		0,5	0,5		0,25		0,25			-		-
			-1													-
			-1												-
				-500	-2	-1	-1		-2	-2
				37,5		0,5	0,5		0,25		0,25				-
															-
			-1			-1			-2			-1
				-100			-1			-2
				37,5		0,5	0,5		0,25		0,25
						-0,5	0,5		-1			-0,5	0,5

На третьей итерации симплексного метода получен оптимальный план вспомогательной задачи: = (200; 0; 0; 37.5; 0; 50; 0; 0; 0), в котором ни одна из искусственных переменных не является базисной, следовательно, вектор = (200; 0; 0; 37.5; 0; 50) является невырожденным опорным планом исходной задачи, определяемым К-матрицей.

На втором этапе решаем задачу

max (–0,4X₁–0,3X₂–0,1X₃–0,1X₅–0,2X₆)

.

Решение приведено в табл. 3.6.

Таблица 3.6

					-0.4	-0.3	-0.1		-0.1	-0.2
S	i
				37,5		0,5	0,5		0,25
			-0,4
			-0,2			-0,5	0,5		-1		-
				-90					-0,5

Окончание табл. 3.6

				12,5	-0,125	0,375	0,5
			-0,1		0,5	0,5					-
			-0,2
				-40	0,25	0,25
			-0,1		-0,25	0,75
			-0,1		0,5
			-0,2	137,5	0,625	-0,375		-1
				-100	0,25	0,25

На первой итерации (табл. 3.6) второго этапа получен оптимальный план исходной задачи ₁ = (0; 0; 12.5; 100; 150) и = 40.

Так как = 0, а вектор не является базисным, то его можно ввести в базис, и при этом в соответствии с формулой (3.28) значение целевой функции не изменится, т.е. на второй итерации можно получить еще один оптимальный план исходной задачи

₂ = (0; 0,25; 0; 100; 137,5) и = 40.

Исходная задача имеет бесчисленное множество решений, задаваемое формулой

(3.87)

Пример 3.15. Решить ЗЛП:

max (2X₁ – X₂ – X₄)

X₁ – 2X₂ + X₃ = 10

–2X₁ – X₂ – 2X₄ 18 (3.88)

3X₁ + 2X₂ + X₄ 36

Приведем ЗЛП (3.88) к каноническому виду

max (2X₁ – X₂ – X₄)

X₁ – 2X₂ + X₃ = 10

-2X₁ – X₂ – 2X₄ – S₁ =18 (3.89)

3X₁ + 2X₂ + X₄-S₂ = 36

Расширенная матрица системы линейных уравнений (3.89)

не является К-матрицей ЗЛП (3.89), т.к. не содержит единичной подматрицы.

Запишем вспомогательную задачу для ЗЛП (3.89). Т.к. матрица содержит один единичный вектор = (1; 0; 0), то при формулировке ВЗ достаточно ввести лишь две искусственные переменные U₁; U₂ во второе и третье уравнения системы (3.89).

Итак, ВЗ имеет вид

-(U₁+U₂) max

X₁ – 2X₂ + X₃ = 10

-2X₁ – X₂ – 2X₄ – X₅ + U₁ = 18 (3.90)

3X₁ + 2X₂ + X₄ – X₆ + U₂ = 36

; U₁,U₂ 0

Решение ВЗ приведено в табл. 3.7.

Таблица 3.7

											-1	-1
S	i
					-1	-2							-
			-1		-2	-1		-2	-1				-
			-1							-1
				-54	-1	-1
										-1
			-1		-0,5			-1,5	-1	-0,5		0,5
					1,5			0,5		-0,5		0,5
				-36	0,5			1,5		0,5		0,5

На первой итерации получен оптимальный план.

= (0; 18; 46; 0; 0; 36; 0).

Т.к. вектор имеет отличную от нуля искусственную переменную U₁ = 36, то множество планов ЗЛП (3.88) пусто в силу несовместности системы уравнений (3.89).

Контрольные вопросы

1. Запишите ЗЛП в форме ОЗЛП.

2. Запишите ЗЛП в форме ОснЗЛП.

3. Запишите ЗЛП в форме КЗЛП.

4. Приведите ОЗЛП к каноническому виду.

5. Приведите ОснЗЛП к каноническому виду.

6. Дайте определение плана КЗЛП.

7. Перечислите свойства множества планов Р.

8. Дайте определение оптимального плана КЗЛП.

9. Какая ЗЛП называется разрешимой?

10. Дайте определение выпуклого множества.

11. Дайте определение гиперплоскости.

12. Дайте определение полупространства.

13. Что называется крайней, или угловой, точкой множества Р?

14. Дайте определение градиента функции.

15. Запишите градиент функции ¦(x) = с₁x₁ + c₂x_2.

16. Что называется линией уровня целевой функции?

17. В каких случаях при решении ЗЛП графическим методом можно убедиться в ее неразрешимости?

18. Что означает разрешимость ЗЛП при графическом методе ее решения?

19. Запишите КЗЛП в алгебраической форме.

20. Запишите КЗЛП в векторно-матричной форме.

21. Дайте определение опорного плана КЗЛП.

22. Дайте определение К-матрицы КЗЛП.

23. Сформулируйте связь между опорным планом и К-матрицей.

24. Число опорных планов конечно или нет?

25. Какого числа не превышает количество опорных планов КЗЛП?

26. Сформулируйте связь между опорным планом и крайней точкой.

27. Сформулируйте утверждение о существовании оптимального опорного плана.

28. Дайте определение симплекс-разности.

29. Сформулируйте критерий оптимальности в алгоритме симплекс-метода.

30. Сформулируйте критерий отсутствия решений в алгоритме симплекс-метода.

31. Сформулируйте основные моменты, которые должен содержать любой конечный алгоритм решения ЗЛП.

32. Где в алгоритме симплекс-метода используется метод Гаусса?

33. Дайте определение Р-матрицы КЗЛП.

34. Дайте определение псевдоплана КЗЛП.

35. Сформулируйте критерий отсутствия решения в алгоритме Р-метода.

36. В каком случае к решению ЗЛП необходимо применять двухэтапный симплекс-метод?

37. Какие ЗЛП не могут быть решены симплекс-методом?

38. Из чего состоит отчет по результатам поиска решения MS Excel?

39. Из чего состоит отчет по устойчивости поиска решения MS Excel?

40. Из чего состоит отчет по пределам поиска решения MS Excel?

Задание №7

1. Решить графическим методом задачу №1 из темы 1.

Задание №8

2. Решить графическим методом задачу.

Из трех сортов бензина образуются две смеси. Первая состоит из А₁ % бензина первого сорта, В₁ % бензина 2-го сорта, С₁ % бензина 3-го сорта; вторая: А₂ % – 1-го, В₂ % – 2-го, С₂ % – 3-го сорта. Цена 1-й смеси – 305 у.е., второй – 200 у.е. за тонну. Сколько смеси первого и второго вида можно изготовить из “а” тонн 1-го сорта, “b” тонн 2-го сорта и “с” тонн 3-го сорта, чтобы получить максимальный доход?

№ задач	А1	В1	С1	А2	В2	С2	а	в	с
		- - - -	- -		-

Задание №9

Решить задачу графическим методом и провести анализ на чувствительность, ответив на вопросы 1–5.

Для приготовления двух видов продукции (A, B) используют три вида сырья. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице.

1. Определить план выпуска продукции из условия максимизации его стоимости.

2. Определить интервал изменения цены на продукцию А, при котором структура оптимального решения останется неизменной.

3. Определить интервал изменения цены на продукцию В, при котором структура оптимального решения останется неизменной.

4. Определить статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.

5. Определить максимальный интервал изменения запасов каждого из ресурсов, в пределах которого структура оптимального решения, то есть номенклатура выпускаемой продукции, остается без изменения.

1.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III		-
Цена ()	7,5

2.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III		-
Цена ()	7,5

3.

Сырье	Норма расходов	Ресурсы
A	B
I	4,5
II
III	-
Цена ()	10,5

4.

Сырье	Норма расходов	Ресурсы
A	B
I
II	1,5
III
Цена ()

5.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III		-
Цена ()

6.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III		-
Цена ()

7.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III		-
Цена ()

8.

Сырье	Норма расходов	Ресурсы
A	B
I
II
III	-
Цена ()

9.

Дата добавления: 2014-12-29