Линейное программирование: Рабочая программа, контрольные работы и учебное пособие, страница 11

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения переменную . Так как минимальное значение  достигается при , то исключаем из базиса переменную . После первой итерации симплекс-таблица примет вид:

№			1	4	1	0	0
5	7	0	0	0	0	1	1
1	1/5	1	1	-3/5	0	-2/5	0
3	21/5	1	0	7/5	1	3/5	0
		22/5	1	4/5	1	1/5	0
			0	-16/5	0	1/5	0

Так как в строке  есть отрицательная оценка , то решение не является оптимальным. Значит, с помощью симплекс-метода нужно улучшить решение, найти другое решение, при котором значение функции  будет больше найденного . При следующей итерации из базиса выводится переменная , так как , а в базис вводится переменная , так как в столбце с отрицательной оценкой есть только один положительный элемент 7/5, который находится в третьей строке. После этой итерации симплекс-таблица примет вид:

№			1	4	1	0	0
5	7	0	0	0	0	1	1
1	2	1	1	0	3/7	-1/7	0
2	3	4	0	1	5/7	3/7	0
		14	1	4	23/7	11/7	0
			0	0	16/7	11/7	0

Так как в строке  нет отрицательных оценок, то решение является оптимальным. Но в исходной задаче не было переменных  и , поэтому в ответе их не учитываем и получаем Х_опт=(2, 3, 0), .

Ответ: , Х_опт=(2, 3, 0).

Задача 3.  Для данной задачи линейного программирования построить двойственную, решить ее графически, по теореме двойственности найти решение исходной задачи:

Решение. В исходной задаче:

, , , ,

то есть нужно максимизировать функцию , если  и . Тогда для этой задачи можно построить двойственную: минимизировать функцию , если , где , , , , или

                        (2.2)

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

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

Рис.2.2

Строим линию уровня , перпендикулярную к вектору , и находим точку  как решение системы уравнений граничных прямых (1) и (2). Тогда решением двойственной задачи будет .

Подставим значения координат  –  и  в систему ограничений (2.2):

Так как при подстановке оптимального решения  в систему ограничений (2.2) третье и четвертое ограничения выполняются как строгие неравенства, то соответствующие координаты оптимального решения исходной задачи равны 0, то есть (см. п.1.10, вторая теорема двойственности). Подставим эти значения в исходную систему ограничений:

         или                

откуда , . Значит,  и .

Ответ: .

Задача 4. Решить транспортную задачу методом потенциалов:

	45	15	20	20
25	9	5	3	10
55	6	3	8	2
20	3	8	4	8

Решение. Определим исходное опорное решение для данной транспортной задачи по методу «минимального элемента».

Просматривая элементы матрицы затрат, находим наименьший элемент . Поэтому принимаем  и исключаем из дальнейшего рассмотрения четвертый столбец, так как . Далее снова находим в оставшейся матрице наименьший элемент  (так как , то можно взять любой). Следовательно, . Теперь исключаем из дальнейшего рассмотрения второй столбец. В матрице затрат снова находим минимальный элемент . Поэтому принимаем  и исключаем третью строку. Новый минимальный элемент , следовательно, . На этом шаге исключаем из рассмотрения третий столбец. После этого остались невычеркнутыми клетки с номерами (1,1) и (2,1). Минимальным оказывается , откуда . Наконец, на последнем шаге заносим в единственную невычеркнутую клетку . Итак, получили исходное опорное решение:

.

Ему соответствует значение целевой функции .

Проверим, является ли найденное решение  оптимальным? Для этого построим систему потенциалов для найденного решения.

Согласно определению, числа  и  (потенциалы) должны удовлетворять  равенствам (в данном случае ):

,

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

Поскольку число уравнений на единицу меньше числа неизвестных, одно неизвестное всегда оказывается свободным и ему можно придать любое числовое значение. Положим  . Тогда из первого уравнения получаем  и из второго - . Из третьего уравнения, подставляя , находим  и из шестого уравнения . Далее, из четвертого и пятого уравнений после подстановки  получим  и . Найденные значения потенциалов указаны в первом столбце и первой строке таблицы:

		45		15		20		20
	25		9		5		3		10
		5				20
	55		6		3		8		2
		20		15				20
	20		3		8		4		8
		20