Контрольная работа на тему: «Линейное программирование».

Задача.Решить симплекс-методом задачу линейного программирования. Результат представить в виде последовательности симплекс-таблиц. Показать построение начального решения и вычисления при переходе от начальной таблицы к первой. Выписать оптимальное решение (значения критерия и всех переменных).

Решить также задачу графически. Сравнить результаты решений.

Вариант № 3.

L= –x₁–x₂→min2x₁+ 3x₂≥ 6 4x₁+ 2x₂≤ 40 –3x₁+ 5x₂≤ 30x₁,x₂≥ 0

Решение:

Приведём систему уравнений к каноническому виду.

L+x₁+x₂→min–2x₁– 3x₂≤ –6 4x₁+ 2x₂≤ 40 –3x₁+ 5x₂≤ 30x₁,x₂≥ 0

L+x₁+x₂= 0 –2x₁– 3x₂+x₃= –6 4x₁+ 2x₂+x₄= 40 –3x₁+ 5x₂+x₅= 30x₁,x₂≥ 0

Из данных задачи составляем исходную симплекс таблицу.

L	x1	x2	x3	x4	x5	Решение	Базис	Отношение
0	-2	-3	1	0	0	-6	x3	3
0	4	2	0	1	0	40	x4	10
0	-3	5	0	0	1	30	x5	-10
1	1	1	0	0	0	0	L

Так как ищем минимальное значение функции, ведущим столбцом будет максимальное положительное число в последней строке. Это столбцы x₁иx₂. Пусть ведущим столбцом будетx₁. Ведущей строкой будет первая строка, т.к. её отношение является минимальным положительным числом.

Умножаем первую строку на -1/2. После симплекс-преобразования получаем новую таблицу.

L	x1	x2	x3	x4	x5	Решение	Базис	Отношение
0	1	3/2	-1/2	0	0	3	x1	-6
0	0	-4	2	1	0	28	x4	14
0	0	19/2	-3/2	0	1	39	x5	-26
1	0	-1/2	1/2	0	0	-3	L

Здесь ведущий столбец x₃, ведомая строкаx₄. После симплекс-преобразования получаем новую таблицу.

L	x1	x2	x3	x4	x5	Решение	Базис	Отношение
0	1	1/2	0	½	0	10	x1	20
0	0	-2	1	½	0	14	x3	-7
0	0	13/2	0	¾	1	60	x5	120/13
1	0	1/2	0	-1/2	0	-10	L

Здесь ведущий столбец x₂, ведомая строкаx₅. Получаем новую таблицу.

L	x1	x2	x3	x4	x5	Решение	Базис
0	1	0	0	-23/52	-1/13	70/13	x1
0	0	0	1	19/26	4/13	432/13	x3
0	0	1	0	3/26	2/13	120/13	x2
1	0	0	0	-29/52	-1/13	-190/13	L

Ответ.Оптимальное значение:x₁= 70/13,x₂= 120/13.

Решение графическим способом:

1. 2x₁+ 3x₂≥ 6

2. 4x₁+ 2x₂≤ 40

3. –3x₁+ 5x₂≤ 30

Контрольная работа на тему: «Транспортные задачи»

Задача.Следующую Т-задачу решить методом потенциалов. Начальный план строить по правилу северо-западного угла.

Вариант № 9.

bj ai	2	3	3	16
68	18	2	9	7
55	30	4	1	55
40	6	4	8	3

Решение:

Т-задача должна быть сбалансирована. Т.к. она у нас не сбалансирована, то добавляется фиктивный потребитель с нулевыми затратами и количеством груза, равным дисбалансу.

																											Потреб.
		bi	I					II					III					IV					V
	ai																					фиктив.
			2					3					3					16					44								68
I
						18					2					9					7					0
																							55						55
II
						30					4					1					55					0
																							40						40
III
						6					4					8					3					0
Постав.				2					3					3					16					139						163
	- стоимость

Заполняем таблицу по правилу северо-западного угла и вычисляем потенциалы.

																														Потр.				V
		bi	I					II						III						IV					V
	ai																							фиктив.
			2					3						3						16					44						68				0
I
					18						2						9						7					0
																									55						55				0
II
			18		30		2				4		9				1		7				55					0
																									40						40				0
III
			18		6		2				4		9				8		7				3					0
Постав.			2					3						3						16					139						163
U			18					2						9						7					0
	- стоимость
	-потенциал

Так как есть клетки, где потенциал больше затрат, то данный план не является оптимальным. Создаём цикл пересчёта.

Пересчитываем потенциалы

																		Потреб.			V
		bi	I			II			III			IV			V
	ai														фиктив.
						3									65			68			0
I
			6		18			2	1		9	3		7			0
									3						52			55			0
II
			6		30	2		4			1	3		55			0
			2									16			22			40			0
III
					6	2		4	1		8			3			0
Постав.			2			3			3			16			139			163
U			6			2			1			3			0

Данное решение является оптимальным.