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

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

  Составим  математическую модель задачи. Для  этого введем переменные: x₁ – количество комплекса «Здоровье» (гр.), x₂ – количество комплекса «Долголетие» (гр.), необходимое для профилактического приема. Целевая функция выражает суммарную стоимость витаминных комплексов, которая должна быть минимально возможной  

  f(x)= 5 x₁ + 4 x₂ ® min (1.7)

  Ограничения, описывающие выполнение норм по витаминам, имеют вид:

 

  По  витамину V₁: 3x₁ + x₂ ³ 9,  (1.8)

  По  витамину V₂: x₁ + 2x₂ ³ 8, (1.9)

  По  витамину V₃: x₁ + 6x₂ ³12.  (1.10)

  При этом переменные должны быть неотрицательны: x_j ³ 0, j = 1, 2.

  Снова начнем решение с построения множества  планов X, для чего проведем граничные прямые, уравнения которых получаются при замене в ограничениях знаков неравенств на равенства  

  p₁: 3 x₁ + x₂ = 9,

  p₂: x₁ + 2 x₂ = 8,

  p₃: x₁ + 6 x₂ = 12.

  Подставляя  координаты точки (0,0) в неравенства (1.8)-(1.10) видим, что начало координат им не удовлетворяет и, следовательно, не входит в множество планов Х. Поэтому штриховки направлены выше и правее граничных прямых. Выделяя точки, удовлетворяющие всем неравенствам и условиям неотрицательности, получаем множество планов, изображенное на рис. 1.2. В данном примере оно не ограничено.

  

  Рис. 1.2

  Изобразим целевую функцию (1.7) с помощью  линий уровня. Для этого достаточно построить целевой вектор c = (5, 4) и перпендикулярно ему провести несколько прямых на множестве Х. Поскольку целевой вектор указывает направление возрастания целевой функции, а в задаче о рационе требуется найти ее минимум, то для нахождения оптимального решения будем перемещать линию уровня параллельно самой себе по множествуХ в направлении, противоположном целевому вектору.

    

  Рис. 1.3  

  Последней точкой множества планов, через которую  еще проходит линия уровня будет  точка пересечения прямых p₁ и p₂. Решая систему уранений (рис. 1.3).  

  3 x₁ + x₂ = 9

  x₁ + 2 x₂ = 8

  получим оптимальный план x₁* = 2, x₂* = 3. Минимальное значение целевой функции при этом будет равно  

  f(x*) = 5∙2 + 4∙3 = 22.

  Следовательно, самый дешевый набор для профилактического  приема состоит из 2 гр. комплекса А и 3 гр. комплекса В, и его стоимость равна 22 руб.

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

  ·                   изображается допустимый многоугольник  – пересечение полуплоскостей, являющихся решениями соответствующих неравенств;

  ·                   изображается целевой вектор  ;

  ·                   через допустимое множество проводится перпендикуляр к целевому вектору – это линия уровня целевой функции;

  ·                   путем перемещения линии уровня параллельно самой себе в направлении целевого вектора до тех пор, пока   не окажется по одну сторону от перемещаемой прямой, визуально определяется точка (или точки) максимума;

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

  Замечание. Для определения точки минимума следует перемещать изолинию против направления целевого вектора.

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

  Бесконечное множество оптимальных  планов. На рис.1.4 целевая функция принимает одно и то же максимальное значение в любой точке отрезка AB, соединяющего две вершины множества планов Х. Такая ситуация возникает, если линии уровня параллельны граничной прямой.

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

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

        

  Рис. 1.4               Рис. 1.5               Рис. 1.6

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

2.1 Идея симплекс-метода

  Рассмотрим  универсальный метод решения  канонической задачи линейного программирования

   ,  ,  ,

  с n переменными и m ограничениями-равенствами, известный как симплекс-метод. 

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

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

  Перебор всех угловых точек сопряжен с  большими вычислительными затратами  и поэтому не эффективен. В 1947 году Дж. Данциг предложил упорядоченную  процедуру перебора угловых точек, при которой для нахождения оптимального решения достаточно исследовать  лишь небольшую их часть. Эта процедура  называется симплекс-методом.

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

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

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

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

  ·                   шаг 0. Определение начального базиса   и соответствующей ему начальной угловой точки (базисного плана)  .

  ·                   шаг 1. Проверка текущего базисного плана на оптимальность. Если критерий оптимальности выполнен, то план оптимален и решение закончено. Иначе переход на шаг 2.

  ·                   шаг 2. Нахождение переменной, вводимой в состав базисных. (Из условия увеличения целевой функции).

  ·                   шаг 3. Нахождение переменной, исключаемой из состава базисных переменных (Из условия сохранения ограничений задачи).

  ·                   шаг 4. Нахождение координат нового базисного плана (смежной угловой точки). Переход на шаг 1.

  Повторяющиеся шаги 1–4 образуют одну итерацию симплекс-метода.

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

  Определение. Будем говорить, что каноническая задача ЛП имеет "предпочтительный вид", если

  1.                правые части уравнений  ,  .

  2.                матрица условий   содержит единичную подматрицу размера 

   .

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

  Пример 2.1.

  

  

  Матрица условий A и вектор правых частей ограничений b имеют вид 

   ,  ,

  а целевой вектор с = (1, -3, 0, 4, 2).

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

  Следовательно, выбирая в качестве базисных переменных x₁, x₃, x₅^, и полагая в системе уравнений x₂ = x₄ = 0 (небазисные переменные), немедленно находим x₁ =10, x₃ =20, x₅ = 8, так что начальный базисный план x⁰ = (10, 0, 20, 0, 8). Видим, что значения базисных переменных равны правым частям ограничений. Из этого понятно требование положительности правых частей b_i.

  В дальнейшем, базисные переменные будем  объединять в вектор x_Б.

  Таким образом, в канонической задаче предпочтительного  вида в качестве начальной базисной матрицы берется единичная подматрица A_Б = E, а соответствующие ей базисные переменные равны правым частям ограничений: 

  x_Б = b.

  Для базисного плана такого вида может  быть сформулирован достаточно простой  для проверки критерий оптимальности. Введем величины  

  ∆_j = < с_Б, A_j > – c_j, j = 1,...,n, (2.1)

  где с_Б – вектор из коэффициентов целевой функции при базисных переменных x_Б, A_j –j-й столбец матрицы условий, c_j – j-й коэффициент целевой функции. Разности ∆_jназываются симплексными разностями или симплексными оценками.

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

  Применим  данный критерий для проверки на оптимальность  базисного плана x⁰ = (10, 0, 20, 0, 8) из примера 2.1.

  Так как в этом плане вектор базисных переменных x_Б =(x₁, x₃, x₅), то с_Б = (c₁, c₃,c₅) = (1, 0, 2).

   .

  Следовательно,

  ∆₁ = < с_Б, A₁ > – c₁ = 1∙1 + 0∙0 + 2∙0 – 1= 0,

 

  ∆₂ = < с_Б, A₂ > – c₂ = 1∙3 + 0∙1 + 2∙2 – (-3) = 10,

  ∆₃ = < с_Б, A₃ > – c₃ = 1∙0 + 0∙1 + 2∙0 – 0= 0,