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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

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

Пример 1  

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

Прибыль от реализации одной  единицы товара первого вида составляет 2 усл. ед., второго вида – 3 усл. ед.

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

           Таблица 2 

 

Ресурсы	Норма затрат ресурсов на товары		Общее   количество   ресурсов
	1 -го вида	2-го вида
1 2 3 4	2 1 4 0	2 2 0 4	12             8 16 12

 

   

Решение

Это задача составления плана  реализации товара  при n=2, m=4.    

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

                                    (16)

В модели управляющие переменные х₁,х₂ – количество реализуемых изделий первого и второго вида, соответственно, Р – прибыль. Система неравенств включает ограничения по ресурсам. Количество ресурсов на реализацию товаров первого и второго вида не превышает общего количества ресурсов каждого типа.

Графическое решение.

Построим в плоскости X₁OX₂ область допустимых решений. Каждое неравенство системы (3.3.2) определяет в плоскости X₁OX₂полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением. Построим прямые (см. рис. 1)

   

Рассмотрим точку с  координатами х₁ =0; х₂ =0. Подставив их в первое неравенство, получаем 0≠12 – верно, следовательно, искомая полуплоскость лежит ниже прямой 2x₁ +2x₂ = 12; остальные полуплоскости находятся аналогичным образом.

Область OABCD – область допустимых решений задачи. 

Для нахождения максимального  значения Р проверим граничные. Точки из области решений.

Построим две линии уровня (рис. 1):

2x₁ + 3x₂ = 6;

2x₁ +3х₂=13.

Функция Р возрастает в направлении вектора-нормали   = (2,3) следовательно, минимум находится в точке (0.0). Максимум определяем, передвигая нашу линию уровня в направлении вектора   параллельно самой себе до тех пор, пока хотя бы одна ее точка будет принадлежать области допустимых решений.

В данном случае это точка: х₁ = 4, х₂ = 2;

при этом P=2*4+3*2=14.

Таким образом, для получения  максимальной прибыли в размере 14 усл. ед. надо продать 4 изделия первого  вида и 2 изделия второго вида. 

 

Рис. 1. Графический метод решения задачи ЛП 

 

Изложенный выше графический  метод применим для решения задач  линейного программирования следующего вида: 

 

                                      (17)

                                               (18) 

 

Алгоритм решения ЗЛП  графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (2.4), и строят их на плоскости x₁ox_3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (2.4).

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

4)  Определяют направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами. Можно построить вектор-нормаль  , его направление показывает направление возрастания функции f, и противоположном направлении функция убывает. Можно просто построить две линии уровня функции f = K₁; f = K₂; (K₁, K₂ – произвольные константы, K₁  K₂), и по их расположению определить направление возрастания (убывания) функции.

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

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

Возможны следующие  варианты областей допустимых решений (рис. 2): 

 

Рис. 2. Варианты областей. а – область допустимых решений  
– замкнутое множество (многоугольник); б – область допустимых решений – открытое множество; в – область допустимых решений – пустое множество (система ограничений (18) несовместна);  
г – область допустимых решений состоит из единственной точки А

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

 

3. Основная задача  линейного программирования (ОЗЛП)

В произвольной форме линейная математическая модель или задача линейного программирования имеет вид (1)–(4).

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

Для применения симплекс-метода задачу следует записать в канонической форме:  

                            (19)

                          (20)

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

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

1) Если требуется найти минимум f, то заменяя f на -f переходят к задаче максимизации, так как min(f)= -max(-f).

2) Если ограничение содержит  неравенство со знаком  , то от него переходят к равенству, добавляя в левую часть ограничения дополнительную неотрицательную переменную. 

 

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

4) Если в задаче какая-либо  из переменных произвольна, то  от нее избавляются, заменяя  ее разностью двух других неотрицательных  переменных. Например, для произвольной  переменной x_k, x_k = x’_k-x”_k, где x’_kx”_k ³ 0, x”_k ³ 0.

Пример 2

Записать в канонической форме задачу                                          

Решение.

f₁= – f= – 5x₁ – 2x₂ +3x₃

Вычитая дополнительную неотрицательную  переменную х₄ из левой части первого неравенства, переходим к равенству.

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

Произвольную переменную x₃ заменяем разностью двух неотрицательных переменных x₃ = x₆ – x₇

Окончательно получаем каноническую форму записи

Задача (19)–(20) называется основной задачей линейного программирования (ОЗЛП).

ОЗЛП не всегда имеет решение.

Во-первых,  уравнения (20) могут оказаться несовместными.

Во-вторых, уравнения (20) могут оказаться совместными не в области неотрицательных решений.

В третьих, допустимые решения (10), (20) существуют, но среди них нет оптимального: функция f не ограничена в области допустимых решений.

Предположим, что все уравнения (20) линейно независимы, т. е. выражают независимые друг от друга условия задачи. Если это не так, то лишние уравнения надо просто исключить. Задачу (19)–(20) имеет смысл решать, когда число уравнений в системе ограничений (20) меньше числа входящих в них неизвестных: т < п. В противном случае, если т = п, то система (2.2) имеет единственное решение, и задача максимизации функции (19) не имеет смысла; если т > п, то система (20) переопределена и в общем случае не имеет решений.

Если т < п, то система (2.2) имеет бесконечное множество решений и среди них можно выбрать оптимальное, доставляющее максимум функции (3.19). 

 

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

Симплекс-метод является методом направленного перебора решений системы (20). Каждое следующее решение улучшает значение целевой функции. Симплекс-метод включает два этапа:

1) Определение начального  решения, удовлетворяющего ограничениям (20).

2) Последовательное улучшение  начального решения и получение оптимального решения задачи (19)–(20). 

Любое решение задачи линейного  программирования называется опорным  планом задачи.

Система (20) содержит т линейно независимых уравнений, и их число меньше числа неизвестных, входящих в систему, следовательно, систему (20) можно разрешить относительно т неизвестных, например x₁,x₂,…x_m, выразив их через остальные неизвестные    

Коэффициенты a_ij,b_i,  ,   в полученной системе, естественно, отличны от коэффициентов системы (20), но для простотыобозначены той же буквой.

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

После указанных преобразований задача (19)–(20) записывается в следующем виде: 

                                    (21)

                                  (22)

Алгоритм решения  системы (21)–(22) симплекс-методом

Шаг 1. Получение начального решения.

Выбираются т переменных, называемых базисными и обладающих следующим свойством: они входят с коэффициентом 1 только в одно уравнение и с коэффициентом 0 в остальные уравнения системы (22).                                                                                                                                                                              

Остальные п – т переменных называют свободными.

Все свободные переменные полагаются равными 0, а базисные переменные — равные правым частям соответствующих ограничений системы (22).

Пусть т базисных переменных — это переменные x₁, x₂,...,x_m (в противном случае переменные всегда можно перенумеровать).Тогда начальное решение Х₀ имеет следующий вид:

Х_о ={x₁= b₁,х₂=b₂,...,х_т = b_m,x_m+l = 0,...,х_n = 0}.

Если все b_i   0, то начальное решение является допустимым. Переходят к шагу 3. В противном случае используют алгоритм нахождения начального решения.

Шаг 3. Выражение функции f только через свободные переменные.

Значения коэффициентов c_j,  , естественно, отличны от значений коэффициентов в формуле (21), но для простоты обозначены той же буквой.)