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

Содержание

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)