Линейное программирование

    0                                                                   35 Д            х1

рис. 2

Коэффициент c (2) можно увеличить до совпадения линии уровня с прямой (1.2), поэтому 10/ c (2)=35/70, c (2) max=20.

Аналогичные рассуждения для нахождения c (1) min и c (2) min.

Таким образом, оптимальное решение задачи не изменится, если отпускная цена на ед.изделия 1 лежит в диапазоне от 7,5 до 18,75, при этом доход будет от 525 тыс.руб до 750 тыс.руб. А отпускная цена на ед.изделия 2 лежит в диапазоне от 8 до 20, при этом доход будет от 400 тыс.руб до 700 тыс.руб.

3. Решение задачи симплекс-методом.

Для приведения системы к каноническому виду введем балансные неизвестные х3 , х4 , х5.

                                          35x1+70x2+х3                      =2450

                                          50x1+40x2       + х4           =2000                         (1.5)              

                                          80x1+35x2             + х5=2800

                                          10х1+15х2                    =F

Составим симплекс таблицу:

                                                                          Таблица 1.

Шаг 1. В столбцы 1-6 и строки 1-4 записываем коэффициенты при неизвестных и свободные члены системы (1.5). В столбце базисных переменных записываем их обозначения. Так как к началу решения оценки базисных переменных неизвестных даем им значения равные нулю. Оценки свободных переменных (количество выпускаемой продукции) принимаются равными их значениям в целевой функции. Решение задачи линейного программирования в симплексной таблице находится в столбце свободных членов, то есть решения на первом шаге выглядит как:

х1 =x2=0; x3=2450; x4=2000; x5=2800

Контрольный столбец служит для проверки правильности решения и представляет собой произведения коэффициентов столбца свободных членов на оценки соответствующих переменных. Сумма этих произведений дает значение целевой функции, в данном случае F (x)=0

Ведущий столбец – 2 (т.е максимальное значение целевой функции -15, которое принадлежит 2му столбцу), ведущая строка – 1 (т.е. при делении коэффициентов в столбце свободных членов на соответствующие коэффициенты ведущего столбца, минимальное значение 35, принадлежащее 1 строке).

Шаг 2. Переход к новому опорному плану осуществляется в результате пересчета симплексной таблицы методом Жордана - Гаусса.

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

Остальные коэффициенты пересчитываются по методу Жордана – Гаусса, т.е. по правилу прямоугольника следующим образом:

35                70

                                  50=50 - (35×40)/70 = 30

50                40

Шаг 3. Аналогично заполняется таблице на 3 шаге. Получаем, что в этой таблице все коэффициенты в строке целевой функции отрицательные или равные нулю, т.е. полученный план оптимален, т.е. нет ни одной переменной, введение которой в план увеличилось бы  значение целевой функции в 575 тыс.руб.

4. Решение двойственной задаче.

Составим и найдем решение двойственной задаче к задаче, решенной графическим и симплекс-методом.

Прямая задача:

Найти =(x₁, x₂), чтобы

F(x) =10x₁+15x₂→max, при

35x1+70x2≤2450

50x1+40x2≤2000

80x1+35x2≤2800

Решение прямой задачи:

x₁ =20; x₂=25

F(x) =575 тыс.руб.

Двойственная задача:

Найти =(u₁,u₂,u₃), чтобы

Z (u) = 2450u₁+2000u₂+2800u₃→min

35u₁+50u₂+80u₃≥10

70u₁+40u₂+35u₃≥15

Относительно рассматриваемого варианта задач соответствующие условия “дополняющей нежесткости” первой и второй группы выглядит следующим образом:

U₁↔(2450-35x₁-70x₂)=0;

             U₂↔(2000-50x₁-40x₂)=0;       (1.6)

U3↔(2800-80x1-35x2)= 0.

              X₁↔ (35u₁+50u₂+80u₃-10)=0;      (1.7)

X₂↔ (70u₁+40u₂+35u₃-15)=0;

Из группы условий (1.6), так как 2800-80×20-35×25=325>0 следует, что ограничения по материалам не лимитирует оптимальную программу, т.е. u₃=0.

Таким образом, из решения след. системы уравнений следует, что:

35u₁+50u₂=10

70u₁+40u₂=15

u₁=1/6; u₂=1/12

При этом доход составит: 2450×1/6+2000×1/12=575 тыс.руб

5. Расчет функции предельной эффективности ресурсов (теневых цен), поступающих на данное предприятие.

При сохранении лимитов по другим ресурсам исследуем зависимость максимума выручки от изменения лимита заработной платы в диапазоне от нуля до бесконечности. Это значит, что при графическом анализе прямые линии, соответствующие амортизации и материалам будут оставаться на своих местах, а прямая линия, соответствующая ограничению по заработной плате будет изменять свое положение от нуля до бесконечности. (рис.2.1)

х2

50  А

35

                         F        В

                                                   С

10

  0                               20 Е                 35Д        х1

рис. 2.1

Предположим, что предприятие имеет общий  расход ресурсов в 10 тыс.руб, вместо заданного в исходных данных 2350 тыс.руб, т.е. первое ограничение исходной задачи (2.1) будет выглядеть как 35x1 + 70x2≤10   тогда область допустимых решений задачи будет представлена треугольником, образованным этой прямой и осями координат. Для определения оптимального решения на таком треугольнике можно использовать градиент целевой функции. Оптимальное решение в данном случае (рис 2.1) будет  точка Е с координатами x1 =20; x2=0.

Решение двойственной задачи для данной ситуации найдем по составленным выше условиям «дополняющей нежесткости». Из группы условий (1.6), так как 2000-50x₁-40x₂=2000-50×20-40×0=1000>0; 2800-80x1-35x2=2800-80×20-35×0=1200>0, следует, что амортизация и материалы не лимитируют производственную программу (пассивные ограничения), т.е. находится в избытке, а значит u2=u3=0.

Из группы условий (1.7) следует, что, если первый продукт выпускается по оптимальной производственной программе, т.е. x1=20  то должно выполняться равенство

35u1+50u2+80u3-10=0

Из последнего уравнения с учетом u2=u3=0 получим u1=2/7.

При повышении лимита потребления заработной платы треугольник, отражающей ОДР, будет увеличиваться (рис. 2.2).

х2

50

35 А

                                  В

                        F

                                               С  

  0                                                    35 Д      х1

рис.2.2

Оптимальное решение в данном случае (рис 2.2) будет  точка Д с координатами x1 =35; x2=0  и точка С с координатами x1=840/29; x2=400/29 

Для расчета расхода сырья на программу (Д) подставим ее координаты в левую часть ограничения по заработной плате, а именно:35×35 + 70×0=1225

Значение дохода в точке Д будет равно: 10×35+15×0=350 тыс.руб

х2

50

35  А

                                     F

25                                  В

15                                                    С

  0                                  20                       35 Д     х1

рис.2.3

Для расчета расхода сырья на программу (С) подставим ее координаты в левую часть ограничения по заработной плате, а именно: 35×840/29+70×400/29=57400/29=1979

Значение дохода в точке С будет равно: 10×840/29+15×400/29=14400/29=496 тыс.руб

Так как используется уже 2 продукта, то  должны выполняться равенства:

35u₁+50u₂+80u₃-10=0

70u₁+40u₂+35u₃-15=0

Из этих двух уравнений с учетом u2=0 перейдём к решению следующей системы:

35u₁+80u₃=10

70u₁+35u₃=15

Откуда u₁=34/175

х2

50А1                                              

                                               F

35А

25                                  В

15                                                С

  0                                20                    35Д               х1

рис. 2.4.

Из этого рисунка следует, что ограничение по заработной плате можно двигать до т.А1(0;50).

При этом u₁=1/6, 35×0+70×50=3500 тыс. руб и доход 10×0+15×50=750 тыс.руб.

Таблица 2. Функция предельной эффективности ресурса «заработная плата».