Экономико-математические методы и прикладные модели

Начальное распределение выберем по методу наименьших стоимостей. Порядок заполнения клеток: (3,1), (1,2), (4,3). (2,4), (1,5), (1,4), (3,5), (4,5)

Суммарные затраты:

f(x) = 6´18+7´15+8´32+8´5+8´40+7´10+14´7+16´13=1107

Рассмотрим процесс нахождения потенциалов для данного распределения.

Положим, Ui=0 Þ V2=U1+C12=7; V5=U1+C15

=7=U3+14=U4+16 Þ U3= -7, U4= -9; V3=U4+C43= -1; V4=U2+8=U1+8 Þ U2=U1=0; V4=8.

Найдем оценки: dij=(Ui+cij)-Vj:

11 0 15 0 0

(dij) = 13 1 11 0 8

0 -4 4 -3 0

8 -6 0 -5 0

Данный план не является оптимальным, т.к. есть отрицательные оценки.

Построим контур перераспределения для клетки (4,2). Наименьшая поставка в вершине контура со знаком “-” равна 13, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком “-” на 13 и увеличив поставки в клетках со знаком “+” на 13. результаты поставлены в таблице 2.

Суммарные затраты:

f(x) = 6´18+7´2+10´13+8´32+8´5+8´40+7-23+14-7=1127

Положим U1=0

V2 = U1+C12=7=U4+10 Þ U4 = -3

V3 = U4+8=5; V4=U1+8=8=U2+8 Þ U2=0

V5 = U1+7= 7 = U3+14 Þ U3= -7

V1 = U3+6= -1

dij = (Ui+Cij)-Vj

9 0 9 0 0

(dij) = 11 1 5 0 8

0 -3 -2 -3 0

14 0 0 1 6

Наличие отрицательных оценок свидетельствует о том, что план не является оптимальным. Построим контур перераспределения для клетки (3,2). Наименьшая поставка в вершине контура со знаком “-” равна 2. Произведем перераспределение поставок. Результаты представим в таблице 3.

Суммарные затраты:

f(x) = 6´18+10´2+10´13+8´32+8´5+8´40+7´25+14´7=1119

Положим, U1=0 Þ V4=8, V5=7; V4=U2+8 Þ U2=0

V5 = U3+14 Þ U3= 7-14= -7; V1= -7+6= -1; V2= -7+10= +3

V2=U4+10 Þ U4=3-10= -7; v3= -7+8=1

9 4 13 0 0

(dij) = 13 5 9 0 8

2 0 2 -3 0

 Скачать реферат