Задания (стр. 5 )

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 1*200 + 2*100 + 1*200 + 4*100 + 2*200 + 3*100 + 0*100 = 1700

	1	2	3	4	Запасы
1	5	1[200]	1	3	200
2	2[300]	4	5	1	300
3	6	2	4	9[100]	100
4	2	6	3[300]	7	300
5	0	0	0	0[100]	100
Потребности	300	200	300	200

2. Подсчитаем число занятых клеток таблицы, их 5, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным.

Строим новый план.

Значение целевой функции для этого опорного плана равно:

F(x) = 1*200 + 2*300 + 9*100 + 3*300 + 0*100 = 2600

	1	2	3	4	Запасы
1	5	1[100]	1[100]	3	200
2	2[100]	4	5	1[200]	300
3	6	2[100]	4	9	100
4	2[200]	6	3[100]	7	300
5	0	0	0[100]	0	100
Потребности	300	200	300	200

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

2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F(x) = 1*100 + 1*100 + 2*100 + 1*200 + 2*100 + 2*200 + 3*100 + 0*100 = 1500

4. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

	v1=0	v2=1	v3=1	v4=-1
u1=0	5	1[100]	1[100]	3
u2=2	2[100]	4	5	1[200]
u3=1	6	2[100]	4	9
u4=2	2[200]	6	3[100]	7
u5=-1	0	0	0[100]	0

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 1*100 + 1*100 + 2*100 + 1*200 + 2*100 + 2*200 + 3*100 + 0*100 = 1500

2 вариант

1. Найти оптимальное решение задачи

Решение:

Необходимо найти минимальное значение целевой функции F = -3X1+X2 => min, при системе ограничений:

x1+3x2≤18 (1)

x1+2x2≥2 (2)

2x1+x2≥4 (3)

x1-x2≤2 (4)

Построим область допустимых решений, т. е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).

Обозначим границы области многоугольника решений.

Рассмотрим целевую функцию задачи F = -3X1+X2 => min.

Построим прямую, отвечающую значению функции F = 0: F = -3X1+X2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

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

Прямая F(x) = const пересекает область в точке I. Так как точка I получена в результате пересечения прямых 1 и 4, то ее координаты удовлетворяют уравнениям этих прямых:

x1+3x2≤18

x1-x2≤2

Решив систему уравнений, получим: x1 = 6, x2 = 4

Откуда найдем минимальное значение целевой функции:

F(X) = -3*6 + 1*4 = -14

2. Найти оптимальное решение

Решение:

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

Поскольку в правой части присутствуют отрицательные значения, умножим соответствующие строки на (-1).

Определим максимальное значение целевой функции F(X) = x1 + 2x2 + 2x3 при следующих условиях-ограничениях:

3x1 + 2x2 - x3≤6

2x1 + x2 + x3≤2

x1 + 3x2 + x3≤3

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6.

3x1 + 2x2-1x3 + 1x4 + 0x5 + 0x6 = 6

2x1 + 1x2 + 1x3 + 0x4 + 1x5 + 0x6 = 2

1x1 + 3x2 + 1x3 + 0x4 + 0x5 + 1x6 = 3

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных:

x4, x5, x6,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,6,2,3)

Базис	B	x1	x2	x3	x4	x5	x6
x4	6	3	2	-1	1	0	0
x5	2	2	1	1	0	1	0
x6	3	1	3	1	0	0	1
F(X0)	0	-1	-2	-2	0	0	0

Переходим к основному алгоритму симплекс-метода.

Итерация №0.

Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:

min (- , 2 : 1 , 3 : 1 ) = 2

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x4	6	3	2	-1	1	0	0	-
x5	2	2	1	1	0	1	0	2
x6	3	1	3	1	0	0	1	3
F(X1)	0	-1	-2	-2	0	0	0	0

Получаем новую симплекс-таблицу: