Численные методы оптимизации. Рейзлин В.И. - 95 стр.

UptoLike

ВУЗ:

ТПУ | Томск

Составители:

Рейзлин В.И.

Рубрика:

Оптимизация

Достаточность. Пусть план

потенциален, так что существует система

, удовлетворяющая (7.8–7.9). Тогда для любого допустимого плана

' [ ' ]

ij m n





 

1 1 1 1 1 1 1 1

' ' ' '

m n m n n m m n

ij ij j i ij j ij i ij

i j i j j i i j

c x v u x v x u x

       

    

     

1 1 1 1 1 1

n m n m m n

j j i i j ij i ij

j i j i i j

v b u a v x u x

     

    

     

 

1 1 1 1 1 1 1 1

n m m n n m n m

j ij i ij j i ij ij ij

j i i j j i j i

v x u x v u x c x

       

    

   

т.е. стоимость перевозок по любому плану

не меньше стоимости перевозок

по потенциальному плану

Следовательно, план

оптимален.

Необходимость. Будем рассматривать транспортную задачу, как задачу

линейного программирования с минимизацией линейной формы

 

min

ij ij

Q X c x



  



при соответствующих ограничениях. Заполним симплексную таблицу и рас-

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

таблицу будем заполнять, повернув.

–

…

–

…

–

…

–

…

–

Q

-1

…

–1

…

–1

…

–1

…

–1

…

–1

…

–1

…

1 w=

…

–b

…

–b

…

–b

Получаем, что двойственная задача имеет вид:

max

j j i i

w b v a u



  



Заказать работу

Вы здесь

Численные методы оптимизации. Рейзлин В.И. - 95 стр.

UptoLike

ВУЗ:

Рейзлин В.И.

Оптимизация

Страницы