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

Решение задач по Мору) 100 баллов от препода, работа была заказана) ...

Само решение

1.1 Задание
В организации имеется возможность выпускать n видов изделий П1, П2, П3,…, Пn. При их изготовлении используются ресурсы Р1, Р2, Р3,…, Рm. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2, b3,…, bm. Расход ресурса i-го вида (i=1,2,…,m) на единицу изделия j-го вида (j=1,2,…,n) составляет aij ден. ед. Цена единицы продукции j-го вида равна сj. Требуется найти оптимальный план выпуска изделий, который обеспечивал бы организации максимальный доход.
1.Построить математическую модель задачи распределения ресурсов.
2.Построить двойственную задачу к задаче распределения ресурсов, дать экономическую интерпретацию.
3.Двойственным симплекс-методом найти оптимальное решение прямой и двойственной задач, пояснить экономический смысл всех п еременных, участвующих в решении.
4.Найти границы изменения дефицитных ресурсов, в пределах которых не изменится структура оптимального плана.
5.Уточнить значения недефицитных ресурсов, при которых оптимальный план не изменится.
6.Найти границы изменения цены изделия каждого вида, в пределах которых оптимальный план не изменится.
7.Определить величину ∆bs ресурса Рs, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства ∆br единиц ресурса Рr, что вызывает уменьшение максимального дохода на ∆rfomax ед.
8.Оценить целесообразность приобретения ∆bk единиц ресурса Рk по цене wk за единицу.
9.Установить, целесообразно ли выпускать новое изделие П1, на единицу которого ресурсы Р1, Р2, Р3 расходуются в количествах a1q, a2q, a3q единиц, а цена единицы изделия составляет с0 единиц.
11.Решить задачу аналитически в среде Microsoft Exсel, приложить отчеты.

1.2 Алгоритм двойственного cимплекс-метода
1. Выбор разрешающей строки
1.1. Находим отрицательный элемент в строке fo(x).
1.2. В столбце над этим найденным элементом выбираем любой положительный элемент, эта строка – разрешающая, переход на пункт 2.
1.3. Если в столбце над найденным элементом нет положительных элементов, то ПЗЛП не имеет смысла, а ДЗЛП не имеет решения, переход на пункт 10.
2. Выбор разрешающего столбца
2.1. Элементы строки fo(x) делим на соответствующие элементы разрешающей строки под переменными.
2.2. Из полученных отношений выбираем максимальное отрицательное, этот столбец – разрешающий, переход на пункт 2.4.
2.3. Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения, переход на пункт 10.
2.4. На пересечении разрешающей строки и разрешающего столбца получен разрешающий элемент.
3. Заполнение нижних частей клеток таблицы.
3.1. Под разрешающим элементом всегда ставим «1».
3.2. Остальные элементы разрешающей строки переписываются без изменений
3.3. Остальные элементы разрешающего столбца переписываются с противоположным знаком.
3.4. Остальные элементы находим по правилу прямоугольника:
искомый элемент умножаем на разрешающий; и из этого произведения вычитаем произведение элементов, расположенных на противоположной диагонали прямоугольника, образуемого искомым и разрешающим элементами (все элементы из верхних клеток).
4. Построение новой симплекс-таблицы
4.1. Меняем местами переменные из разрешающей строки и разрешающего столбца.
4.2. Элементы из нижних клеток предыдущей симплекс-таблицы делим на верхний разрешающий элемент и записываем на соответствующие места в верхние клетки новой симплекс-таблицы.
5. Если в новой таблице в строке f0(x) есть отрицательные элементы то переходим на пункт 1. (Нецелесообразно выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).
6. Нахождение допустимого (одновременно оптимального) решения прямой задачи.
6.1. Если в новой таблице в строке f0(x) нет отрицательных элементов, а в столбце свободных членов остались отрицательные элементы, то строка с отрицательным значением bi выбирается за разрешающую.
6.2. Переход на пункт 2.
7. Если в новой симплекс-таблице в строке f0(x) и столбце bi нет отрицательных элементов, то найденное решение является оптимальным.
8. Если в строке f0(x) есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.
8.1. Столбец с нулевым элементом в строке f0(x) выбирается за разрешающий.
8.2. Находится неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца.
8.3. Из полученных отношений выбирается минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден.
8.4. Переход на пункт 3.
9. Если в столбце bi есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.
9.1. Строка с нулевым элементом в столбце bi выбирается за разрешающую.
9.2. Переход на пункт 2.
10. Конец.
Замечание: можно находить решение только прямой задачи, а решение двойственной находится из взаимооднозначного соответствия переменных прямой и двойственной задач.

Построение новой симплекс-таблицыМеняем местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делим на верхний разрешающий элемент и записываем на соответствующие места в верхние клетки новой симплекс-таблицы.Если в новой таблице в строке f0(x) есть отрицательные элементы то переходим на пункт 1. (Нецелесообразно выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).Нахождение допустимого (одновременно оптимального) решения прямой задачи.Если в новой таблице в строке f0(x) нет отрицательных элементов, а в столбце свободных членов остались отрицательные элементы, то строка с отрицательным значением bi выбирается за разрешающую. Переход на пункт 2.Если в новой симплекс-таблице в строке f0(x) и столбцеbi нет отрицательных элементов, то найденное решение является оптимальным.Если в строке f0(x) есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.Столбец с нулевым элементом в строке f0(x) выбирается за разрешающий.Находится неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца.Из полученных отношений выбирается минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден.Переход на пункт 3.Если в столбце bi есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.Строка с нулевым элементом в столбце bi выбирается за разрешающую.Переход на пункт 2.Конец. Замечание: можно находить решение только прямой задачи, а решение двойственной находится из взаимооднозначного соответствия переменных прямой и двойственной задач.Исходные данныеОбозначенияВариант 55n3b135b255b345a111a123a136a212a223a231a316a321a332c13c24c31r1∆br0,2s2k3∆bk0,2ck15ℓ4a1ℓ2a2ℓ3a3ℓ1cℓ35Представим исходные данные таблицей 0.Таблица 0 - Исходные данныеНорма затратРесурсыВиды изделийКол-во ресурсовСкрытые цены ресурсовyiyi*136352315561245Цена единицы изделия341maxf0(х)ming0(у)План выпускаxjxj* 1. R= 2. Q= 3. Переход к канонической форме ПЗЛП с помощью введения дополнительных переменных x4, x5, x6.R= Переход к канонической форме ДЗЛП с помощью введения дополнительных переменных y4, y5, y6. Q= Выражение базисных переменныx Таблица 1 – Шаг 1 симплекс-метода 1 -11 3 -156-635-2952233115555621-52-245-65-3 -1 -4 -1 -1 10 55Таблица 2 – Шаг 2 симплекс-метода -11 -3 -15 15-6-3-295-602231115555216-55-2-1-6580-1 -1 -1 1 1 455 220Таблица 3 – Шаг 3 симплекс-метода -1 1 5 28,333-15,667-20-800,667-0,6670,3330,6670,333218,333805,33311,6671,667-0,333-0,33326,66726,667-0,333 -0,333 0,333 2,333 1,333 773,333 400Таблица 4 – Шаг 4 симплекс-метода0,1875 0,1875 5,3125 5,3125-1,06251-15-15-0,1250,06250,125-2,1250,375-0,37515-10,31250,1875-0,18750,31250-0,06250,06255-6,250,0625 -0,31250,4375 -7,43751,3125 -1,312675 -60Таблица 5 – Шаг 5 симплекс-метода-0,17647-5-0,9411814,11765-0,0588220,3529419,7058820,1764710-0,058825,8823530,29411871,23529456,47059Таблица 8 – Экономический смысл оптимальных решений ПЗЛП и ДЗЛПКомпоненты оптимального решенияП1П2П3Излишки ресурсовПЗЛПХ1*Х2*Х3*Х4*Х5*Х6*5,8823539,7058820014,117650ДЗЛП0071,23529400,294118У4*У5*У6*У1*У2*У3*Превышение затрат на производство единицы продукции в скрытых ценах ресурсов над ценойСкрытые цены ресурсовКомпоненты оптимального решения Экономический смысл переменных:x1*, x2*, x3* - основные переменные - оптимальный план производства, x4*,x5*,x6* - дополнительные переменные - изменение ресурсов,y1,y2,y3-основные переменные - скрытые цены.y4,y5,y6 - дополнительные переменны – избытки от производства (издержки, не вошедшие в план производства).