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

Содержание

I. Цель работы……………………………………………………………………..3

II.     1. Решение задачи графическим методом……………………………...4-10

2. Экономический анализ задачи с использованием графического метода…………………………………………………………………………11-14

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

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

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

6. Исследование предельной эффективности с помощью симплекс-метода…………………………………………………………………………..26

I.Цель работы

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

Условия задачи: предприятие осваивает выпуск 2-х новых изделий. Расходы по заработной плате, амортизационным отчислениям, материалам, лимиты, вы­деленные предприятию, и прибыль на одно изделие приведены ниже в таблицах.

Необходимо составить такой  план производства, который давал бы предприятию максимальную прибыль.

II.      1. Решение задачи графическим методом.

Составим математическую модель задачи.

Целевая функция будет иметь вид: F(x) =10x1+15x2 max

при ограничениях:          35x1+70x2≤2450

                                          50x1+40x2≤2000                                        (1.1)

                                          80x1+35x2≤2800

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

35x1+70x2=2450.

х1=70 (х2=0, 35х1=2450, х1=2450/35)

х2=35 (х1=0, 70х2=2450, х2=2450/70)

х2

35

0                                                         70               х1

рис.1.1 ОДР по заработной плате

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

50x1+40x2=2000

х1=40 (х2=0, 50х1=2000, х1=2000/50)

х2=50 (х1=0, 40х2=2000, х2=2000/40)

х2

50

  0                          40                                   х1

рис.1.2 ОДР по амортизации

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

80x1+35x2=2800

х1=35 (х2=0, 80х1=2800, х1=2800/80)

х2=80 (х1=0, 35х2=2800, х2=2800/35)

х2

80

  0                                   35                        х1

рис.1.3 ОДР по материалам

Следующим шагом нужно выделить общую часть обозначенных штриховкой полуплоскостей или, другими словами, найти их пересечение. На рис. 1.4 заштрихованный многоугольник представляет собой все множество точек, координаты которых обращают в истинные утверждения все ограничения и граничные условия модели. Это означает, что область допустимых решений задачи ЛП построена.

х2

80

50

35    А

                         В

                                        С

                                                         Д

  0                                                     35       40                                                 70     х1                    

рис. 1.4 Нахождение общей ОДР задачи

Выделенному многоугольнику (рис. 1.4) области допустимых решений соответствуют шесть опорных решений – шесть угловых точек: О (0;0); А(0;35); В (20;25); С(840/29;400/29); Д (35;0).

Координаты точки С(840/29;400/29) можно найти, вычислив координаты точки пересечения прямых по материалам и амотризации, для чего нужно решить систему уравнений:

                                          50x1+40x2=2000                                       

                                          80x1+35x2=2800

Откуда х1=840/29, х2=400/29

Далее подставляем координаты каждой угловой точки в целевую функцию и определяем максимальный доход:

F(А)=10×0+15×35=525

F(В)=10×20+15×25=575

F(С)=10×840/29+15×400/29=14400/29=497

F(Д)=10×35+15×0=350

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

х2

35  А

                В

              С

  0                                         20                      35  Д            х1

Рис.1.5. Нахождение оптимального решения

Под линией уровня целевой функции понимается геометрическое место точек, для координат которых целевая функция имеет постоянное числовое значение (рис. 1.6).

Например, уравнение  линии уровня 350 будет иметь вид: 10x1+152=350 или уравнение линии уровня 525 - 10x1+15x2=525 (соответственно: прямая 1) и 2), рис.1.6) и т.д.

Под градиентом целевой функции понимается вектор с началом в текущей точки плоскости и координаты, которые соответствуют коэффициентам при неизвестных в целевой функции (х1=10; х2=15). (рис.1.6)

х2

              F(10;15)

35    А

              В

              2)              С

              1)

           0                                                                35   Д                  х1

Рис.1.6. Нахождение оптимального решения с помощью линий прибыли и вектора-градиента

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

Отсюда оптимальным решением задачи являются: X1=20; X2=25; F(x)=575 рублей. 

2. Экономический анализ задачи с использованием графического метода.

Проведём экономический анализ, рассмотренный выше задачи по производству изделий.

Математическая модель задачи имеет вид

                                        F (x) =10x1+15x2→max

при ограничениях:

          35x1+70x2≤2450 (ограничение по заработной плате) (1.2)

          50x1+40x2≤2000 (ограничение по амортизации) (1.3)

          80x1+35x2≤2800  (ограничение по материалам) (1.4)           

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

  Рассмотрим увеличение активного ресурса ограничения (1.2) по заработной плате (рис.1.7)

х2.

50    А1

35     А

25                                     В

                                                             С

   0                                                        35 Д                  х1

рис.1.7 Расчет предельно допустимого запаса заработной платы

Подставляя координаты точки А1 в неравенство (1.2), получим предельно допустимый запас заработной платы:

35x1+70x2=35×0+70×50=3500 тыс.руб

При этом величина дохода составит:

F(x)=10×0+15×50=750 тыс.руб

Рассмотрим увеличение ограничения активного ресурса по амортизации (рис.1.8)

х2

35   А

              1)

                              В              2)

                                           М   

                                             С

              3)

  0                                                   35Д           х1

рис.1.8 Расчет предельно допустимого запаса амортизации

При перемещении прямой (2) параллельно самой себе вправо до пересечения с прямыми  (1) и (3), в точке М ограничение (1.3) будет оставаться активным. Точку М определим как точку пересечения прямых:

35x1+70x2=2450

80x1+35x2=2800 

Откуда координаты точки М(25,2;22,4)

Предельно допустимый запас амортизации:

50x1+40x2=50×25,2+40×22,4=2156 тыс.руб

При этом величина дохода составит:

F(x)=10×25,2+15×22,4=588 тыс.руб

Рассмотрим ограничение пассивного ресурса по материалам (рис.1.9).

х2

35     А

              В

                                                           С

   0                                                              35  Д                         х1      

рис.1.9 Расчет предельного изменения запасов материалов.

Предельное изменение запаса  материалов:

80x1+35x2=80×20+35×25=2475

При этом величина дохода составит:

F (x)=10×20+15×25=575

Таким образом, заработную плату можно увеличить на 1050 тыс.руб. (3500-2450), амортизацию – на 156 тыс.руб. (2156-2000), а материалы уменьшить на 325 тыс. руб (2800-2475).

Проведем анализ задачи по пределам возможного изменения  коэффициентов целевой функции, т.е. по диапазону цен на изделия, при котором не происходит изменения  оптимального решения.

Изменение коэффициентов целевой функции оказывает влияние на наклон линии уровня (рис. 2.). Угловой коэффициент линии уровня:

                                                  K =c1/c2 =c1/15

Если по условию задачи c2 = 15, то c1 можно увеличивать до совпадения линии уровня с прямой 1.3. Угловой коэффициент линии уровня:

Угловой коэффициент прямой 1.3: K (1) =5/4.

Так как прямые совпадают, K=K (1), то c (1) max=18, 75

х2

35    А

                                           В

              F(10;20)                                    

                          F(10;15)                      С

                          F(18,75;15)                                                  

    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. Функция предельной эффективности ресурса «заработная плата».