К данной задаче линейного программирования составить двойственную задачу. Решить данную задачу графическим методом, а двойственную задачу симплекс- методом. Применяя теорему двойственности получить решение двойственной задачи по известному решению исходной задачи.
Для всех вариантов x1≥ 0, x2≥0.
2x1 +5x2≤ 20,
6x1+7x2 ≤ 42,
10x1+3x2 ≤ 30,
ƒ( x ) = 4x1 +4x2→max
Решение
Решаем данную задачу графическим методом.
Построим область допустимых решений, т.е. решим графически систему неравенств.
Рассмотрим целевую функцию задачи f =4 x1 + 4 x2 → max.
Построим прямую, отвечающую значению функции f = 0: f = 4 x1 + 4 x2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации f(X). Начало вектора – точка (0; 0), конец – точка (4; 4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, двигаем прямую до последнего касания обозначенной области.
Так как точка M получена в результате пересечения прямых 2x1+5x2=20,10x1+3x2=30, то ее координаты удовлетворяют уравнениям этих прямых:
2x1+5x2=2010x1+3x2=30
Решив систему уравнений, получим: x1=45/22, x2=35/11
Откуда найдем максимальное значение целевой функции:
fmax=4*45/22+4*35/11=230/11
Составим двойственную задачу.
138493519367500g=20y1+42y2+30y3 → min2y1+6y2+10y3≥45y1+7y2+3y3≥4y1 ≥ 0, y2 ≥ 0, y3 ≥ 0
Переходим к канонической форме.
2y1+6y2+10y3-y4 = 4
5y1+7y2+3y3-y5 = 4
Домножим оба уравнения на -1
-2y1-6y2-10y3+y4 = -4
-5y1-7y2-3y3+y5 = -4
В качестве базисных переменных принимаем Y = (4,5).Выразим базисные переменные через остальные:
y4 = 2y1+6y2+10y3-4
y5 = 5y1+7y2+3y3-4
Подставим их в целевую функцию:
g(Y) = 20y1+42y2+30y3
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной y4 следует ввести переменную y3.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B y1 y2 y3 y4 y5
y3 2/5 1/5 3/5 1 -1/10 0
y5 -14/5 -22/5 -26/5 0 -3/10 1
g(Y0) -12 14 24 0 3 0
Среди свободных членов bi имеются отрицательные значения, следовательно, полученный базисный план не является опорным.
Вместо переменной y5 следует ввести переменную y4.
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.
Базис B y1 y2 y3 y4 y5
y3 4/3 5/3 7/3 1 0 -1/3
y4 28/3 44/3 52/3 0 1 -10/3
g(Y1) -40 -30 -28 0 0 10
Выразим базисные переменные через остальные:
y3 = -5/3y1-7/3y2+1/3y5+11/3
y4 = -44/3y1-52/3y2+10/3y5+91/3
Подставим их в целевую функцию:
g(Y) = 20y1+42y2+30(-5/3y1-7/3y2+1/3y5+11/3) = -30y1-28y2+10y5+40
5/3y1+7/3y2+y3-1/3y5=11/3
44/3y1+52/3y2+y4-10/3y5=91/3
При вычислениях значение gc = 40 временно не учитываем.
Решим систему уравнений относительно базисных переменных: y3, y4Полагая, что свободные переменные равны 0, получим первый опорный план:Y0 = (0,0,11/3,91/3,0)
Базис B y1 y2 y3 y4 y5
y3 4/3 5/3 7/3 1 0 -1/3
y4 28/3 44/3 52/3 0 1 -10/3
g(Y0) 0 30 28 0 0 -10
Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты.
В качестве ведущего выберем столбец, соответствующий переменной y1, так как это наибольший коэффициент.
2-ая строка является ведущей.
Разрешающий элемент равен (142/3) и находится на пересечении ведущего столбца и ведущей строки.
Формируем следующую часть симплексной таблицы
Задать вопрос
на новый заказ в Автор24.
