Задание 10. Решить транспортную задачу при дополнительный условиях

Задание 2
Найти все базисные решения системы

Решение
x_2=(24-12x_3+4x_4)/8
x_1=(6+x_2+6x_3-5x_4)/9
Задание 3
Найти все опорные решения системы.

Решение
x_2=(9-x_3-x_4)/3=3-x_3/3-x_4/3
x_1=8-2x_3-(9-x_3-x_4)/3=5-5/3 x_3+x_4/3
Опорные решения:
X=(5;3;0;0),X=(10/3,8/3,1,0),X=(16/3,8/3,0,1),X=(11/3,7/3,1,1)

Задание 4
Решить графически задачу линейного программирования.

Решение
Решим задачу на максимум.

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
2x1-5x2=-10
4x1+5x2=40
Решив систему уравнений, получим: x1 = 5, x2 = 4
Откуда найдем максимальное значение целевой функции:
F(X) = 1*5 + 2*4 = 13
Решим задачу на минимум

Прямая F(x) = const пересекает область в точке A. Так как точка A получена в результате пересечения прямых (3) и (5), то ее координаты удовлетворяют уравнениям этих прямых:
x1+5x2=5
x1=0
Решив систему уравнений, получим: x1 = 0, x2 = 1
Откуда найдем минимальное значение целевой функции:
F(X) = 1*0 + 2*1 = 2
Задание 5
Решить симплексным методом следующую задачу линейного программирования.

Решение
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
x1+2x2+x3+x4 = 10
2x1+x2+2x3+x5 = 6
3x1+x2+2x3+x6 = 12
Введем новую переменную x0 = -3x1+4x2-x3.
Выразим базисные переменные <4, 5, 6> через небазисные (свободные).
x0 = 0-3x1+4x2-x3
x4 = 10-x1-2x2-x3
x5 = 6-2x1-x2-2x3
x6 = 12-3x1-x2-2x3
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют положительные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
Поскольку коэффициент при переменной x2 больше, чем при остальных переменных, то при увеличении x2целевая функция будет увеличиваться быстрее.
max(-3,4,-1,0,0,0) = 4
x0 = 0-3x1+4x2-x3
x4 = 10-x1-2x2-x3
x5 = 6-2x1-x2-2x3
x6 = 12-3x1-x2-2x3
В качестве новой переменной выбираем x2.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2 и из них выберем наименьшее:
min (10 : 2 , 6 : 1 , 12 : 1 ) = 5
Вместо переменной x4 в план войдет переменная x2.
Выразим переменную x2 через x4
x2 = 5-1/2x1-1/2x3-1/2x4
и подставим во все выражения.
x0 = 0-3x1+4(5-1/2x1-1/2x3-1/2x4)-x3
x5 = 6-2x1-(5-1/2x1-1/2x3-1/2x4)-2x3
x6 = 12-3x1-(5-1/2x1-1/2x3-1/2x4)-2x3
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 20-5x1-3x3-2x4
x2 = 5-1/2x1-1/2x3-1/2x4
x5 = 1-3/2x1-3/2x3+1/2x4
x6 = 7-5/2x1-3/2x3+1/2x4
Полагая небазисные переменные x = (2, 5, 6) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (5, 0, 3, 2, 0, 0), x0 = 20
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 20-5x1-3x3-2x4
x2 = 5-1/2x1-1/2x3-1/2x4
x5 = 1-3/2x1-3/2x3+1/2x4
x6 = 7-5/2x1-3/2x3+1/2x4
Оптимальный план можно записать так:
x1 = 0, x2 = 5, x3 = 0
F(X) = -3*0 + 4*5 -1*0 = 20

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

Решение
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
x1+x2+2x3+x4 = 4
x1-x2+x3 = 2
3x1+x2+2x3-x5 = 6
Расширенная матрица системы ограничений-равенств данной задачи:
1 1 2 1 0 4
1 -1 1 0 0 2
3 1 2 0 -1 6


Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной можно выбрать x5.
Получаем новую матрицу:
1 1 2 1 0 4
1 -1 1 0 0 2
-3 -1 -2 0 1 -6
3. В качестве базовой переменной можно выбрать x3.
Разрешающий элемент РЭ=1. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2записываем нули.
Все остальные элементы определяются по правилу прямоугольника.
Получаем новую матрицу:
-1 3 0 1 0 0
1 -1 1 0 0 2
-1 -3 0 0 1 -2
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,3,5).
Выразим базисные переменные через остальные:
x4 = x1-3x2
x3 = -x1+x2+2
x5 = x1+3x2-2
Подставим их в целевую функцию:
F(X) = -2x1-2x2-2(-x1+x2+2)
или
F(X) = -4x2-4
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной x5 следует ввести переменную x1.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B x1 x2 x3 x4 x5
x4 2 0 6 0 1 -1
x3 0 0 -4 1 0 1
x1 2 1 3 0 0 -1
F(X0) -4 0 -4 0 0 0
Выразим базисные переменные через остальные: