Связь между решениями прямой и двойственной задачи

Рассмотрим двойственную пару симметричных задач (13)-(15) и (16)-(18). Каждая из задач двойственной пары является самостоятельной задачей линейного программирования и может быть решена независимо одна от другой. Однако, при определении симплексным методом оптимального плана одной из задач тем самым находится решение и другой задачи.

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

Теорема 1. Для любых допустимых планов и прямой и двойственной ЗЛП справедливо неравенство , т. е.

. (19)

Теорема 2 (критерий оптимальности Канторовича). Если для некоторых допустимых планов и пары двойственных задач выполняется равенство

, (20)

то –оптимальный план исходной задачи, а –оптимальный план двойственной задачи.

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

Теорема 3 (первая теорема двойственности).Если одна из пары двойственных задач (13)-(15) или (16)-(18) имеет оптимальный план, то и другая имеет оптимальный план, и значения целевых функций задач при их оптимальных планах равны между собой, т. е.

. (21)

Если же целевая функция одной из пары двойственных задач не ограничена (для исходной задачи (13)-(15)–сверху, для двойственной задачи (16)-(18)–снизу), то система ограничений другой задачи противоречива (задача вообще не имеет допустимых планов).

Теорема 4 (вторая теорема двойственности).Для того чтобы планы и пары двойственных задач были оптимальными, необходимо и достаточно, чтобы выполнялись условия:

(22)

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

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

(23)

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

Оптимальное распределение ресурсов.

Транспортная задача

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

Рассмотрим постановку транспортной задачи по критерию стоимости. Пусть некоторый однородный товар (кирпич, пиломатериалы и т.п.) хранится на m складах А_i (i= 1¸ m) и требуется в n пунктах В_j (j= 1¸ n). Известны следующие параметры: а_i – запас товара на i -м складе; b_j – потребность в товаре в j -м пункте; с_ij – стоимость перевозки единицы товара из i -го склада в j- й пункт. Предполагается, что стоимость перевозки произвольного количества товара пропорциональна этому количеству. Требуется составить план перевозок товара так, чтобы удовлетворить потребности при имеющихся запасах, обеспечив при этом наименьшую суммарную стоимость перевозок.

Приведённые выше условия – экономическая постановка задачи. Обозначим через х_ij количество товара, перевозимого из i- го склада в j- й пункт. Стоимость перевозки товара из А_i в В_j составит с_ijх_ij, а суммарная стоимость перевозок есть . Следовательно,

z = . (1)

Далее, все запасы из пункта А_i должны быть вывезены, т.е.

, i =1¸ m. (2)

Все потребности пункта В_j должны быть удовлетворены, т.е.

, j =1¸ n. (3)

Естественно предполагать также, что

х_ij³ 0, i =1¸ m, j= 1¸ n. (4)

Математическая модель ТЗ состоит в определении неотрицательного плана перевозокХ = (х_ij), для которого выполняются условия (2) и (3), а целевая функция (1) принимает наименьшее значение. Матрица Х = (х_ij) _m×n называется матрицей перевозок.

Рассмотрим решение ТЗ, экономико-математическая постановка которой приведена выше. Для наглядности условия ТЗ можно представить таблицей 1.

Таблица 1

Bj Аi	b 1	b 2	…	bп
а 1	с 11 х 11	с 12 x 12	…	с 1 п x 1 n
а 2	c 21 x 21	c 22 x 22	…	c 2 п x 2 n
…	…	…	…	…
ат	cm 1 xm 1	cm 2 xm 2	…	cmn xmn

Если сумма всех запасов равна сумме всех заявок, т.е.

а_i = b_j, (5)

то мы имеем ТЗ закрытого типа.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (8), (9) п.1, определяемое матрицей перевозок Х, называется планом ТЗ.

Определение 2. План Х*, при котором функция (1)принимает своё минимальное значение, называется оптимальным планом ТЗ.

Теорема 3. Для того чтобы ТЗ имела допустимые планы, необходимо и достаточно, чтобы выполнялось равенство (5).

В случае если сумма запасов не равна сумме потребностей (заявок), имеем задачу открытого типа. Если сумма заявок превышает сумму запасов, вводится фиктивный поставщик А_{т +1}, «запас» которого равен разности между суммой заявок и суммой запасов: а_{т +1}= b_j- а_i. В случае, когда сумма запасов превышает сумму заявок, вводится фиктивный потребитель В_{п +1}, «заявка» которого равна разности между суммой запасов и суммой заявок: b_{п +1}= а_i - b_j. Стоимости всех фиктивных перевозок полагают равными нулю. Таким образом, задача открытого типа легко сводится к задаче закрытого типа.

Поскольку ТЗ является задачей линейного программирования, она может быть решена симплекс-методом. Но в силу специфики задачи (каждая переменная входит лишь в два уравнения системы (8), (9) разд.1. и коэффициенты при переменных равны единице) оптимальный план ТЗ может быть получен путем некоторых преобразований транспортной таблицы. Как и в общем случае, оптимальный план ищется среди опорных решений.

Число переменных х_ij в ТЗ с m пунктами отправления и n пунктами назначения равно mn, а число уравнений в системах (2) и (3)равно m+n. Т.к. в закрытой ТЗ выполняется условие (5), то число линейно независимых уравнений равно m+n -1. Следовательно, опорный план ТЗ может иметь не более m+n -1 отличных от нуля переменных. Это – базисные переменные. Если в опорном плане число отличных от нуля переменных равно в точности равно m+n -1, то план является невырожденным, а если меньше – то вырожденным.

Для определения опорного плана существует несколько методов. Рассмотрим два из них – метод северо-западного угла и метод минимальной стоимости.

 

⇐ Предыдущая234567891011Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: