Задача I

Составить план перевозок зерна из районов А1, А2, А3, запасы которых составляют соответственно 250, 150 и 100 тыс. ц. в 5 пунктов В1, В2, В3, В4, В5, потребности которых 70, 110, 90, 130, 100 тыс. ц. Затраты на перевозку 1 тыс. ц. зерна приведены в таблице.

Минимизировать общие затраты на реализацию плана перевозок.

Решение:

а). Метод “северо-западного угла”. Установим характер задачи:

, итак

Þ модель задачи закрытая.

Составим распределительную таблицу:

Итак, получили план X1 такой, что в пункт В1 надо отправить зерна 70 тыс. ц., а в В2 110 тыс. ц. из района А1. В пункт В3 70 тыс. ц. из района А1 и 20 тыс. ц. из района А2. В пункт В4 130 тыс. ц. из района А2 и наконец в пункт В5 100 тыс. ц из района А3. Суммарные расходы на перевозку зерна составляют:

Z(X1) =70× 10+110× 4+70× 6+20× 12+130× 7+100× 5 =

= 700+440+420+240+910+500=3210 руб.

б). Метод “ минимального элемента “. Составим распределительную таблицу:

В результате полного распределения зерна получаем план X2, для которого значение целевой функции:

Z(X2) =10× 10+110× 4+130× 8+50× 5+100× 4+10× 9+90× 5=

=100+440+1040+250+400+90+450=2770 руб.

в). Построение нового улучшенного опорного плана по методу потенциалов.

Рассмотрим опорный план, найденный по методу “минимального элемента”.

	B1	B2	B3	B4	B5	ai	ui
A1
A2	+ 5 50				- 4		- 5
A3	- 9				+ 5		- 1
bj
uj

Проверяем условие m+n-1=3+5-1=7, число занятых клеток удовлетворяет этому условию.

Для определения потенциалов составляем уравнения:

u1+u1=10 Пусть u1=0, тогда u1=10

u1+u2=4 u2=4

u1+u4=8 u4=8

u2+u1=5 u2=5-10=-5

u2+u5=4 u5=4-(-5) =9

u3+u1=9 u3=9-10=-1

u3+u3=5 u3=5-(-1) =6

Определяем оценки свободных клеток:

S13=6-(6+0) =0 S23=12-(6-5) =11 S34=10-(8-1) =4

S15=20-(9+0) =11 S24=7-(8-5) =4 S35=5-(9-1) =-3

S22=11-(4-5) =12 S32=7-(4-1) =4

Так как не все Sij³ 0, то план не оптимальный. Наиболее перспективной клеткой является клетка (3;

5), так как S35 - наименьшая. С вершиной в клетке (3;

5) строим замкнутый цикл. В него войдут вершины: (3;

5), (3;

1), (2;

1), (2;

5).

Найдем l=min(10; 100) =10, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

	B1	B2	B3	B4	B5	ai	ui
A1	- 10 10		+ 6
A2	+ 5		12		- 4		- 5
A3			- 5		+ 5		- 4
bj
uj

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

S13=-3 S22=12 S24=4 S32=7

S15=11 S23=8 S31=3 S34=6

Так как не все Sij³ 0, то план не оптимальный. Наиболее перспективной клеткой является клетка (1;

3), так как S13 - наименьшая. С вершиной в клетке (1;

3) строим замкнутый цикл.

Найдем l=min(90; 90;

10) =10, после пересчета получим новый цикл. Заменяя старый цикл на новый, получим следующую таблицу:

Таблица.

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

S11=3 S22=9 S24=1 S32=4

S15=14 S23=8 S31=3 S34=3

Так как все Sij> 0, то план оптимальный и единственный. Затраты на перевозки по оптимальному плану составляют:

min Z=110× 4+10× 6+130× 8+70× 5+80× 4+80× 5+20× 5=

=440+60+1040+350+320+400+100=2710 руб.

Ответ: затраты на перевозки по оптимальному плану составляют 2710 рублей.