Основные теоремы двойственности

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

 

Возможны следующие случаи:

 

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

 

Первая теорема двойственности.

 

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

 

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

 

Вторая теорема двойственности (теорема о дополняющей нежесткости):

 

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

 

Теорема об оценках:

 

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

 

Экономический смысл первой теоремы двойственности следующий. План производства и набор ресурсов оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при известных заранее ценах продукции , равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов Для всех других планов прибыль от продукции всегда меньше или равна стоимости затраченных ресурсов , т.е. ценность выпущенной продукции не превосходит суммарной оценки затраченных ресурсов. Значит, величина характеризует производственные потери в зависимости от рассмотренной производственной программы и выбранных оценок ресурсов.

28.Применение двойственных оценок при анализе оптимального плана. Пример.

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

30.Экономическая интерпретация двойственных задач. Значение нулевых оценок в решении экономической задачи. Примеры.

Исходная задача I имела конкретный экономический смысл: основные переменные хi обозначали количество произведенной продукции i-го вида, дополнительные переменные обозначали количество излишков соответствующего вида ресурсов, каждое из неравенств выражало собой расход определенного вида сырья в сравнении с запасом этого сырья. Целевая функция определяла прибыль при реализации всей продукции. Предположим теперь, что предприятие имеет возможность реализовывать сырье на сторону. Какую минимальную цену надо установить за единицу каждого вида сырья при условии, чтобы доход от реализации всех его запасов был не меньше дохода от реализации продукции, которая может быть выпущена из этого сырья.

 

Переменные у1, у2, у3 будут обозначать условную предполагаемую цену за ресурс 1, 2, 3 вида соответственно. Тогда доход от продажи видов сырья, расходуемых на производство одной единицы продукции I, равен: 5у1 + 1· у3. Т. к. цена продукции I типа равна 3 ед., то 5у1 + у3 3, в силу того, что интересы предприятия требуют, чтобы доход от продажи сырья был не меньше, чем от реализации продукции. Именно в силу такого экономического толкования система ограничений двойственной задачи принимает вид: А целевая функция G = 400y1 + 300y2 + 100y3 подсчитывает условную суммарную стоимость всего имеющегося сырья. Понятно, что в силу I теоремы двойственности F(x*) = G(y*) равенство означает, что максимальная прибыль от продажи всей готовой продукции совпадает с минимальной условной ценой ресурсов. Условные оптимальные цены уi показывают наименьшую стоимость ресурсов, при которой выгодно обращать эти ресурсы в продукцию, производить.

 

Еще раз обратим внимание на то, что уi - это лишь условные, предполагаемые, а не реальные цены на сырье. Иначе читателю может показаться странным, что например, у1* = 0. Этот факт вовсе не означает, что реальная цена первого ресурса нулевая, ничего бесплатного в этом мире нет. Равенство нулю условной цены означает лишь, что этот ресурс не израсходован полностью, имеется в излишке, недефицитен. Действительно, посмотрим на первое неравенство в системе ограничений задачи I, в котором подсчитывается расход первого ресурса: 5х1* + 0, 4х2* + 2х3* + 0, 5х4* = 66 < 400. его избыток составляет х5 = 334 ед. при данном оптимальном плане производства. Этот ресурс имеется в избытке, и поэтому для производителя он недефицитен, его условная цена равна 0, его не надо закупать. Наоборот, ресурс 2 и 3 используются полностью, причем у3 = 4 а у2 = 1, т. е. сырье третьего вида более дефицитно, чем второго, его условная цена больше. Если производитель продукции имел бы возможность приобретать дополнительно сырье к уже имеющемуся, с целью получения максимального дохода от производства, то увеличив сырье второго вида на единицу, он бы получил дополнительно доход в у2 денежных единиц, с увеличением на единицу сырья третьего вида, значение целевой функции увеличилось бы еще на у3 единицы.

 

Если перед производителем стоит вопрос, " выгодно ли производить какую-либо продукцию при условии, что затраты на единицу продукции составят 3, 1, 4 единиц 1, 2, 3-го видов сырья соответственно, а прибыль от реализации равна 23 единицам", то в силу экономического истолкования задачи ответить на этот вопрос несложно, поскольку затраты и условные цены ресурсов известны. Затраты равны 3, 1, 4, а цены у1* = 0, у2* = 1, у3* = 4. Значит, можно посчитать суммарную условную стоимость ресурсов, необходимых для производства этой новой продукции: 3 · 0 + 1 · 1 + 4 · 4 = 17 < 23. значит продукцию производить выгодно, т. к. прибыль от реализации превышает затраты на ресурсы, в противном случае ответ бы на этот вопрос был отрицательным.

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

32.Использование оптимального плана и симплекс-таблицы для анализа чувствительности целевой функции. Пример.

Транспортная задача и ее свойства. Пример.

Классическая транспортная задача ЛП формулируется следующим образом.

 

Имеется m пунктов производства (поставщиков) и n пунктов

 

потребления (потребителей) однородного продукта. Заданы величины:

- объем производства (запас) i-го поставщика, i=1, m;

- объем потребления (спрос) j-го потребителя, i=1, n;

- стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

 

Требуется составить такой план перевозок, при котором спрос

 

всех потребителей был бы выполнен и при этом общая стоимость всех

 

перевозок была бы минимальна.

 

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

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

 

В случае, когда суммарные запасы превышают суммарные

 

потребности, т.е. вводится фиктивный n+1 потребитель, потребности которого В случае, когда суммарные потребности превышают суммарные

 

запасы, т.е. , вводится фиктивный m+1 поставщик, запасы которого Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика

 

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

 

Прежде чем решать транспортную задачу, необходимо проверить, к какой модели она принадлежит, и если необходимо, то привести ее к

 

закрытой модели.

 

Основные свойство транспортной задачи

 

Математические модели любых транспортных задач ЛП обладают общими чертами, а именно,

 

1) коэффициенты целевой функции неотрицательны (стоимости перевозок не могут быть отрицательными величинами);

 

2) коэффициенты правых частей ограничений неотрицательны (запасы и потребности продукта);

 

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

 

В силу этих особенностей транспортная задача обладает следующими свойствами.

 

Теорема 1.

 

Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

 

Доказательство.

 

Количество базисных компонент определяется число линейно-независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.

 

Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

Но в закрытой модели выполняется балансовое равенство поэтому получаем, что нетривиальная линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это означает, что среди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно m+n-1 и базис задачи состоит из m+n-1 компонент.

 

Теорема доказана

 

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

 

Теорема 2.

 

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

 

Доказательство.

 

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

 

Покажем существование допустимого решения. Так как

 

суммарные запасы совпадают с суммарными потребностями то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).

 

Покажем ограниченность целевой функции.

 

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

 

Теорема доказана

 

Открытая и закрытая модели транспортной задачи. Примеры

2. Модели транспортной задачи

2.1. Закрытая модель транспортной задачи

 

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

Доказательство. Пусть

= M > 0

.

Тогда величиныxij=aibj/M(i= 1, 2, 3, ...m; j= 1, 2, 3, ..., n) являются планом, так как они удовлетворяют системе ограничений

( 2 ) и ( 3 ).

Действительно, подставляя значения в (2) и (3), находим

 

= ai,

 

= bj.

Выберем из значенийCijнаибольшее Cў=max Cijи заменим в линейной функции ( 1 ) все коэффициенты на Cўтогда, учитывая ( 2 ), получим

 

,

Выберем из значенийCijнаименьшееCў(=min Cijи заменим в линейной функции все коэффициенты наCў(; тогда, учитывая ( 2 ) имеем

 

Объединяя два последних неравенства в одно двойное, окончательно получаем

Cў(M? Z? CўM,

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

 

 

2.2. Открытая модель транспортной задачи

 

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

, называется открытой. Для открытой модели может быть два случая:

a)суммарные запасы превышают суммарные потребности

;

b)суммарные потребности превышают суммарные запасы

.

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

Найти минимальное значение линейной функции

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

, i = 1, 2, ..., m, (случай а)

, j = 1, 2, ..., n;

, i = 1, 2, ..., m, (случай б)

, j = 1, 2, ..., n,

xij і 0 (i = 1, 2, ..., m; j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1=

. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1=

.

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

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

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

 

Понятие минимального остовного дерева. Алгоритм построения минимального остовного дерева. Пример.

Постановка задачи

 

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?

 

В общем случае, задачу можно сформулировать так. Пусть дан связный, неориентированный граф с весами на ребрах G(V, E), в котором V — множество вершин (контактов), а E — множество их возможных попарных соединений (ребер). Пусть для каждого ребра (u, v) однозначно определено некоторое вещественное число w(u, v) — его вес (длина или стоимость соединения). w() называется весовой функцией. Задача состоит в нахождении такого связного ациклического подграфа T ⊂ G, содержащего все вершины, что суммарный вес его ребер будет минимален.

 

Так как T связен и не содержит циклов, он является деревом и называется остовным или покрывающим деревом (spanning tree). Остовное дерево T, у которого суммарный вес его ребер w(T) = ∑ (u, v)∈ T w(u, v) минимален, называется минимальным остовным или минимальным покрывающим деревом (minimum spanning tree).

 

Рис. 1. Минимальное остовное дерево. Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c, d) и добавлением ребра (a, b) получается новое минимальное остовное дерево.

 

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

Рис.2-а. Минимальное остовное дерево.

Суммарный вес равен 3. Рис.2-б. Минимальный покрывающий подграф.

Суммарный вес равен 0.

Также считаем, что для любой пары ребер их весовые характеристики будут различны. Это гарантирует уникальность построенного минимального остовного дерева. Для примера, если все ребра имеют единичный вес, то любое остовное дерево будет минимальным (с суммарным весом v-1, где v – количество вершин в графе). В данном случае, любой алгоритм построит одно из минимальных остовных деревьев. Один из вариантов разрешения неопределенности заключается в модификации алгоритма сравнения ребер по весу, например, так:

 

SHORTER-EDGE(i; j; k; l)

1: if w(i, j) < w(k, l) then return (i, j)

2: if w(i, j) > w(k, l) then return (k, l)

3: if min(i, j) < min(k, l) then return (i, j)

4: if min(i, j) > min(k, l) then return (k, l)

5: if max(i, j) < max(k, l) then return (i, j)

6: return (k, l)

Задача поиска кратчайшего пути. Алгоритм решения Флойда. Пример.

42.Задача поиска кратчайшего пути. Алгоритм решения Дейкстры. Пример.

 

 

⇐ Предыдущая12345

Поделиться: