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

⇐ ПредыдущаяСтр 2 из 6Следующая ⇒

Первое упоминание (1938 г.) о математических методах в эффективном управлении производством принадлежит советскому математику Л. В. Канторовичу. Год спустя, в 1939 г., Л. В. Канторович опубликовал работу «Математические методы организации и планирования производства» и практически применил полученные результаты. Термин «линейное программирование» ввели американские математики Дж. Данциг и Т. Купманс в конце 40-х годов.

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

1) быть единственным для данной задачи;

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

3) линейно зависеть от входных параметров.

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

а) удовлетворяют системе ограничений

(1)

б) являются неотрицательными , (2)

в) обеспечивают экстремум целевой функции (максимум или минимум)

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

Вектор , удовлетворяющий условиям задачи (1), (2), называется допустимым решением или опорным планом.

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

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

Если система ограничений состоит лишь из нестрогих неравенств, то это – стандартная форма задачи линейного программирования:

(3)

В матричной форме:

где – скалярное произведение соответствующих векторов.

Если система ограничений состоит лишь из равенств, то это – каноническая форма задачилинейного программирования:

(4)

В матричной форме:

Преобразование задач

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

1) Максимизация целевой функции

равносильна минимизации целевой функции

так как min = – max [– ].

2) Чтобы изменить тип ограничения – неравенства, нужно умножить

его на –1:

Þ .

3) Чтобы перейти от ограничений – неравенств к равенствам, нужно

ввести дополнительную переменную :

а) Þ

;

б) Þ

4) Чтобы перейти от ограничений – равенств к неравенствам,

достаточно заменить эти ограничения на два противоположных неравенства:

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

Переход от стандартной задачи к канонической осуществляется добавлением новых неотрицательных переменных (неосновные переменные) со знаком «+» для неравенств со знаком « » и со знаком «–» для неравенств со знаком « ». Результат в матричной форме:

Пример 3.

Это стандартная задача. Из нее получим каноническую задачу, добавив в 1-е и 4-е неравенства переменные –х₃, –х₆ и во 2-е и 3-е неравенства переменные х₄, х₅.