1. Исследование задачи оптимального распределения ресурсов

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.Определить величину ∆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. Находим отрицательный элемент в строке f_o(x).

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

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

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

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

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

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

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

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

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

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

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

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

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