Линейное программирование. Метод Гаусса

 
 
 

     По  данному условию сформулируем задачу линейного программирования.

     Обозначим: x1 - количество выпускаемых ежедневно  хоккейных клюшек, x2 - количество выпускаемых  ежедневно шахматных наборов.

     Формулировка  ЗЛП:  = 2x1 + 4x2 → max;  

                              4x1 + 6x2 ≤ 120,

                                      2x1 + 6x2 ≤ 72,

                                      x2 ≤ 10;

                        x1 ≥ 0,   x2 ≥ 0.  

     Подчеркнем, что каждое неравенство в системе  функциональных ограничений соответствует  в данном случае тому или иному  производственному участку, а именно: первое - участку А, второе - участку В, третье - участку С.  

2.2 Транспортная задача. 

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

     Три поставщика одного и того же продукта располагают в планируемый период следующими его запасами: первый – 120 условных единиц, второй – 100 условных единиц, третий – 80 условных единиц. Этот продукт должен быть перевезен к трем потребителям, потребности которых равны 90, 90 и 120 условных единиц, соответственно.

      Обычно  начальные условия транспортной задачи записывают в так называемую транспортную таблицу (см. таблицу 2.3). В ячейках таблицы в левом верхнем углу записывают показатели затрат (расходы по доставке единицы продукта между соответствующими пунктами), под диагональю каждой ячейки размещается величина поставки xij (т.е. xij – количество единиц груза, которое будет перевезено от i-го поставщика j-му потребителю).

      

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

     Сформулируем  ЗЛП:  = 7x11 + 6x12 + 4x13 + 3x21 + 8x22 + 5x23 + 2x31 + 3x32 + 7x33 → min;  

      x11 + x12 + x13 = 120,

   x21 + x22 + x23 = 100,

      x31 + x32 + x33 = 80,

      x11 + x21 + x31 = 90,

      x12 + x22 + x32 = 90,

      x13 + x23 + x33 = 120;

             

      xij ≥ 0. 

     2.3 Геометрическое решение задач линейного программирования 

     Если  система ограничений задачи линейного  программирования представлена в виде системы линейных неравенств с двумя  переменными, то такая задача может  быть решена геометрически. Таким образом, данный метод решения ЗЛП имеет очень узкие рамки применения.

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

      Геометрический (или графический) метод предполагает последовательное выполнение ряда шагов. Ниже представлен порядок решения задачи линейного программирования на основе ее геометрической интерпретации.

      1. Сформулировать ЗЛП. 

      2. Построить на плоскости {х1, х2} прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств.

      3. Найти полуплоскости, определяемые  каждым из ограничений задачи.

      4. Найти область допустимых решений. 

      5. Построить прямую c1x1 + c2x2 = h, где h - любое положительное число, желательно такое, чтобы проведенная прямая проходила через многоугольник решений.

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

      7. Определить координаты точки  максимума (минимума) функции и  вычислить значение функции в этой точке.

     Далее рассмотрим пример решения ЗЛП графическим  методом. Для этого воспользуемся  представленной выше задачей о хоккейных  клюшках и шахматных наборах.

      1. Выше уже приводилась формулировка  задачи, здесь нам остается лишь  повторить ее:  = 2x1 + 4x2 → max;  

      4x1 +6x2 ≤ 120,

      2x1 +6x2 ≤ 72,

      x2 ≤ 10; 

      x1 ≥ 0,   x2 ≥ 0. 

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

      

      3. Штрихи на прямых указывают полуплоскости, определяемые ограничениями задачи.

      4. Область допустимых решений включает  в себя точки, для которых  выполняются все ограничения  задачи. В нашем случае область  представляет собой пятиугольник (на рисунке обозначен ABCDO и  окрашен синим цветом).

      5. Прямая, соответствующая целевой  функции, на рисунке представлена  пунктирной линией.

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

      7. Осталось вычислить координаты  точки С. Она является точкой пересечения прямых (1) и (2). Решив совместно уравнения этих прямых, найдем: , . Подставляя найденные величины в целевую функцию, найдем ее значение в оптимальной точке .

      Таким образом, для максимизации прибыли  компании следует ежедневно выпускать 24 клюшки и 4 набора. Реализация такого плана обеспечит ежедневную прибыль в размере $64.

3. Симплекс-метод 

      Этот  один из первых специализированных методов  оптимизации, нацеленный на решение  задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс-метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных таблицы.

 

Задача  линейного программирования имеет  вид:

Х1  ≥ 0 , Х2 ≥ 0 , Х3  ≥ 0 , (0)

Х1  / 200 + Х2 / 300 + Х3   / 120 ≤ 100 , (1)

Х1  / 300 + Х2 / 100 + Х3   / 100 ≤ 100 , (2)

Х1 / 200 ≤ 100 , (3)

Х2 / 120 ≤ 100 , (4)

Х3 / 80 ≤ 100 , (5)

F = 15 Х1 + 12 Х2  + 14 Х3 → max .

 Здесь:

(0) - обычное  в экономике условие неотрицательности  переменных,

(1) - ограничение  по возможностям штамповки (выраженное  для облегчения восприятия в процентах),

(2) - ограничение  по возможностям отделки, 

(3) - ограничение  по сборке для кухонь,

(4) - то  же для кофемолок, 

(5) - то  же для самоваров (как уже  говорилось, все три вида изделий  собираются на отдельных линиях).

Наконец, целевая функция F - общая прибыль предприятия.

      F = 15 Х1 + 12 Х2  + 14 Х3 → max .

     Х1  / 200 + Х2 / 300 + Х3   / 120 ≤ 100 ,

     Х1  / 300 + Х2 / 100 + Х3   / 100 ≤ 100 ,

     Х3 / 80 ≤ 100 .

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

       В соответствии с симплекс-методом  введем т.н. "свободные переменные" Х4, Х5, Х6, соответствующие недоиспользованным  мощностям, т.е. от системы неравенств  перейдем к системе уравнений:

Х1  / 200 + Х2 / 300 + Х3   / 120 + Х4  = 100 ,

Х1  / 300 + Х2 / 100 + Х3   / 100 + Х5 = 100 ,

Х3 / 80 + Х6  = 100 ,

15 Х1 + 12 Х2  + 14 Х3   = F .

     У этой системы имеется очевидное  решение, соответствующее одной  из вершин многогранника допустимых значений переменных:

Х1 = Х2  = Х3  = 0, Х4  = Х5 = Х6  = 100,  F = 0. 

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

       В соответствии с симплекс-методом  выбираем переменную, которая входит  в целевую функцию F с самым большим положительным коэффициентом. Это Х1.

        Сравниваем частные от деления  свободных членов в первых  трех уравнениях на коэффициенты  при только что выбранной переменной  Х1: