Методы оптимальных решений. Контрольная работа.

Задачи 1.5
Решить графически
Необходимо найти максимальное значение целевой функции
F = 3x1+2x2 → max, при системе ограничений:
2x1+x2≤2 (1)
3x1+4x2≤12 (2)
x1≥0 (3)
x2≥0 (4)
Задача 2.5
Для производства 4х видов продукции предприятие использует 4ре вида сырья. Другие условия задачи приведены в таблице.
Вид ресурса Изделие Запас сырья
1 2 3 4
I 3 4 10 8 80
II 9 5 12 9 90
III 12 6 15 10 100
ценность 5,5 7 9 11

Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной. Задачу решить симплекс методом. Составить двойственную задачу и решить симплекс методом.
Задача 3.5
Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственн ...

Отсутствует

Отсутствует

к. в строке целевой функции нет положительных коэффициентов.Ответ:Оптимальное значение функции Q(x)=3503достигается в точке с координатами:x1=0x2=503x3=0x4=0s1=403s2=203s3=0Прямая задача линейного программирования имеет вид:F(X)=5.5X1+7X2+9X3+11X4 (max)Ограничения:3X1+4X2+10X3+8X4≤809X1+5X2+12X3+9X4≤9012X1+6X2+15X3+10X4≤100X1≥0X2≥0X3≥0X4≥0Так как в прямой задаче требуется найти максимум фунции, то приведем первоначальное условие к виду{F(x) = СT x| Ax≤B, xi ≥0, i = 1,m}В результате получим следующие матрицы:CT=5.57911A=34108951291261510B=8090100Для составления двойственной задачи линейного программирования найдем матрицы АT, BT, CC=5.57911AT=39124561012158910BT=8090100Следовательно, двойственная задача линейного программирования будет иметь вид:F(Y)=80Y1+90Y2+100Y3 (min)Ограничения:3Y1+9Y2+12Y3≥5.54Y1+5Y2+6Y3≥710Y1+12Y2+15Y3≥98Y1+9Y2+10Y3≥11Y1≥0Y2≥0Y3≥0Шаг:1Избавимся от неравенств в ограничениях, введя в ограничения 1, 2, 3, 4 неотрицательные балансовые переменные s1, s2, s3,s4.3x1+9x2+12x3-s1=112   (1)4x1+5x2+6x3-s2=7   (2)10x1+12x2+15x3-s3=9   (3)8x1+9x2+10x3-s4=11   (4)x1, x2, x3, s1, s2, s3, s4 ≥ 0Шаг:2Ищем в системе ограничений базисные переменные.Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу.Введем по одной искусственной неотрицательной переменной ri в каждое уравнение системы ограничений.Получим следующую систему ограничений,3x1+9x2+12x3-s1+r1=112   (1)4x1+5x2+6x3-s2+r2=7   (2)10x1+12x2+15x3-s3+r3=9   (3)8x1+9x2+10x3-s4+r4=11   (4)x1, x2, x3, s1, s2, s3, s4, r1, r2, r3, r4 ≥ 0с базисными переменными r1,r2,r3,r4.Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2,r3,r4). Для этого сформируем вспомогательную целевую функцию :G =r1+r2+r3+r4и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:   - вычтем из функции G уравнение 1   - вычтем из функции G уравнение 2   - вычтем из функции G уравнение 3   - вычтем из функции G уравнение 4 Функция G примет вид : G =-25x1-35x2-43x3+s1+s2+s3+s4+652Теперь мы можем сформировать начальную симплекс-таблицу.Шаг:3Начальная симплекс-таблицаБПx1x2x3s1s2s3s4r1r2r3r4РешениеОтношениеr13912-10001000112112/12=1124r24560-100010077/6=76r310121500-10001099/15=35r48910000-100011111/10=1110Q8090100000000000--G-25-35-4311110000-652--Итерация 1  БПx1x2x3s1s2s3s4r2r3r4РешениеОтношениеx314341-11200000011241124/14=116r25212012-100100174174/52=1710r3254340540-10010178178/254=1750r41123205600-100177127712/112=76Q55150253000000-2756--G-574-1140-3112111000-30724--Итерация 2  БПx1x2x3s1s2s3s4r2r4РешениеОтношениеx3018251-215012500028752875/125=283r201500-125010175175/25=172x113250150-4250001750--r4021250-41502225-1013417534175/2225=316Q04250-830445000-96815--G0-262504151-3225100-59675--Итерация БПx1x2x3s1s2s3s4r2РешениеОтношениеx3015221-4330012201616/122=113r20-2110433-1051114343/511=4415x11311053300-211076--s3021220-103301-25220316--Q000000100-110--G02110-43310-5110-43--Итерация 3-a  БПx1x2x3s1s2s3s4РешениеОтношениеx307101-21511000130--s40-250415-1150144154415/7=11x1115015-250017101710/1=172s301200-5210172--Q040-832200-4183--G00000000--Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"Итерация 4  БПx1x2x3s1s2s3s4РешениеОтношениеx307101-21511000130--s40-250415-1150144154415/415=11x1115015-250017101710/15=172s301200-5210172--Q040-832200-4183--Итерация 5  БПx1x2x3s1s2s3s4РешениеОтношениеx3235610-160076--s4-43-2300-530123--s15101-200172--s301200-5210172--Q4032030050300-3503--Достигнуто оптимальное решение, т.к. в строке целевой функции нет отрицательных коэффициентов.Ответ:Оптимальное значение функции Q(x)=3503достигается в точке с координатами:x1=0x2=0x3=76s1=172s2=0s3=172s4=23Задача 3.5Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 100,190,80,70 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 150,130,160 ед.