Информационный сайт

 

Реклама
bulletinsite.net -> Книги на сайте -> Программисту -> Сигал И.Х. -> "Введение в прикладное дискретное программирование " -> 15

Введение в прикладное дискретное программирование - Сигал И.Х.

Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование — М.: ФИЗМАТЛИТ, 2003. — 240 c.
ISBN 5-9221-0377-6
Скачать (прямая ссылка): vvedenievprikladnoeprogrammirovanie2003.djvu
Предыдущая << 1 .. 9 10 11 12 13 14 < 15 > 16 17 18 19 20 21 .. 84 >> Следующая


= 0, > 0.

(2.1.22)

Числа Cij — затраты на перевозку единицы груза из г в j. Под d^ можно понимать, например, плату за аренду транспортных средств,

Cy (Хг3)

0

Xtj

не зависящую от их загрузки, либо затраты на строительство магистрали от каждого пункта і до каждого пункта j, не зависящие от будущих грузопотоков. Предполагается, что Cij >0, d^ > 0, г = 1,2,. ..,ш; j = 1,2,...,п.

График функции Cij (Xij) схематически изображен на рис. 2.4.

Рис. 2.4 Задачу (2.1.18)-(2.1.22) назы-

вают транспортной задачей с фиксированными доплатами или неоднородной транспортной задачей. Очевидно, что если все = 0, задача превращается в обычную транспортную задачу. В противном же случае эта задача из-за разрывности каждого слагаемого (2.1.22) в нуле (см. рис. 2.4) вообще выпадает из рамок линейного программирования; однако путем введения дополнительных целочисленных переменных ее удается свести к частично целочисленной задаче линейного программирования.

Способ такого сведения был указан М. Балинским. Он состоит в следующем. Найдем величины

Mij = min (cii,bj), і = 1,2,..., m; j = 1,2, ...п.

Введем целочисленные переменные

(2.1.23)

У ij = Sign(Zii) = Рассмотрим задачу

Xij — 0, Xij > 0.

ЕЕ (CijXij + dijUij) min

І= I j = I

при дополнительном условии

0 ^ Xij ^ Mijijij, і — 1,2,..

(2.1.24)

(2.1.25)

(2.1.26)

Частично целочисленная задача (2.1.25), (2.1.19)-(2.1.21), (2.1.26) эквивалентна исходной задаче (2.1.18)-(2.1.22). Действительно, при Uij =0в силу (2.1.24) автоматически получаем Xij = 0, а при = = 1 неравенства (2.1.26) становятся излишними, так как в любом
Гл. 2. Модели дискретного программирования

41

допустимом плане транспортной задачи условия хц < Mij выполнены всегда. Наоборот, если в некотором оптимальном плане задачи (2.1.25), (2.1.19)-(2.1.21), (2.1.26) будет хц = 0, то соответствующее уц должно быть нулем (если оно окажется положительным, то план не будет оптимальным, ибо, уменьшив уц, мы не нарушим ограничений и придадим целевой функции (2.1.25) меньшее значение). Наконец, если Xij > 0, то в силу условий (2.1.24) уц может быть только единицей.

Таким образом, целочисленные переменные у^ в этой постановке согласуют строительство магистралей между і и j (или, в зависимости от интерпретации, аренду транспорта для этой магистрали) и осуществление перевозок между І Hj.

Разумеется, к полученной целочисленной задаче применимы любые общие методы целочисленного программирования. Однако ее большие размеры (матрица ограничений при сведении данной задачи к общей задаче линейного программирования имеет размеры (тп + + т + п) х 2тп делают это затруднительным для задач «сколько-нибудь заметных» размеров. Специфическая структура матрицы ограничений, по-видимому, не принесет в этом случае серьезного облегчения при практическом решении задач.

Поэтому естественно пытаться использовать здесь специфику задачи в ином направлении — в направлении создания специализированных приближенных методов. Простой приближенный метод был предложен в 1961 г. М. Балинским. Идея этого метода основана на рассмотрении задачи с отброшенным условием целочисленности (2.1.24). Данная идея выражается в следующей теореме.

Теорема 2.2 (теорема Балинского). Пусть X1 = ||ж-||, Y1 = = WijW — оптимальное решение задачи (2.1.25), (2.1.19)-(2.1.21), (2.1.26 . Тогда

X1ij=MijV1ij. (2-1.27)

Из этой теоремы следует, что при поиске оптимального решения (плана) задачи с фиксированными доплатами (2.1.25), (2.1.19)-

(2.1.21), (2.1.26) при отказе от требования целочисленности переменных yij можно выразить из (2.1.27) через Xij:

Xij

^ = MT/

После подстановки у^ в целевую функцию (2.1.25) получим

т п т п / ^

'У 'У (cIjXij + (Iij IJi j) = icijxij + X j j -JJ-

г=1 J=I i=l J=I V %3

тп п / \ т п

= E Ё (? + м~) Xii = Ё Ёc'aXii-

і= I j=I ' %3 ' і= I j=I

В результате мы пришли к обычной транспортной задаче с матрицей
42 Разд. I. Предмет и модели дискретного программирования

затрат ||С"||: т п

E E c'aXii ^ min • (2.1.28)

І=1 j = I

Таким образом, транспортная задача с фиксированными доплатами аппроксимирована обычной транспортной задачей (2.1.28), (2.1.19)-

(2.1.21), компьютерное решение которой не представляет никаких трудностей.

По оптимальному плану X* = \х.

ij і

естественным образом выписывается приближенный план X0 = \\х

задачи (2.1.28), (2.1.19)- (2.1.21)

о и

Y0 = \\Уіі

задачи с фиксированными доплатами:

= Vij = O5 если ХЬ = о,

х

7*9. — т** .

7" —

Hj

4 ' (2.1.29)

= 1, если X*j > 0.

Благодаря своей простоте описанный прием (часто называемый методом Балинского) может широко применяться для приближенного решения реальных задач.

Поясним идею этого метода, обратившись к геометрической интерпретации (рис. 2.5). Попытаемся заменить на каждой магистрали (i,j) неоднородную функцию затрат Cij (Xij) однородной функцией CriiXij5 значения которой не бы

Ij^lJ 5

превышали бы значений сц (xij) для Xij < Mij. Если потребовать, ЧТОбы Прямые C1-Xij и пересекались В точке Xi3 мы получим
Предыдущая << 1 .. 9 10 11 12 13 14 < 15 > 16 17 18 19 20 21 .. 84 >> Следующая
Реклама
Авторские права © 2009 AdsNet. Все права защищены.
Rambler's Top100