Метод оптимальных решений МОР

Решенная контрольная работа по МОР. ...

Условия
Решение
Список использованной литературы

Для производства двух видов изделий A и B предприятие использует три вида сырья. Другие условия задачи приведены в таблице.
Вид сырья Нормы расхода сырья на одно изделие, кг Общее количество сырья, кг
A B
I 2 3 90
II 1 3 60
III 4 5 360
Прибыль от реализации одного изделия, ден. ед. 60 15

Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной. Решить задачу графически. Составить двойственную задачу, решить ее с помощью теорем двойственности. Дать экономическую интерпретацию результатов.

Подставим оптимальный план прямой задачи в систему ограниченной математической модели:2*45 + 3*0 = 90 = 901*45 + 3*0 = 45 < 604*45 + 5*0 = 180 < 3601-ое ограничение прямой задачи выполняется как равенство. Это означает, что 1-ый ресурс полностью используется в оптимальном плане, является дефицитным и его оценка согласно второй теореме двойственности отлична от нуля (y1>0).2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y2 = 0.Неиспользованный экономический резерв ресурса 2 составляет 15 (60-45).Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).3-ое ограничение выполняется как строгое неравенство, т.е. ресурс 3-го вида израсходован не полностью. Значит, этот ресурс не является дефицитным и его оценка в оптимальном плане y3 = 0.Неиспользованный экономический резерв ресурса 3 составляет 180 (360-180).Этот резерв не может быть использован в оптимальном плане, но указывает на возможность изменений в объекте моделирования (например, резерв ресурса можно продать или сдать в аренду).Таким образом, отличную от нуля двойственные оценки имеют лишь те виды ресурсов, которые полностью используются в оптимальном плане. Поэтому двойственные оценки определяют дефицитность ресурсов.Обоснование эффективности оптимального плана.При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получим:2*30 + 1*0 + 4*0 = 60 = 603*30 + 3*0 + 5*0 = 90 > 121-ое ограничение двойственной задачи выполняется как равенство. Это означает, что 1-ый ресурс экономически выгодно использовать, а его использование предусмотрено оптимальным планом прямой задачи (x1>0).2-ое ограничение выполняется как строгое неравенство, т.е. ресурс 2-го вида использовать экономически не выгодно. И действительно в оптимальном плане прямой задачи x2 = 0.Поскольку теневая (альтернативная) цена больше рыночной цены этого продукта, то выгоднее продать ресурсы по рыночным ценам.При этом разница между ценами (90 - 12 = 78) показывает величину изменения целевой функции F(x) при введении дополнительной единицы xi.Задача 2.Решить задачу симплекс методомШаг:1Ищем в системе ограничений базисные переменные.Базисные переменные в исходной задаче отсутствуют, это значит, что исходная задача не содержит в себе допустимого базисного решения. Для его нахождения вначале составим и решим вспомогательную задачу.Введем по одной искусственной неотрицательной переменной ri в каждое уравнение системы ограничений.Получим следующую систему ограничений,4x1+x2-3x3-x4+2x5+r1= 3   (1)-x1+x2-5x3-2x4+3x5+r2= 1   (2)10x1+x2-2x3-2x4+4x5+r3= 2   (3)x1, x2, x3, x4, x5, r1, r2, r3 ≥ 0с базисными переменными r1,r2,r3.Целью решения вспомогательной задачи является получение допустимого базисного решения не содержащего искусственных переменных (r1,r2,r3). Для этого сформируем вспомогательную целевую функцию :G = r1+r2+r3и проведем ее минимизацию в заданной системе ограничений. Если после минимизации функции G ее оптимальное значение будет равно нулю и все искусственные переменные окажутся выведенными из базиса, то полученное базисное решение есть допустимое базисное решение исходной задачи. Если же после минимизации функции G ее оптимальное значение окажется отличным от нуля, значит исходная система ограничений противоречива (область допустимых решений пуста) и исходная задача решения не имеет.Для решения вспомогательной задачи симплекс-методом выразим функцию G через свободные переменные, для этого:   - вычтем из функции G уравнение 1   - вычтем из функции G уравнение 2   - вычтем из функции G уравнение 3 Функция G примет вид : G = -13x1-3x2+10x3+5x4-9x5+6Теперь мы можем сформировать начальную симплекс-таблицу.Шаг:2Начальная симплекс-таблицаБПx1x2x3x4x5r1r2r3РешениеОтношениеr14 1 -3 -1 2 1 0 0 3 3/4=3 4 r2-1 1 -5 -2 3 0 1 0 1 --r310 1 -2 -2 4 0 0 1 2 2/10=1 5 Q-7 1 -1 3 -5 0 0 0 0 --G-13 -3 10 5 -9 0 0 0 -6 --Итерация 1 Как производится итерация?...БПx1x2x3x4x5r1r2РешениеОтношениеr10 35-115-15251 0 11511 5 /2 5 =11 2 r20 1110-265-1151750 1 656 5 /17 5 =6 17 x11 110-15-15250 0 151 5 /2 5 =1 2 Q0 1710-12585-1150 0 75--G0 -1710375125-1950 0 -175--Итерация 2 Как производится итерация?...БПx1x2x3x4x5r1РешениеОтношениеr10 817-27171170 1 351735 17 /8 17 =35 8 x50 1134-2617-11171 0 6176 17 /11 34 =12 11 x11 -1347171170 0 117--Q0 4117-98173170 0 3717--G0 -8172717-1170 0 -3517--Итерация 3 Как производится итерация?...БПx1x2x3x4x5r1РешениеОтношениеr10 0 7111 -16111 171117 11 /1=17 11 x20 1 -5211-2 34110 1211--x11 0 3110 1110 111--Q0 0 62115 -82110 -511--G0 0 -711-1 16110 -1711--Итерация 3-a Как производится итерация?...БПx1x2x3x4x5РешениеОтношениеx40 0 7111 -1611171117 11 /4=17 7 x20 1 -38110 2114611--x11 0 3110 1111111 11 /1=1 3 Q0 0 27110 -211-9011--G0 0 0 0 0 0 --Получено оптимальное решение вспомогательной задачи (найден минимум функции G т.к. в строке целевой функции нет отрицательных коэффициентов). Все искусственные переменные вышли из базиса и поэтому мы можем приступить к решению исходной задачи, приняв полученное базисное решение в качестве опорного. Сторка "G" нам больше не нужна, принятие решения о направляющем столбце, во всех последующих итерациях, будем принимать по строке "Q"Итерация 4 Как производится итерация?...БПx1x2x3x4x5РешениеОтношениеx40 0 7111 -1611171117 11 /7 11 =17 7 x20 1 -38110 2114611--x11 0 3110 1111111 11 /3 11 =1 3 Q0 0 27110 -211-9011--Итерация 5 Как производится итерация?...БПx1x2x3x4x5РешениеОтношениеx4-730 0 1 -5343--x23831 0 0 43163--x31130 1 0 1313--Q-9 0 0 0 -1 -9 --Достигнуто оптимальное решение, т.к. в строке целевой функции нет положительных коэффициентов.Ответ:Оптимальное значение функции Q(x)=9достигается в точке с координатами:x1=0x2=16 3 x3=1 3 x4=4 3 x5=0Задача3. Решить транспортную задачуСтоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов12345Запасы151274819023692102103911476200Потребности100140110120130Решение.Проверим необходимое и достаточное условие разрешимости задачи.∑a = 190 + 210 + 200 = 600∑b = 100 + 140 + 110 + 120 + 130 = 600Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.Занесем исходные данные в распределительную таблицу.12345Запасы151274819023692102103911476200Потребности100140110120130Этап I. Поиск первого опорного плана.1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj.Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя.Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.Искомый элемент равен 2Для этого элемента запасы равны 210, потребности 120. Поскольку минимальным является 120, то вычитаем его.x24 = min(210,120) = 120.5127x8190369210210 - 120 = 909114x6200100140110120 - 120 = 01300Искомый элемент равен 3Для этого элемента запасы равны 90, потребности 100. Поскольку минимальным является 90, то вычитаем его.x21 = min(90,100) = 90.5127x81903xx2x90 - 90 = 09114x6200100 - 90 = 1014011001300Искомый элемент равен 4Для этого элемента запасы равны 200, потребности 110. Поскольку минимальным является 110, то вычитаем его.x33 = min(200,110) = 110.512xx81903xx2x09114x6200 - 110 = 9010140110 - 110 = 001300Искомый элемент равен 5Для этого элемента запасы равны 190, потребности 10. Поскольку минимальным является 10, то вычитаем его.x11 = min(190,10) = 10.512xx8190 - 10 = 1803xx2x0x114x69010 - 10 = 0140001300Искомый элемент равен 6Для этого элемента запасы равны 90, потребности 130. Поскольку минимальным является 90, то вычитаем его.x35 = min(90,130) = 90.