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

Рассмотрим пару двойственных задач:

{AX<=B

{X≥0 (1)

F=CX max

{A^TY≥C^T

{Y≥0 (2)

W=B^TYmin

Основное нер-во двойственности. Если X=(x1,x2…xn) и Y=(y1,y2…ym) – произвольные допустимые решения пары двойственных задач (1) и (2), то

F=CX<= W=B^TY.

Следствие 1.Если допустимые решения x(x1x2…xn) и у(у1у2…ym) пары ДЗ 1 и 2 таковы, что CX= B^TY, то х и у – опт-решения задач.

Следствие 2. Если целевая ф-ия F задачи 1 не ограничена сверху на допустимом множестве задачи, то у задачи 2 нет ни одного допустимого решения. Если целевая ф-ия W задачи 2 не ограничена снизу на доп-м множ-ве задачи, то у задачи 1 нет ни одного доп-го решения.

Первая теорема двойственности. Если одна из пары двойственных задач имеет решение, то и другая имеет решение, причем оптимальные значения целевых ф-ий совпадают Fmax=Wmim. Вторая ТД. Допустимые решения X и У пары ДЗ оптимальны тогда и только тогда, когда значения цел-х ф-ий F и W на этих решениях совпадают:

Fmax=CX= B^TY=Wmin.

18. Транспортные задачи. Экономико-матем-ая модель тз.

Исходные параметры модели ТЗ

1) m – количество пунктов отправления, n – количество пунктов

назначения.

2) Am – запас продукции в пункте отправления Ai (i =1,n )

3) Bn – спрос на продукцию в пункте назначения Bj ( j =1,m)

4) cij – тариф (стоимость) перевозки единицы продукции из пункта

отправления Am в пункт назначения Bn

Искомые параметры модели ТЗ

1) xij – количество продукции, перевозимой из пункта отправления Am в

пункт назначения Bn

2) f(X) – транспортные расходы на перевозку всей продукции.

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

19. Теорема о разрешимости тз.

Для того, чтобы ТЗ имела доп-ое решение, необходимо и достаточно, чтобы выполнялось условие

( 4)

Р ассмотрим условие (1) первую строку E по i а вторую E по j. Докажем, что если i и j явл-ся доп-м решением, то выполняется усл-е 4. Суммируем 1 строку по I, вторую по j.

Левые части получ-х рав-в отличны только порядком суммирования. Докажем теперь достаточность.

20. Нахождение исходного опорного решения тз.

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

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

3. Метод двойного предпочтения. Сначала по строкам, затем по столбцам выбираются клетки с наим-м тарифом и расставляются предпочтения «+», там где ++ - отправляется первоначально, далее по оставшимся клеткам аналогично.