Привести математическую формулировку задачи
Привести математическую формулировку двойственной задачи
Решить двойственную задачу симплексным методом
Найти решение исходной задачи в последней симплексной таблице двойственной задачи
Вариант 4
Рацион некоторого животного должен в день содержать не менее 350 единиц углеводов и 250 единиц протеина. Для составления рациона имеется три основных вида продуктов. Продукт I стоит - 350 р за весовую единицу, продукт II – 50 р за весовую единицу, продукт III – 250 р за весовую единицу. Продукт I содержит 15 единиц углеводов и 50 единиц протеина, продукт II содержит 120 единиц углеводов и 20 единиц протеина, а продукт III содержит 50 единиц углеводов и 40 единиц протеина на одну весовую единицу корма. Определить самую дешевую комбинацию продуктов, которая удовлетворит необходимым ограничениям.
Ответ
y1=1519,y2=7938, FY3=15321719 или x1=0, x2=1538, x3=6119, FX=15321719.
Решение
Для большей наглядности составим таблицу:
Добавки Продукты Минимум
I II III
Углеводы 15 120 50 <=350
Протеин 50 20 40 =250
Стоимость, р. 350 50 250
Пусть куплено x1 весовых единиц продукта I, x2 весовых единиц продукта II и x3 весовых единиц продукта III. Тогда целевая функция будет выглядеть следующим образом:
Fx=350x1+50x2+250x3→min.
Рацион должен иметь не менее 350 единиц углеводов:
15x1+120x2+50x3≤350,
а также 250 единиц протеина:
50x1+20x2+40x3=250.
Также необходима неотрицательность переменных x1,x2,x3:
x1,x2,x3≥0.
Получили следующую математическую модель:
Fx=350x1+50x2+250x3→min.
15x1+120x2+50x3≤350,50x1+20x2+40x3=250,x1,x2,x3≥0.
Упоядочим задачу линейного программирования. Для задачи на максимум ограничения задачи линейного программирования должны быть либо в виде равенств, либо в виде "≤", а для задачи на минимум − либо в виде равенств, либо в виде "≥". У нас задача на минимум. Поэтому, если есть ограничения в виде "≤", то умножим данную строку на −1:
Fx=350x1+50x2+250x3→min.
-15x1-120x2-50x3≥-350,50x1+20x2+40x3=250,x1,x2,x3≥0.
Сделаем следующие обозначения. Вектор коэффициентов целевой функции прямой задачи:
C=350 50 250.
Свободные члены системы ограничений прямой задачи:
B=-350250.
Матрица коэффициентов прямой задачи:
A=-15-120-50502040.
Двойственная задача строится следующим образом. Если целевая функция исходной задачи исследуется на максимум, до целевая функция двойственной задачи исследуется на минимум и наоборот. Коэффициенты целевой функции двойственной задачи совпадают с свободными членами системы ограничений прямой задачи:
Cдв=BT=-350 250.
Свободные члены двойственной задачи равны коэффициентам целевой функции прямой задачи
Bдв=CT=35050250.
Матрица коэффициентов двойственной задачи равно матрице коэффициентов прямой задачи, взятой в транспонированном виде.
Aдв=AT=-1550-12020-5040.
Количество переменных двойственной задачи равно количеству ограничений прямой задачи, а количество ограничений двойственной задачи равно количеству переменных прямой задачи.
Поскольку у нас целевая функция двойственной задачи исследуется на максимум, то ограничения двойственной задачи должны быть либо в виде "≤", либо в виде "=", причем знак "=" будет в том случае, если соответствущей этой строке переменная исходной задачи не имеет ограничение в виде ее неотрицательности
. Если в исходной задаче есть ограничения в виде равенств, то соответствующие им переменные двойственной задачи не имеют ограничения в виде неотрицательности.
Учитывая вышесказанное, запишем двойственную задачу линейного программирования:
-350y1+250y2→max
-15y1+50y2≤350,-120y1+20y2≤50,-50y1+40y2≤250,y1≥0, y2-∀.
Решим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы.Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).В 1-м неравенстве вводим базисную переменную y3. В 2-м неравенстве вводим базисную переменную y4. В 3-м неравенстве смысла вводим базисную переменную y5.
-15y1+50y2+y3=350,-120y1+20y2+y4=50,-50y1+40y2+x5=250,Матрица коэффициентов А этой системы уравнений имеет вид:
A=-1550100-12020010-5040001.
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.Решим систему уравнений относительно базисных переменных: y3, y4, y5.Полагая, что свободные переменные равны 0, получим первый опорный план:Y0 = 0, 0, 350, 50, 250.Базисное решение называется допустимым, если оно неотрицательно.
Базис B y1
y2
y3
y4
y5
y3
350 -15 50 1 0 0
y4
50 -120 20 0 1 0
y5
250 -50 40 0 0 1
F(Y0)
0 350 -250 0 0 0
Переходим к основному алгоритму симплекс-метода.Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.В качестве ведущего выберем столбец, соответствующий переменной y2, так как это наибольший коэффициент по модулю.Вычислим значения min по строкам как частное от деления: biai2 и из них выберем наименьшее.
b1a12=35050=7,
b2a22=5020=52=212,
b3a32=25040=254=614.min 7, 212, 614=212.Следовательно, 2-ая строка является ведущей.Разрешающий элемент равен (20) и находится на пересечении ведущего столбца и ведущей строки.
Базис B y1
y2
y3
y4
y5
min
y3
350 -15 50 1 0 0 7
y4
50 -120 20 0 1 0 52
y5
250 -50 40 0 0 1 254
F(Y1)
0 350 -250 0 0 0
Формируем следующую часть симплексной таблицы
Задать вопрос
на новый заказ в Автор24.
