Оптимизация задачи методом потенциалов - Транспортная задача линейного проектирования

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

Допустимый план перевозок тогда и только тогда является оптимальным, когда каждому пункту отправления и назначения можно сопоставить величину, характеризующую уровень оценки груза в нем (потенциал) так, что множество этих потенциалов удовлетворяет следующим условиям:

    1. Разность потенциалов пунктов назначения и отправления, между которыми запланированы перевозки, равна затратам по транспортировке единицы груза между этими пунктами. 2. Аналогичные разности для всех остальных пар пунктов, между которыми запланированы перевозки, не превосходят затрат по транспортировке. С помощью критерия оптимальности можно не только проверить на оптимальность любой план, но и, в случае его неоптимальности, указать способ улучшения этого плана.

Для оптимизации транспортной задачи в качестве опорного возьмем план, составленный по методу Фогеля, так как у него стоимость наименьшая. Исходная таблица имеет вид:

Таблица 5

Телефонные станции

Районы

Свободные номера

I

II

III

IV

V

1

1

2

6

3
    2 25

25

2

6

2
    2 25
    1 5

3

30

3

2
    1 25
    2 5

1
    3 10

40

4
    2 30

5

6
    4 25

6

55

5

0

0
    0 15

0

0

15

Заявки

30

25

45

30

35

Обозначим потенциалы пунктов отправления (АТС) как U1...U5, а потенциалы пунктов назначения (районы) как V1...V5. Изобразим стрелками направления телефонизации районов.

Исходя из того, что

Vj=Ui+Cij, Cij -

Стоимость прокладки кабеля. Критерий оптимальности состоит в том, что разность потенциалов между пунктами назначения и отправления должна быть меньше стоимости перевозки: Vj-Ui-Cij0.

Для того чтобы проверить план на оптимальность, прежде всего вычисляем систему потенциалов (оценок единицы груза) в пунктах отправления и в пунктах назначения. В тех клетках, где стоят перевозки на оптимальность проверять не надо, т. к. там условие будет равно нулю. Проверяются пустые клетки.

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

Пусть U3=10, тогда:

V2=U3+C32=10+1=11

V3=U3+C33=10+2=12 U2=V3-C23=12-2=10

V5=U3+C35=10+3=13 U1=V5-C15=13-2=11

V4=U2+C24=10+1=11 U4=V4-C44=11-4=7

V1=U4+C41=7+2=9 U5=V3-C53=12-0=12

Для всех пустых клеток проверим критерий оптимальности: Vj-Ui-Cij0.

X11: V1-U1-C11=9-11-1=-3

X12: V2-U1-C12=11-11-2=-2

X13: V3-U1-C13=12-11-6=-5

X14: V4-U1-C14=11-11-3=-3

X21: V1-U2-C21=9-10-6=-7

X22: V2-U2-C22=11-10-2-1

X25: V5-U2-C25=13-10-3=0

X31: V1-U3-C31=9-10-2=-3

X34: V4-U3-C34=11-10-1=0

X42:V2-U4-42=11-7-5=-1

X43: V3-U4-C43=12-7-6=-1

X45: V5-U4-C45=13-7-6=0

X51: V1-U5-C51=9-12-0=-3

X52: V2-U5-C52=11-12-0=-1

X54: V4-U5-C54=11-12-0=-1

X55: V5-U5-C55=13-12-0=1

Максимальное положительное значение получили в клетке Х 55. то говорит о том, что построенный план неоптимальный. В этом месте добавим в таблицу перевозку К. Это вызывает нарушение баланса по столбцу 5, следовательно, в нем необходимо отнять К (клетка 3V). В строке 3 прибавим К (клетка 3III). Для соблюдения баланса по третьему столбцу и строке 5 отнимем К в клетке 5III.

Таблица 6

Телефонные станции

Районы

Свободные номера

I

II

III

IV

V

1

1

2

6

3
    2 25

25

2

6

2
    2 25
    1 5

3

30

3

2
    1 25
    2 5+К

1
    3 10-К

40

4
    2 30

5

6
    4 25

6

55

5

0

0
    0 15-К

0

0

+К

15

Заявки

30

25

45

30

35

Так как все расстояния положительны, то при распределении ресурсов К выбираем равным наименьшему числу от которого отнимаем. В данном случае К=10. Новая таблица имеет вид:

Таблица 7

Телефонные станции

Районы

Свободные номера

I

II

III

IV

V

1

1

2

6

3
    2 25

25

2

6

2
    2 25
    1 5

3

30

3

2
    1 25
    2 15

1

3

40

4
    2 30

5

6
    4 25

6

55

5

0

0
    0 5

0
    0 10

15

Заявки

30

25

45

30

35

Стоимость нового плана равна:

S=2*25+2*25+1*5+1*25+2*15+2*30+4*25+0*5+0*10=320 единиц.

Для новой матрицы строим новый рисунок:

Аналогичным образом определяем потенциалы для новой таблицы:

Пусть U3=10, тогда:

V2=U3+C32=10+1=11

V3=U3+C33=10+2=12 U2=V3-C23=12-2=10

V4=U2+C24=10+1=11 U4=V4-C44=11-4=7

V1=U4+C41=7+2=9 U5=V3-C53=12-0=12

V5=U5+C55=12+0=12 U1=V5-C15=12-2=10

Для всех пустых клеток проверим условий оптимальности:

X11: V1-U1-C11=9-10-1=-2

X12: V2-U1-C12=11-10-2=-1

X13: V3-U1-C13=12-10-6=-4

X14: V4-U1-C14=11-10-3=-2

X21: V1-U2-C21=9-10-6=-7

X22: V2-U2-C22=11-10-2=-1

X25: V5-U2-C25=12-10-3=-1

X31: V1-U3-C31=9-10-2=-3

X34: V4-U3-C34=11-10-1=0

X35: V5-U3-C35=12-10-3=-1

X42:V2-U4-42=11-7-5=-1

X43: V3-U4-C43=12-7-6=-1

X45: V5-U4-C45=12-7-6=-1

X51: V1-U5-C51=9-12-0=-3

X52: V2-U5-C52=11-12-0=-1

X54: V4-U5-C54=11-12-0=-1

Критерий оптимальности выполняется для всех пустых клеток, значит план оптимальный, окончательная стоимость 320 единиц.

Ввести m, n

Задать начальные значения элементам

Xij, Cij, Ai, Bj, Ui, Vj

Вычислить базисное допустимое решение

Вычислить коэффициенты Ui и Vj для Перейти к базисному

Базисного допустимого решения допустимому решению

Найти Cij для небазисных переменных

Проверка

Условия Cij>0

Получение оптимального плана

Листинг программы.

Procedure vvod_dan; (ввод данных с клавиатуры)

Begin

I:=1;

K:=0;

S1:=0;

While (k=0) and (i<n) do

Begin

Write('введите запaсы ',i,'-того поставщика: ');

Readln(a[i]);

If a[i]=0 then

Begin

K:=1;

I:=i-1;

End

Else

Begin

A1[i]:=a[i];

S1:=s1+a1[i];

I:=i+1;

End;

End;

J:=1;

K:=0;

S2:=0;

Textcolor(5);

While (k=0) and (j<m) do

Begin

Write('введите запрос ',j,'-того потребителя: ');

Readln(b[j]);

If b[j]=0 then

Begin

K:=1;

J:=j-1;

End

Else

Begin

B1[j]:=b[j];

S2:=s2+b1[j];

J:=j+1;

End;

End;

Textcolor(yellow);

K:=0;

If s1<s2 then

Begin

Writeln('ошибка ввода, проверьте баланс');

Readln;

Halt;

End;

If (s2<s1) and (k=0) then

Begin

Writeln('ошибка ввода, проверьте баланс');

Readln;

Halt; end;

X:=i;

Y:=j;

End;

Похожие статьи




Оптимизация задачи методом потенциалов - Транспортная задача линейного проектирования

Предыдущая | Следующая