Переход от стандартной формы задачам линейного программирования (злп) к канонической

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

Рассмотрим, каким образом можно перейти от стандарт­ной форме записи к канонической. Для осуществления дан­ного перехода нужно в каждое из m неравенств системы ограничений ввести m дополнительных неотрицательных переменных: х_п+ь х_п+2, х_п+га, тогда система ограниче­ний примет вид:

(4)

здесь x_n+1, x_n+2,...x_n+m — выравнивающие балансовые пере­менные, где x_j  0, где (j = I ...n+m). Добавив эти балансовые переменные в неравенства, превращаем их в уравнения.

Если же в стандартной форме требовалось минимизиро­вать целевую функцию, то, заменив ее знак на «-», полу­чим:

(5)

Таким образом, с помощью представленных преобразо­ваний мы перешли от стандартной формы ЗЛП к ее кано­нической форме.

Для решения этой задачи необходимо найти такой век­тор Х=(х_1, х₂,x₃,…,х_n+m), который удовлетворял бы системе ограничений (4) и при котором целевая функция (5) принимала бы максимальное значение.

Пример

Пусть задача линейного программирования задана в стандартной форме: F = 2х, + Зх₂ —> max при ограничениях:

Приведем эту задачу к каноническому виду.

Обратим имеющуюся систему неравенств в равенства, водя для этого в каждое из них соответствующую неотрицательную переменную:

В данном примере все дополнительные переменные вве­дены со знаком «+», так как рассматриваемые неравенства имеют знак .

(Необходимо заметить, что в том случае, если неравен­ства имели бы знак , переменные нужно было бы вводить со знаком «-».)

Вопросы для самоконтроля:

1.Примеры задач линейного программирования (ЛП).

2.Формулировка общей задачи математического программирования.

Рекомендуемая литература:

1.Акулич И.Л. Математическое программирование в примерах и задачах. — М.: Высш. шк., 1986.

2.Алексеев В.М., Галеев Э.М., Тихомиров В.М. Сборник задач по оптимизации. М.: Наука, 1984.

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

Содержание лекционного занятия:

• ЗЛП имеет единственное решение

• ЗЛП имеет альтернативный оптимум

• ЗЛП имеет минимум и не имеет макси­мума

• ЗЛП не имеет решения

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

Пример

Найти решение X*=(x*₁,x*₂), которое удовлетворяет системе неравенств:

(1)

условиям неотрицательности переменных: x₁0, x₂0, (2)

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

f = c₁ x₁+с₂х₂ —»max(min). (3)

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

Применение геометрического метода предполагает ис­пользование нескольких этапов.

На первом из них в системе координат Х₁ ОХ₂ строится область допустимых решений задачи (ОДЗ). Для этого каждое из неравенств системы (1) заменяем равенст­вом и строим соответствующие этим равенствам гранич­ные прямые:

a _i1x₁+a_i2 x₂=b_i (i=l.. .m).

Каждая из этих прямых делит плоскость XiOX2 на две полуплоскости (рис. 1). Для точки (.) А, принадлежащей одной из этих полуплоскостей, выполняется неравенство:a _i1x₁+a_i2 x₂b_i (i=l.. .m).

Для любой (.)В, принадлежащей другой полуплоскости, — противоположное неравенство: a _i1x₁+a_i2 x₂b_i (i=l.. .m).

А для любой из точек, лежащих на граничной прямой, выполняется уравнение: a _i1x₁+a_i2 x₂=b_i (i=l.. .m).

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

Если же неравенство не удовлетворяется, штриховка, выделяющая искомую полуплоскость, обращена в проти­воположную от данной точки сторону.

Рис.1. Построение ОДЗ

Чтобы графически определить, по какую сторону от граничной прямой располагается полуплоскость, содержа­щая

Неравенства x₁0, x₂0, также соответствуют полу­плоскостям, одна из которых расположена справа от оси ординат, а другая - над осью абсцисс (рис. 1).

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

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

• пустой, что означает несовместимость систем нера­венств:

• одной точкой:

• выпуклым многоугольником:

• неограниченной выпуклой многоугольной областью:

Х₂

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

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

Уравнение:

c₁ x₁+c₂x₂ =L при фиксированном значении L определяет прямую, а при изменении L — семейство параллельных прямых с параметром L. Вектор C=(c₁, c₂), перпендикулярный ко всем этим прямым, показывает направление возрас­тания параметра L. Так, на рис. 2 показаны прямые, соответствующие уравнению

2x₁+3x₂=L при L=-3, 0, 3, 9.

Рис.2. Графическое изображение целевой функции

Для всех точек, лежащих на одной из этих прямых, функция F принимает одно определенное значение, равное соответствующему значению L. Поэтому рассматриваемые прямые называются линиями уровня для параметра L.

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

Построим, для рассмотренного выше примера линии уровня и определим направление их возрастания.

Чтобы построить вектор С=(с₁,с₂), можно использовать следующий прием: по оси X₁ откладывается значение пер­вой компоненты вектора с₁=2, а по оси Х₂ — значение вто­рой компоненты с₂=3.

По найденным координатам строим прямоугольник и находим направление возрастания вектора С. Затем пер­пендикулярно вектору С строим линии уровня.

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

На рис. 3 видно, что в крайнем положении линия уровня проходит через (.) В. При дальнейшем ее перемеще­нии она уже не будет иметь общих точек с областью допус­тимых решений. Таким образом, искомое оптимальное ре­шение, которое графически соответствует координатам (.)В, можно найти путем совместного решения системы двух уравнений, соответствующих граничным прямым АВ иВД.

Если при тех же исходных данных требовалось бы до­стичь минимума функции F, то, очевидно, линию уровня пришлось бы перемещать в направлении, противоположном вектору С. В этом случае оптимальное решение, соот­ветствующее минимуму функции F, определялось бы коор­динатами точки (.) 0.

Рис. 3. Определение оптимального решения гра­фическим методом

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

• ЗЛП имеет единственное решение

• ЗЛП имеет альтернативный оптимум

• ЗЛП имеет минимум и не имеет макси­мума

• ЗЛП не имеет решения

Вопросы для самоконтроля:

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

2. Элементы геометрии в n - мерном пространстве.

Рекомендуемая литература:

1.Ашманов С.А. Линейное программирование. —М.: Наука, 1981.

2.Айсагалиев А.С., Айсагалиева С.С. Лекции по методам оптмизации.-Алматы:Гылым,1996