–ассмотрим задачу максимизации линейной формы (1) и, одновременно, задачу минимизации (2):


img001 img002

«адача (2) называетс¤ двойственной по отношению к пр¤мой (1) (и наоборот!).

ѕреобразовани¤ при решении пр¤мой и двойственной задач. ѕусть имеютс¤ пр¤ма¤ и двойственна¤ задачи следующего вида:


ѕр¤ма¤ задача:
img003
ѕредставим ограничени¤ в виде:
img004
ƒвойственна¤ к ней задача:
img005
img006

ƒл¤ ограничений пр¤мой задачи симплексна¤ таблица имеет вид:



 img007 Е img008 Е img009 1
img010= img011 Е img012 Е img013 img014
Е Е Е Е Е Е Е
img015= img016 Е img017 Е img018 img019
Е Е Е Е Е Е Е
img020= img021 Е img022 Е img023 img024
img025= img026 Е img027 Е img028 0

ѕусть img029 - разрешающий элемент. —делаем шаг модифицированного жорданова исключени¤ и получим таблицу:



 img030 Е img031 Е img032 1
img033= img034 Е img035 Е img036 img037
Е Е Е Е Е Е Е
img038= img039 Е 1 Е img040 img041
Е Е Е Е Е Е Е
img042= img043 Е img044 Е img045 img046
img047= img048 Е img049 Е img050 img051

где img052, и всю данную таблицу следует разделить еще на img053.

—имплексную таблицу дл¤ двойственной задачи запишем, развернув ее на img054. ѕолучаем:



 img055= Е img056= Е img057= img058
img059 img060 Е img061 Е img062 img063
Е Е Е Е Е Е Е
img064 img065 Е img066 Е img067 img068
Е Е Е Е Е Е Е
img069 img070 Е img071 Е img072 img073
1 img074 Е img075 Е img076 0

ѕусть img077 - направл¤ющий элемент. —делаем шаг обыкновенного жорданова исключени¤ (отличие от модифицированного состоит в том, что элементы в разрешающей строке мен¤ют знаки, а в столбце знаки сохран¤ютс¤;  в остальном преобразование остаетс¤ тем же):



 img078= Е img079= Е img080= img081
img082 img083 Е img084 Е img085 img086
Е Е Е Е Е Е Е
img087 img088 Е 1 Е img089 img090
Е Е Е Е Е Е Е
img091 img092 Е img093 Е img094 img095
1 img096 Е img097 Е img098 img099

где img100, и всю данную таблицу также следует разделить еще на img101.

«амечание: Ќе следует забывать при преобразовани¤х, что в данном случае у нас таблица развернута.

“аким образом, нетрудно заметить, что шаг модифицированного жорданова исключени¤ над симплексной таблицей пр¤мой задачи соответствует шагу обыкновенного жорданова исключени¤ над симплексной таблицей двойственной задачи. Ёти взаимно двойственные задачи можно совместить в одной симплексной таблице:


img102=
img103		 Е img104=
img105		 Е img106=
img107		 img108
1
img109  img110= img111 Е img112 Е img113 img114
Е Е Е Е Е Е Е
img115  img116= img117 Е img118 Е img119 img120
Е Е Е Е Е Е Е
img121 img122= img123 Е img124 Е img125 img126
1  img127= img128 Е img129 Е img130 0

ћожно показать, что, реша¤ основную задачу линейного программи­ровани¤, решаем и двойственную к ней. » наоборот. ѕричем, img131.

Hosted by uCoz