Методы линейного программирования, двойственность в линейном программировании

Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л.В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике.

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

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

Форма записи задачи линейного программирования выглядит следующим образом.

Например, дана система m уравнений и неравенств с n переменными:

(1.1)

и линейная функция:

. (1.2)

Необходимо найти такое решение системы (1) Х = (х1, х2, … , хn) с неотрицательными компонентами хj ≥ 0, , при котором линейная функция f принимает наибольшее (наименьшее) значение.

Систему (1) называют системой ограничений, функцию f (2) – целевой функцией ограничений, поставленную задачу – общей задачей линейного программирования.

Сформулируем некоторые теоремы линейного программирования.

1. Теорема о замене линейного неравенства линейным уравнением и неравенством. Каждому решению 1, а2, … аn) неравенства:

(1.3)

соответствует единственное решение 1, а2, …, аn, an+1) уравнения

(1.4)

и неравенства хn+1 ≥ 0 и наоборот.

2. Если область допустимых значений (ОДР) системы ограничений задачи линейного программирования замкнутая, ограниченная, то оптимальное решение задачи существует и совпадает хотя бы с одним из опорных решений системы ограничений.

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

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

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

, , . (1.5)

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в пункт назначения n, который потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки Cij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы kCij.

Далее предполагается, что

, (1.6)

где ai - количество продукции, находящееся на складе i;

bj – потребность потребителя j.

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

1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок , то количество продукции, равное остается на складах. В этом случае вводим «фиктивного» потребителя n + 1 с потребностью и положим транспортные расходы pi, n+1 равными 0 для всех i.

2. Если сумма поданных заявок превышает наличные запасы , то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного пункт отправления во все пункты назначения принять равным нулю.

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

, (1.7)

; (1.8)

; (1.9)

, (1.10)

где xij – количество продукции,поставляемое со склада i потребителю j;

Сij – издержки (стоимость перевозок со склада i потребителю j).

Рассмотрим пример. Компания «Архстройдор» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона, дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. тонн щебенки. Стоимости перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице 1.1.

Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными.

Таблица 1.1

Исходные данные

Карьер Строительный объект

 

Данная транспортная задача является закрытой, так как запасы поставщиков: 800 + 900 + 600 = 2300 равны спросу потребителей 300 + 600 + + 750 = 2300. Математическая модель задачи линейного программирования в данном случае имеет вид: xij; i = 1, 2, 3; j = 1, 2, 3, 4 – количество щебенки, перевозимой с i-го карьера на j-й объект. Тогда целевая функция равна:

. (1.11)

Ограничения имеют вид:

(1.12)

Американский математик Дж. Данциг разработал эффективный метод решения задач линейного программирования – симплекс-метод.

Симплексный метод решения задачи линейного программирования основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает (при условии, что данная задача имеет оптимальный план и каждый ее опорный план является невырожденным). Указанный переход возможен, если известен какой-нибудь исходный опорный план.[1]

Основное содержание симплексного метода заключается в следующем:

- указать способ нахождения оптимального опорного решения;

- указать способ перехода от одного опорного решения к другому, на котором значение целевой функции будет ближе к оптимальному, т.е. указать способ улучшения опорного решения;

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

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

- привести задачу к каноническому виду;

- найти начальное опорное решение с «единичным базисом» (если опорное решение отсутствует, то задача не имеет решения);

- вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода;

- если выполняется признак единственного оптимального решения, то решение задачи заканчивается;

- если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения.

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

Двойственная задача – это вспомогательная задача линейного программирования, формулируемая с помощью определенных правил непосредственно из условий исходной задачи, которая в этом случае называется прямой задачей линейного программирования.[2]

В зависимости от вида исходной задачи линейного программирования различают симметричные, несимметричные и смешанные пары двойственных задач.

Теория двойственности в линейном программировании строится на следующих основных теоремах.

1. Если задача линейного программирования имеет конечный оптимум, то двойственная к ней также имеет конечный оптимум, и оптимальные значения линейных форм обеих задач совпадают, то ест Fmax = Zmin или Fmin = Zmax. Если линейная форма одной из двойственных задач не ограничена, то условия другой задачи противоречивы.

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

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

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