Краткие исторические сведения

Время рождения ЛП – 1939 год: напечатана брошюра члена-корреспондента АН СССР Леонида Витальевича Канторовича «Математические методы организации и планирования производства».

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

Второе рождение ЛП получило в конце сороковых годов с появлением ЭВМ.

Основной метод решения задач - симплексный метод – был разработан американскими исследователя в 1949 году Дж. Б. Данцигом и Т. Купмансом.

В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за «вклад в разработку теории и оптимального использования ресурсов в экономике».

Термин «линейное программирование впервые появился в работах Дж. Б. Данцигам и Т. Купманса в 1951 году.

Слово «программирование» означает, что набор полученных решений определяет программу (или план) реализации производственных задач.

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

Следует максимизировать целевую функцию:

(1)

при условиях связи:

(2)

и условиях неотрицательности

(3)

В векторном виде:

, ,

Тогда условие (1) имеет вид:

Замечание.

Если критерий задачи

,

то

Три формы задания ЗЛП:

Если (условия связи заданы только в форме неравенств) – ЗЛП в стандартной форме:

.

Если (условия связи заданы только в форме равенств) – ЗЛП в канонической форме:

.

Если – ЗЛП в общей форме.

– матрица условий,

– вектор условий.

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

1. Любая ЗЛП может быть приведена к ЗЛП в канонической форме путём введения балансовых переменных.

Пример:

Вводим балансовые неотрицательные переменные и во второе и третье ограничение:

Полученная задача имеет вид

2. Любая ЗЛП может быть приведена к ЗЛП в стандартной форме.

Ограничение в виде равенства

можно представить в виде двух неравенств

,

.

Переход к неотрицательным переменным:

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

, , .

Любое решение системы ограничений (2)-(3) называется допустимым решением.

Совокупность всех допустимых решений называется областью допустимых решений (ОДР).

Допустимое решение, для которого целевая функция достигает максимума (минимума), называется оптимальным решением.