Лекции по "Развитию операционных систем"

 

Начальный опорный план получим по правилу «минимального элемента».

Загрузку начинаем с клетки, которой соответствует наименьший тариф cij≠0 всей матрицы тарифов. В нашем случае минимальным тарифом является с14=1, который соот-ветствует клетке (1, 4). В эту клетку вписываем x14=min (360; 200)=200. Исключаем четвертый столбец. У поставщика A1 осталось еще 160 единиц продукции, которые по-местим в клетку (1, 2). Исключаем первую строку. Но потребителю B2 необходимо еще 30 ед. продукции, которые берем у поставщика A2, и помещаем в клетку (2, 3). Исключаем второй столбец. Оставшиеся у поставщика A2 120 ед. продукции помещаем в клетку (2, 3). Исключаем вторую строку. Необходимые потребителю B3 220 ед. продукции берем у поставщика A3 и помещаем в клетку (3, 3). Исключаем третий столбец. В пункте A3 оставшиеся 160 ед. продукции помещаем в клетку (3; 1). Исключаем третий столбец. Оставшиеся 110 ед. помещаем в клетку (4; 1).

Полученный нами план является невырожденным, так как выполняется условие базисных клеток: m+n-1=4+4-1=7, и число заполненных клеток тоже 7. А значит, полу-чено опорное решение, которое запишем матрицей

.

 

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

ui+vj=cij,

где ui – потенциал i-го поставщика;

     vj – потенциал j-го потребителя;

     cij – тариф заполненной клетки.

В нашем случае получаем следующие уравнения:

Полагая v4=0, получаем следующие потенциалы:

   u1=1                   u3=3                                       v1= 0                    v3= 4

   u2=0                   u4=0                                     v2= 2                     v4=0

 

Все полученные данные заносим в таблицу 2.

Далее вычисляем оценки свободных клеток по формуле:  .

s11=c11-(u1+v1) =7-(1+0) =6 ³ 0   s24=c24-(u2+v4) = 8-(0+0) =8 ³ 0   s42=c42-(u4+v2) = 0-(0+2) = -2

s13=c13-(u1+v3) = 6-(1+4) =1 ³ 0   s32=c32-(u3+v2) = 5-(3+2) = 0      s43=c43-(u4+v3) = 0-(0+4) = -4

s21=c21-(u2+v1) = 5-(0+0) =5 ³ 0   s34=c34-(u3+v4) = 9-(3+0) = 6 ³ 0  s44=c44-(u4+v4) = 0-(0+0) = 0

Так как s42<0, и s43<0 то полученный план не является оптимальным. Наиболее потенциальной клеткой является клетка (4; 3). Поэтому строим для клетки (4; 3) замк-нутый цикл, который в таблице 2 выделяем пунктирной линией:

(4, 3)→(3, 3)→(3, 1)→(4, 1).

Свободной клетке условно приписываем знак «+», тогда следующей клетке по ходу часовой стрелки – знак «-» и т.д., знаки чередуются.

В отрицательных вершинах цикла определяем наименьшую загрузку клетки, т.е.

min (x33, x41)=min (220, 110)=110.

Количество продукции, равное 110ед., прибавляем к поставкам в клетках со знаком «+» и вычитаем из поставок в клетках со знаком «-».

Получаем новый план, который заносим в таблицу 3.

Проверяем, является ли полученный план оптимальным. Для этого каждому поставщику и потребителю придаем число – потенциал. Вычисляем потенциалы так же, как это делали выше:

.

Полагая v3=0, получаем следующие потенциалы, которые заносим в таблицу 4:

   u1=5                   u3=7                                       v1= -4                    v3= 0

   u2=4                   u4=0                                     v2= -2                    v4= -4

Вычисляем оценки свободных клеток:

   s11=7-(5-4) =6 ³ 0        s24=8-(4-4) = 8 ³ 0                 s41=0-(0-4) = 4 ³ 0

   s13=6-(5+0) =1 ³ 0        s32=5-(7-2) = 0                        s42=0-(0-2) =2 ³ 0

   s21=5-(4-4) =5 ³ 0         s34=9-(7-4) = 6 ³ 0                  s44=0-(0-4) = 4 ³ 0

 

Поскольку все sij>0, то полученный план является оптимальным, который можно представить в виде матрицы

.

 

2)  Суммарные затраты fmin при этом будут составлять:

Потребитель B3 не дополучил 110 единиц продукции.

Ответ: ,  fmin=2800 ден.ед.

,