Контрольная по методам принятия оптимальных решений (вариант 62)

      В организации имеется возможность выпускать 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.Определить величину ∆b_s ресурса Р_s, введением которого в производство можно компенсировать убыток и сохранить максимальный доход на прежнем уровне (ресурсы предполагаются взаимно заменяемыми), получаемый при исключении из производства ∆b_r единиц ресурса Р_r, что вызывает уменьшение максимального дохода на ∆_rf_omax ед.

        8.Оценить целесообразность приобретения ∆b_k единиц ресурса Р_k по цене w_k  за единицу.

       9.Установить, целесообразно ли выпускать новое изделие П₁, на единицу которого ресурсы Р₁, Р₂, Р₃ расходуются в количествах a₁q, a₂q,  a₃q единиц, а цена единицы изделия составляет с₀ единиц.

       11.Решить задачу аналитически в среде Microsoft Exсel, приложить отчеты.

    1.2 Алгоритм двойственного cимплекс-метода

1. Выбор разрешающей строки

1.1.   Находим отрицательный элемент в строке f_o(x).

1.2.   В столбце над этим найденным элементом выбираем любой положительный элемент, эта строка – разрешающая, переход на пункт 2.

1.3.   Если в столбце над найденным элементом нет положительных элементов, то ПЗЛП не имеет смысла, а ДЗЛП не имеет решения, переход на пункт 10.

1. Выбор разрешающего столбца

2.1.   Элементы строки f_o(x) делим на соответствующие элементы разрешающей строки под переменными.

2.2.   Из полученных отношений выбираем максимальное отрицательное, этот столбец – разрешающий, переход на пункт 2.4.

2.3.   Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения, переход на пункт 10.

2.4.   На пересечении разрешающей строки и разрешающего столбца получен разрешающий элемент.

1. Заполнение нижних частей клеток таблицы.

3.1.   Под разрешающим элементом  всегда ставим  «1».

3.2.   Остальные элементы разрешающей строки переписываются без изменений

3.3.   Остальные элементы разрешающего столбца переписываются с противоположным знаком.

3.4.   Остальные элементы  находим по правилу прямоугольника:

искомый  элемент умножаем на разрешающий; и из этого произведения вычитаем произведение элементов, расположенных на противоположной диагонали прямоугольника, образуемого искомым и  разрешающим элементами (все элементы из верхних клеток).

1. Построение новой симплекс-таблицы

4.1.   Меняем местами переменные из  разрешающей строки и разрешающего столбца.

4.2.   Элементы из нижних клеток предыдущей симплекс-таблицы  делим на верхний разрешающий элемент и записываем на соответствующие места в верхние клетки новой симплекс-таблицы.

1. Если в новой таблице  в строке f₀(x) есть отрицательные элементы то переходим на пункт 1. (Нецелесообразно  выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).
2. Нахождение допустимого (одновременно оптимального) решения прямой задачи.

6.1.   Если в новой таблице  в строке f₀(x) нет отрицательных элементов, а в столбце свободных членов остались отрицательные элементы, то строка с отрицательным значением b_i  выбирается за разрешающую.

6.2.   Переход на пункт 2.

1. Если в новой симплекс-таблице в  строке f₀(x) и столбце b_iнет отрицательных элементов, то найденное решение является оптимальным.
2. Если в строке f₀(x) есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.

8.1.   Столбец с нулевым элементом в строке f₀(x) выбирается за разрешающий.

8.2.   Находится неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца.

8.3.   Из полученных отношений выбирается минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден.

8.4.   Переход на пункт 3.

1. Если в столбце b_i есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода.

9.1.   Строка с нулевым элементом в столбце b_iвыбирается за разрешающую.

9.2.   Переход на пункт 2.

1. Конец.

Замечание: можно находить решение только прямой задачи, а решение двойственной находится из взаимооднозначного соответствия переменных прямой и двойственной задач.