Задача 2.12.

Решение

Задача уже задана в канонической форме:

В качестве базисных возьмем переменные .

Выразим базисные переменные через свободные переменные :

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

X_{1 оп.} (0; 0; 1; 1; 2)

Если подставить в выражение для целевой функции начальное опорное решение, то получим Z(X_{1 оп.}) = .

Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:

,

где: - вектор коэффициентов целевой функции при базисных переменных;

- вектор разложения соответствующего вектора по базису опорного решения;

с_к - коэффициент целевой функции при переменной х_к.

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

i	Базис	сi	2	-1	3	-2	1	F(X)
			x1	x2	x3	x4	x5	А0
1	x3	3	-1	1	1	0	0	1
2	x4	-2	1	-1	0	1	0	1
3	x5	1	1	1	0	0	1	2
∆ j			-6	7	0	0	0	3

Оценка ∆₁ отрицательна, следовательно, значение целевой функции можно улучшить, перейдя к другому опорному решению.

Для выбора разрешающей строки найдем минимальное отношение свободного члена из столбца А₀ к соответствующему положительному коэффициенту из столбцов ∆₁ и ∆₂ , т.е. min{-; 1/1; 2/1} = min{-; 1; 2} = 2. Таким образом, в качестве разрешающей строки берем вторую строку таблицы и выводим переменную х₄ из базиса. А вводить в базис соответствующую переменную x₁. Столбец x₁ становится разрешающим. На втором шаге итерации базис будет состоять из переменных x₃, х₁, х₅.

i	Базис	сi	2	-1	3	-2	1	F(X)
			x1	x2	x3	x4	x5	А0
1	x3	3	-1	1	1	0	0	1
2	x4	-2	1	-1	0	1	0	1
3	x5	1	1	1	0	0	1	2
∆ j			-6	7	0	0	0	3

Заполняем вторую симплексную таблицу. Производим симплексное преобразование. Так как разрешающий элемент уже равен 1, то вторая строка остается без изменений. Далее вторую строку прибавляем к первой строке. Далее вторую строку вычитаем из третьей строки. Далее вторую строку умножаем на 6 и прибавляем к четвертой строке. Эти действия позволяют обнулить элементы под разрешающим элементом.

i	Базис	сi	2	-1	3	-2	1	F(X)
			x1	x2	x3	x4	x5	А0
1	x3	3	0	0	1	1	0	2
2	x1	2	1	-1	0	1	0	1
3	x5	1	0	2	0	-1	1	1
∆ j			0	1	0	6	0	9

Новый опорный план является оптимальным, так как все ∆_j ≥ 0.

Оптимальный план выпуска продукции:

x₁ = 1, x₂ = 0, x₃ = 2, x₄ = 0, x₅ = 1.

Максимальное значение целевой функции составляет

.

II. Получим оптимальный план выпуска продукции с помощью надстройки Поиск решения (Ехсеl). Искать решение будем для преобразованной системы (*).

Создаем форму для решения и вводим формулы:

Получаем следующую форму:

Задаем целевую ячейку и ограничения с помощью встроенной программы Поиск решения (выбираем поиск минимального значения):

Нажимаем выполнить и получаем решение:

Решение F_max(Х) = 9 – совпало с решением, найденным ранее симплекс-методом.

Ответ: максимальное значение целевой функции составляет Z_max(Х) = 9. Оптимальный план выпуска продукции: x₁ = 1, x₂ = 0, x₃ = 2, x₄ = 0, x₅ = 1.

Задача 3.2. Решить задачу графическим способом.