Лекция 3. Различные формы задач линейного программирования


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

· Стандартная форма задачи линейного программирования

· Каноническая форма задачи линейного программи­рования (ЗЛП)

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

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

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

Общая форма задачи линейного программирования

Задана система m линейных уравнений с n переменны­ми:

(1)

xj >0, где(j = l...n) , (2)

а линейная функция:

F = c1 x12 x23 x3+... + cn xn → max(min). (3)

Необходимо найти такой вектор Х=(х1, х23 ,.. xn), который удовлетворяет ограничениям (1) и (2) и при котором линейная функции F принимает максимальное (или минимальное) значение.

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

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

Оптимальным решением (или оптимальным планом) за­дачи линейного программирования называется решение Х*=(х*1 ,х*2...хn), удовлетворяющее системам ограничений, при которой линейная функция F достига­ет оптимального значение (минимума или максимума).

Термины «решение» или «план» — синонимы, одна­ко первый используется чаще, когда речь идет о формали­зованной постановке задачи, а второй — о содержательной.

Стандартная форма задачи линейного программирования

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

а линейная функция:

F = c1 x12 x2+c3 x3+... + cт xт->max(min),

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

Особенность данной формы состоит в том, что в ней система как функциональных, так и прямых ограничений состоит из одних неравенств, переменные xj ≥0, где (j=l...n) являются неотрицательными, а целевая функция может стремиться как к минимуму, так и к максимуму.

Каноническая форма задачи линейного программи­рования (ЗЛП)

Форма, в которой:

F= c1 x1 +c2 x2+c3 x3+... + cn xn->max

все переменные Xj — неотрицательны, система ограниче­ний представляет собой систему уравнений, а целевая функция стремится к максимуму, называется канонической формой задачи линейного программирования.

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

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

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

(4)

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

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

(5)

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

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

Пример

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

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

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

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

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

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

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

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

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

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

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