Математическое моделирование

Х₂

 

                                             

                                                        Х₁

                

                           Рис.1                                        

       Рассмотрим линию уровня линейной функции F, то есть линию, вдоль которой эта функция (3) принимает одно и тоже фиксированное значение. Уравнение линии уровня c₁x₁ + c₂x₂ = L, (4)  где L – некоторое фиксированное значение (уровень). При изменении значения уровня L уравнение (4) представляет собой семейство параллельных прямых. Вектор  С (с₁, с₂) – градиент функции F, он перпендикулярен  ко всем этим прямым и показывает направление возрастания уровня L.

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

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

      Из  рис. 1 видно, что в крайнем положении  линия уровня переходит через точку D. При дальнейшем её перемещении в том же направлении она уже не будет иметь общих точек с областью допустимых решений.

      Таким образом, искомое максимальное решение, которое графически соответствует  координате точки D можно найти путём совместного решения системы двух уравнений, соответствующих граничным прямым CD и DE. Если при тех же исходных данных требовалось бы достичь минимума функции F, то, очевидно, линию уровня пришлось бы перемещать в направлении противоположном вектору С. В этом случае оптимальное решение, (минимум) определялось координатами точки А.

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

Х₂                                             Х₂                                                                                Х₂

 

                                              Х₁                                                    Х₁                                          Х₁  

      Рис. 2                                        Рис. 3                                                           Рис. 4 

      На  Рис. 2 оптимальное решение (минимум) достигается в двух вершинах выпуклого  многоугольника и, следовательно, в  любой точке отрезка AE. Говорят, что в этом случае задача имеет альтернативный оптимум, т.е. бесчисленное множество оптимальных решений. Линии уровня целевой функции в этом случае оказались параллельны одной из сторон замкнутого выпуклого многоугольника допустимых решений.

     На  Рис. 3 ОДР является неограниченным выпуклым многоугольником (многоугольной областью). В этом случае оптимальное значение целевой функции существует, если целевая функция стремится к минимуму (ограничена снизу). И не существует при стремлении к максимуму (не ограничена сверху).

      На  Рис. 4 ОДР не ограничена и целевая функция не ограничена, следовательно, ЗЛП не имеет решений.

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

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

      Недостатки  геометрического  метода:

     Во 1-ых, возможны «технические» погрешности, которые неизбежно возникают  при приближённом построении графика.

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

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

§ 5.  Симплексный метод.

5.1.    Симплексный метод  с естественным  базисом. 

      Впервые СМ был предложен американским учёным ДЖ. Данцингом в 1949 году. Однако, ранее, в 1939г. идеи этого метода  были разработаны  русским  учёным Л.В.Канторовичем.

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

     Для реализации симплекс метода необходимо знать три основных элемента:

1. способ определения какого-либо первоначального, допустимого (неотрицательного) базисного решения задачи;
2. правило перехода к лучшему (точнее не худшему) решению;
3. критерий проверки оптимальности найденного решения.

     Мы  рассмотрим две разновидности систем ограничений ЗЛП: с «естественным  базисом» и с «искусственным базисом».

     Для использования симплекс метода с естественным базисом ЗЛП должна быть приведена к каноническому виду, причём матрица системы уравнений должна содержать единичную подматрицу размерностью (m x n). В этом случае очевиден начальный опорный план.

     Пусть имеем ЗЛП. (1) Целевая функция F(X) = с₁х₁ + с₂х₂ + . . . +с_nx_n ® max при следующих условиях:

      a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

      a₂₁x₁ + a₂₂x₂ + … + a_2nx_n = b₂

     …………………………………..

     a_m1x₁ + a_m2x₂ +… + a_mnx_n = b_m

      x_j ³ 0, j = 1, n

Пусть для определённости матрица  системы (2) имеет вид:

         1   0   …   0   a_1,m+1   …   a_1n

                                                      0   1   …   0   a_2,m+1   …   a_2n

           ……………………………….

           0   0   …   1   a_m,m+1   …   a_mn 

     Тогда первые m переменных примем за базисные х₁, х₂, …, х_n – базисные, оставшиеся n-m переменных x_m+1, …, x_n – свободные. Выразим базисные переменные через свободные и получим общее решение системы (2).

 x₁ = b₁ – (a_1m+1x_m+1 + … + a_1nx_n)

 x₂ = b₂ – (a_2m+1x_m+1 + … + a_2nx_n)

      ………………………………………

      x_m = b_m – (a_mm+1x_m+1 + … + a_mnx_n)

      Если  в решении (3) b₁ ³ 0,  …, b_m ³ 0, то такое решение называется допустимым и соответствующее базисное решение также является допустимым и имеет вид:

      X₀ = (b₁, b₂, …, b_m, 0, 0, …, 0) - первоначальный опорный план.

     По  поводу возможности получения из системы (2) общего решения вида (3) заметим следующее:

      Замечание. Если система (2) совместна, то с помощью метода Гаусса всегда можно получить какое-либо решение вида (3), то есть выделить базис неизвестных           Б: {x₁, x₂, …, x_m}. Весь вопрос в том, является ли этот базис допустимым, то есть будут ли все свободные члены в правых частях уравнений (3) неотрицательными.

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

      После того, как выделен допустимый базис  неизвестных Б: {x₁, x₂, …, x_m} (3), заменим в выражении (1) для целевой функции каждую базисную переменную ее выражением через свободную. В итоге, функция (1) запишется только через свободные переменные:

      F = с₁ (b₁ – (a_1m+1x_m+1 + … + a_1n x_n)) + … + с_m(b_m – (a_mm+1x_m+1 + … + a_mnx_n)) + с_m+1x_m+1 + … + с_nx_n = g₀ + g_m+1x_m+1 + … + g_nx_n    (4).

      В выражении (4) переменные x_m+1, …, x_n – свободные, то есть они могут принимать любые неотрицательные значения. Изменяя значения свободных переменных значение целевой функции тоже будет меняться. Возможны три случая:

     1. Все коэффициенты при свободных переменных в выражении для целевой функции (4) неположительны: то есть g_m+1£ 0, …, g_n £ 0. Тогда для любого неотрицательного решения системы (2) произведения g_m+1x_m+1, …, g_nx_n тоже будут неположительны g_m+1x_m+1£ 0, …, g_nx_n £ 0. Значит

F = g₀ + g_m+1x_m+1 + … + g_nx_n £ g₀. Таким образом, Fmax =g₀ и базисное решение X₀ = (b₁, b₂, …, b_m, 0, 0, …, 0) является оптимальным. Задача решена.