Алгебраическая формулировка задачи линейного программирования в общем виде

2009-09-16

Лекция 4

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

Алгебраическая формулировка задачи линейного программирования в общем виде

Требуется найти максимум или минимум линей функции n-переменных.

                                                           (1)

При ограничениях, наложенных на переменные  вида:

                                                                             (2)

                                                                      (3)

                                                                      (4)

При ограничения 2-4 поставленная задача оптимизация может принимать три случая:

1. Условия 2-4 противоречивы, то есть не существует значений переменных , которые удовлетворяли бы всем условиям 2-4; задача не имеет ни одного допустимого решения.
2. Условия 2-4 совместны. Область, определяемая ими ограничена, и тогда возможны единственное оптимальное допустимое решение и несколько допустимых оптимальных решений.
3. Условия 2-4 непротиворечивы, но область, определяемая ими, неограниченна. Значение целевой функции может быть сделано неограниченно большим для задачи максимизации и сколь угодно малым для задачи минимизации.

Запись критерия и ограничений в разных задачи различается. Различие в записях условий задачи целесообразно сводить к канонической форме (далее КФ).

КФ задачи линейного программирования

Задачи линейного программирования (далее ЛП) следующим образом:

- найти минимум линейной формы ;

- ;                                                                                                 (5)

- .                                                                                                       (6)

Из условий 1-4 видно, что для перехода к КФ необходимо от ограничений неравенств 3 перейти к ограничениям равенства. В условия 3 введем дополнительные неотрицательные переменные . Тогда ограничение 3 можно представить в виде равенств:

                                           (7)

            В линейную форму дополнительные переменные входят с нулевыми коэффициентами.

Если число неотрицательных переменных , то общая задача уже сведена к КФ. Если , то возможны два варианта:

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

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

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

а) задача ЛП неразрешима;

б) общее количество переменных и ограничений сокращается.

Графическая интерпретация задач ЛП

1. Рассмотрим случай, когда . Число переменных n на два больше, чем независимых уравнений. Так как разность равна 2, выберем две свободные переменные, например, и , остальные m-переменных сделаем базисными и выразим через свободные.

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

1.

2.

3.

4.

5.

Выбираем в качестве свободных переменных и . Выразим через них базисные переменные .

По условию задачи все переменные должны быть неотрицательны. Имеем систему: