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

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

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

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

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

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

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

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

В этом случае все неравенства приводят к уравнениям, вводя новые (балансовые) переменные в каждое неравенство системы.

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

Пример. Пусть система ограничений представлена в виде неравенств:

Добавим в каждое из них по одной новой (балансовой) переменной. Получим каноническую задачу линейного программирования:

(у новой переменной ставим знак «+»,если в неравенстве был знак « », и наоборот, у новой переменной ставим знак «-»,если в неравенстве был знак « »)

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

Теорема 1. Множество всех допустимых решений задачи линейного программирования является выпуклым.

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

Теорема 2. Если существует единственное решение задачи линейного программирования, то оно совпадает с одной из угловых точек множества допустимых решений.

Теорема 3. Каждому допустимому базисному решению соответствует угловая точка области ограничений.

Теорема 4. Каждой угловой точке множества допустимых решений соответствует допустимое базисное решение.

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

Задачи для самостоятельного решения

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

а) б)

2. Привести задачи линейного программирования 1-13 (задачи для самостоятельного решения из п. 2.1) к каноническому виду.