Вопрос 6. Симметричные и несимметричные двойственные задачи( теория двойственности)

(I)

(I)это стандартная форма записи задачи ЛП ( прямая задача)

Составим Двойственную задачу (II) к задаче (I)

-компоненты(координаты) вектора y.

Ограничения двойственности

……………………………………

(II)

(II)

(II) называют двойственной задачей задачи (I)

(I) (II)

Замечание. Количество компонент (координат) вектора y в (II) совпадает с количеством столбцов .

Замечание. Задачи (I) и (II) являются двойственными по отношению друг к другу.

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

Замечание. Если в двойственной задаче целевая функция исследуется на min, то система ограничений указывается в виде неравенств

Замечание. Если в двойственной задаче целевая функция исследуется на max, то система ограничений указывается в виде неравенств

Вопрос 8. Метод северо-западного угла

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

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

Во избежании ошибок после построения начального базисного (опорного) решения необходимо проверить , что число занятых клеток равно m+n-1.

Вопрос 9. Метод потенциалов

Если допустимое решение Х =( ) i=1, 2,…m, j=1,2,…n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков (i=1, 2,…m) и потребителей (j=1,2,…n), удовлетворяющие следующим условиям

Группа равенств (1) используется как система уравнений

для нахождения потенциалов.

Так как число неизвестных системы на единицу больше числа уравнений,

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

из системы.

Группа неравенств (2) используется для проверки оптимальности опорного решения. Эти неравенства удобнее представить в следующем виде

Числа называются оценками для свободных клеток таблицы (векторов условий) транспортной задачи.

Вопос 10 Пример игры с 2 пальцами.

Два игрока показывают 1 или 2 пальца, при этом предполагают – какое кол-во пальцев укажет противник.

I II

1. 2

предположение предположение

II 1 I 2

Рассмотрим все возможные стратегии(конечное число).

(I, II) : 1) (1,1) 2) (1,2) 3) (2,1) 4) (2,2)

А налогично рассматриваются 2 игрока А 4х4

а11 а12 а13 а14

а21 а22 а23 а24

А = а31 а32 а33 а34

а41 а42 а43 а44

а 11 – выигрыш I игрока, при условии, что I принимает 1) и II принимает 1) стратегии

а 12 – выигрыш I игрока, при условии, что I применит 1) стратегию, а II – 2) стратегию.

I II

1. 2

I I 1 I 1

Выигрыш II игрока 1+2=3

а13 = выигрыш I игрока.