Лекция 1. Линейное программирование

Общая постановка задачи

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

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

Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

ь задача об оптимальном использовании ресурсов при производственном планировании;

ь задача о смесях (планирование состава продукции);

ь задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или «задача о рюкзаке»);

ь транспортные задачи (анализ размещения предприятия, перемещение грузов).

Линейное программирование — наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

ь математические модели большого числа экономических задач линейны относительно искомых переменных;

ь данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;

ь многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

Определение. Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.

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

Z (x)=c1x1+c2x2 +. .. +cJxJ +. .. +cnxn > max (min).

при ограничениях:

где Xi — неизвестные; a ij, bj, Ci — заданные постоянные величины.

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

Математическая модель в более краткой записи имеет вид.

Z (x) = ?Ci Xi >max (min).

при ограничениях:

Определение. Допустимым решением (планом) задачи линейного программирования называется вектор X =(х1,х2,…хn), удовлетворяющий системе ограничений.

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

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

Базисное допустимое решение Является опорным решением, где r— ранг системы ограничений.

Виды математических моделей ЛП Математическая модель задачи ЛП может быть канонической и неканонической.

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

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

Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную хn+i .

Если знак неравенства, то — минус. В целевую функцию балансовые переменные не вводятся.

Чтобы составить математическую модель задачи ЛП, необходимо:

• 1) ввести обозначения переменных;
• 2) исходя из цели экономических исследований, составить целевую функцию;
• 3) учитывая ограничения в использовании экономических показателей задачи и их количественные закономерности, записать систему ограничений.