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

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

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

Имеется m видов сырья в количестве b₁, b₂, …, b_m, которые используют для изготовления n видов продукции. Известно, что на единицу каждого вида продукции расходуется a_ij количество сырья, где i= , j= . Пусть C_j – прибыль при реализации j-того вида продукции.

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

Z(x)=C₁x₁+C₂x₂+…+C_nx_n → max

x_j≥0; j=

Предположим, что второй производитель хочет перекупить сырьё.

Составим двойственную задачу, решение которой позволит определить условие продажи сырья. Введём цены видов сырья: I=y₁, II=y₂, …, N=y_m. Затраты на приобретение i-того вида сырья в количестве b_i=b_iy_i. Второму производителю выгодно минимизировать суммарные затраты на приобретение всех видов сырья. По этому целевая функция задачи имеет вид: F(y)=b₁y₁+b₂y₂+…+b_my_m → min

Первому производителю не выгодно продать сырьё, если суммарная стоимость всех видов сырья, расходуемых на каждое изделие j-той продукции a_1jy₁+a_2jy₂+…+a_mjy_m≤C_j.

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

y_j≥0; j=

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

Двойственные задачи бывают симметричными и несимметричными.

Симметричные пары:

1)если Z(x) → max, Ах≤А₀, х≥0, то F(y) =YA₀→ min, YA≥С, y≥0;

2)если Z(x) → min, Ах≥А₀, х≥0, то F(y) =YA₀→ max, y≥0.

Общие правила составления двойственных задач:

1)Во всех ограничения исходной задачи свободные члены должны находится в правой части, а члены с независимыми – в левой.

2)Ограничения неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.

3)Если знаки неравенств в исходной задаче ≤, то целевая функция должна стремится к максимуму, если знаки ≥, то должна стремится к минимуму.

4)Целевая функция двойственной задачи F(y)=с₀+b1y1+b₂y₂+…+b_my_n → min, где с₀ – свободный член целевой функции Z(x).

5)Целевая функция F(y) должна оптимизироваться противоположным, по сравнению с Z(x), образом.

6)Каждому неизвестному x_j исходной задачи соответствует ограничение в двойственной задаче.

 

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

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

Двойственные задачи бывают симметричными и несимметричными.

Теорема 1.

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

Теорема 2.

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

 

Теорема двойственности

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

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

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

 

 

19. Оценки как мера дефицитности ресурсов. Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.

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

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

 

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

 

 

(2.9)

В том случае, если Δ_j ≤ 0, вариант производства является выгодным, если Δ_j > 0 – вариант невыгоден.

 

20. Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов": (В формулировке для несимметричной двойственной задачи)

Если i-ая компонента оптимального плана исходной задачи строго положительна, то i-ое ограничение двойственной задачи при подстановке в нее оптимального плана превращается в строгое равенство

.

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

.

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

Еще раз вспомним симплекс-метод и симплекс-таблицу для оптимального плана. Там получалось, что если , то , если же , то .

Но. согласно предыдущей теореме,

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

,

так что i-ая строка матрицы

имеет вид

.

Поэтому, если ,

то должно быть

и

.

Если же ,

то должно быть

, то есть

.

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

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

Теорема 3. (В формулировке для симметричной двойственной задачи).

Если i-ая компонента оптимального плана какой-то задачи положительна, то i-ое ограничение двойственной ей задачи, при подстановке в не оптимального плана, превращается в строгое равенство.

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

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

Открытая модель решается приведением к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель Bn+1, потребности которого bn+1 =. В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик Am+1, запасы которого am+1 =.
Стоимость перевозки единицы груза как фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика полагают равными нулю, так как груз в обоих случаях не перевозится.
После преобразований задача принимает вид закрытой модели и решается обычном способом. При равных стоимостях перевозки единицы груза от поставщиков к фиктивному потребителю затраты на перевозку груза реальным потребителям минимальны, а фиктивному потребителю будет направлен груз от наименее выгодных поставщиков. То же самое получаем и в отношении фиктивного поставщика.
Прежде чем решать какую-нибудь транспортную задачу, необходимо сначала проверить, к какой модели она принадлежит, и только после этого составить таблицу для ее решения. Закрытой же моделью задачи будет обратное открытой

22.Методы построения начального опорного решения.
Метод северо-западного угла.
Существует ряд методов построения начального опорного решения, наиболее простым из которых является метод северо-западного угла. В данном методе запасы очередного поставщика используются для обеспечения запросов очередных потребителей до тех пор, пока не будут исчерпаны полностью, после чего используются запасы следующего по номеру поставщика. Заполнение таблицы транспортной задачи начинается с левого верхнего угла и состоит из ряда однотипных шагов. На каждом шаге, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или потребитель. Осуществляется это таким образом: 1. если, то и исключается поставщик с номером i,, k=1, 2,..., n, kj,;2. если, то и исключается потребитель с номером j,, k=1, 2,..., m, ki,;3. если, то и исключается либо i-й поставщик,, k=1, 2,..., n, kj,, либо j-й потребитель,, k=1, 2,..., m, ki, Нулевые перевозки принято заносить в таблицу только тогда, когда они попадают в клетку (i,j), подлежащую заполнению. Если в очередную клетку таблицы (i,j) требуется поставить перевозку, а i-й поставщик или j-й потребитель имеет нулевые запасы или запросы, то в клетку ставится перевозка, равная нулю (базисный нуль), и после этого, как обычно, исключается из рассмотрения соответствующий поставщик или потребитель. Таким образом, в таблицу заносят только базисные нули, остальные клетки с нулевыми перевозками остаются пустыми. Во избежание ошибок после построения начального опорного решения необходимо проверить, что число занятых клеток равно m+n-1 и векторы-условия, соответствующие этим клеткам, линейно независимы. Теорема4. Решение транспортной задачи, построенное методом северо-западного угла, является опорным. Доказательство. Число занятых опорным решением клеток таблицы должно быть равно N=m+n-1. на каждом шаге построения решения по методу северо-западного угла заполняется одна клетка и исключается из рассмотрения одна строка (поставщик) или один столбец (потребитель) таблицы задачи. Через m+n-2 шага в таблице будет занято m+n-2 клетки. В то же время останутся невычеркнутыми одна строка и один столбец, при этом незанятая клетка одна. При заполнении этой последней клетки число занятых клеток составит m+n-2+1=m+n-1.Проверим, что векторы, соответствующие занятым опорным решением клеткам, линейно независимы. Применим метод вычеркивания. Все занятые клетки можно вычеркнуть, если проделать это в порядке их заполнения.
Метод минимальной стоимости.
Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,...,m, j=1,2,...,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем. Теорема5. Решение транспортной задачи, построенное методом минимальной стоимости, является опорным.

Метод потенциалов

Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией, которая в каждой клетке совершает поворот на 90, Знаком " + " отмечают те вершины, в которых перевозки увеличиваются, а знаком "- " - те вершины, в которых перевозки уменьшаются. Перемещение какого-то количества единиц груза по циклу означает увеличение перевозок на это количество единиц в положительных вершинах и уменьшение перевозок на это же количество единиц в отрицательных вершинах. При этом, если перевозки остаются неотрицательными, план остается допустимым. Стоимость плана при этом может меняться. Ценой цикла называется увеличение стоимости перевозок при перемещении единицы груза по этому циклу. Очевидно, цена цикла равна алгебраической сумме стоимостей, стоящих в вершинах цикла, при этом стоимости в положительных вершинах берутся со знаком " +", а стоимости в отрицательных вершинах берутся со знаком " - ". Идея метода потенциалов состоит в следующем. Для любой свободной клетки транспортной таблицы всегда существует единственный цикл, положительная вершина которого лежит в этой свободной клетке, а все остальные - в базисных. Если цена такого цикла отрицательна, то план можно улучшить перемещением перевозок по данному циклу. Количество единиц груза, которое можно переместить, определяется минимальным значением перевозок, стоящих в отрицательных вершинах цикла (если переместить большее число единиц груза, возникнут отрицательные перевозки). Если циклов с отрицательной ценой нет, то это означает, что дальнейшее улучшение плана невозможно, т.е. оптимальный план найден.

Вычислительная схема метода потенциалов

Шаг 1. Строим опорный план (методом северо-западного угла) с

n+m-1 базисными клетками. Шаг 2. Определяем платежи

для всех базисных клеток. Один из платежей (например a1) полагаем равньм нулю. Шаг 3. Считаем псевдостоимости для всех свободных клеток. Если

для всех клеток, то план оптимален. Вычисляем значение целевой функции L на этом плане и исследования прекращаем.

Шаг 4. Если есть свободная клетка, для которой то улучшаем план, перебрасывая перевозки по циклу этой свободной клетки. Шаг 5. Возвращаемся к шагу 2 для пересчета платежей нового опорного плана.

 

 

24Транспортная задача с ограничениями на пропускную способность.
Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1); 2), где и - постоянные величины.1. если, то необходимо прежде, чем решать задачу, сократить (уменьшить) запросы l-го поставщика и запросы k-го потребителя на оптимальном решении следует увеличить объем перевозки на величину.2. если, то необходимо вместо k-го потребителя с запросами ввести двух других потребителей. Один из них с номером k должен иметь запросы =, а другой с номером n+1 - запросы. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости, которая принимается равной сколь угодно большему числу М(М>>1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как =М - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+1) останется пустой, =0 и объем перевозки не превзойдет.В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной М>>1. В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо существование начального опорного решения.

 

25.Транспортная задача по критерию времени.
Задача по критерию времени возникает при перевозке срочных грузов. Как и в обычной транспортной задаче, имеется m поставщиков с запасами однородного груза в количестве и n потребителей, которым этот груз должен быть доставлен в объеме. Известно, i=1,2,,...,m, j=1,2,...,n - время, за которое груз доставляется от каждого i-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок груза, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и наибольшее время доставки всех грузов является минимальным.Составим математическую модель этой задачи. Обозначим - объем перевозимого груза от i-го поставщика j-му потребителю. Система ограничений задачи не отличается от системы ограничений обычной транспортной задачи. Пусть Х=() i=1,2,,...,m, j=1,2,...,n - некоторое опорное решение задачи. Запишем целевую функцию задачи. Обозначим через Т(Х) наибольшее значение элементов матрицы Т=(), i=1,2,,...,m, j=1,2,...,n, соответствующих клеткам таблицы, занятым опорным решением: Т(Х)=. Таким образом, за время Т(Х) план перевозок будет выполнен полностью. Математическая модель имеет вид Т(Х)= (26), i=1,2,...,m, (27), j=1, 2,..., n, (28), i=1,2,,...,m+1, j=1,2,...,n. (29)Задача решается в следующем порядке. Находится начальное опорное решение Х1. определяется значение целевой функции Т(Х1)==. Все свободные клетки, которым соответствует значения >T(X1), исключаются из рассмотрения (перечеркиваются). Занимать эти клетки нецелесообразно, так как повысится значение целевой функции. Чтобы понизить ее значение, необходимо освободить клетку (l1, k1), в которой достигает максимума. Для этого строят так называемые разгрузочные циклы, которые могут включать в свой состав несколько свободных клеток. В каждом разгрузочном цикле, начиная с разгружаемой клетки (l1, k1), расставляются поочередно знаки "-" и "+" и осуществляется сдвиг на величину =. Если удается эту клетку разгрузить, то она исключается из рассмотрения (зачеркивается). Получается новое опорное решение Х2, на котором значение целевой функции меньше, чем на Х1. далее снова пытаются разгрузить клетку, соответствующую Т(Х2)= =. Процесс продолжается до тех пор, пока возможность разгрузить соответствующую клетку не исчезнет.

 

Задача о назначениях.

ЗАДАЧА О НАЗНАЧЕНИЯХ [assignment problem] — вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации “рабочий — станок” характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т. д.

Математически такие задачи — частный случай распределительных задач с той особенностью, что в них объемы наличных и требующихся для выполнения каждой работы ресурсов равны единице, т. е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях (обозначения см. в ст. “Распределительные задачи”). Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется матрицей оценок, результаты — в матрице назначений.

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

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

Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов:

1 этап:

1 Формализация проблемы в виде транспортной таблицы

2 В каждой строке таблицы найти наименьший элемент и вычесть его из всех элементов данной строки

3 Повторить ту же процедуру для столбцов

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

2 этап:

1 Найти строку, содержащую только одно нулевое значение, в его клетку помещается один элемент (0 обводится квадратиком). Если такие строки отсутствуют, допустимо начать с любой строки.

2 Зачеркнуть оставшиеся нулевые значения данного столбца

3 Повторять пп.1-2, пока продолжение указанной процедуры окажется невозможным

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

4 Найти столбец, содержащий только одно нулевое значение, в его клетку помещается один элемент.

5 Зачеркнуть оставшиеся нули в данной строке

6 Повторять пп.4-5, пока продолжение указанной процедуры окажется невозможным

Если выяснится, что таблица содержит неучтенные нули - повторить пп. 1-6

Если решение является допустимым, оно оптимально. Если нет - перейти к этапу 3.

3 этап: (Если решение является недопустимым)

1 Провести минимальное количество прямых через столбцы и строки матрицы таким образом, чтобы они проходили через все нули, содержащиеся в таблице

2 Найти наименьший из элементов, через которые не проходит ни одна прямая

3 Вычесть его из всех элементов, через которые не проходят прямые

4 Прибавить его ко всем элементам, лежащим на пересечении прямых

5 Элементы, через которые проходит только одна прямая, оставить неизменными

В результате в таблице появится как минимум одно новое нулевое значение. Вернуться к этапу 2 и повторить решение заново.