Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Решение. 1) Найдем суммарные запасы продукции и суммарные потребности 150+380=890; b1+b2+b3+b4=270+190+340+200=1000




1) Найдем суммарные запасы продукции и суммарные потребности 150+380=890; b 1+ b 2+ b 3+ b 4=270+190+340+200=1000. Поскольку ,то есть отсутствует баланс между производимой продукцией и потребнос-тями, то мы имеем задачу открытого типа. Вводим фиктивного поставщика A 4, который имеет запас продукции в объеме (един.). Все тарифы на доставку продукции фиктивного поставщика равны нулю, т.е. c 41= c 42= c 43= c 44=0

Данные задачи заносим в таблицу 1.

Табл. 1.

  Поставщики Потребители Запас груза, ai
B 1 B 2 B 3 B 4
A 1          
A 2          
A 3          
A 4          
Потребность в грузе, bj          

 

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

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

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

.

 

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

ui+vj=cij,

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

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

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

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

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

u 1=1 u 3=3 v 1= 0 v 3= 4

u 2=0 u 4=0 v 2= 2 v 4=0

 

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

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

s 11= c 11-(u 1+ v 1) =7-(1+0) =6 ³ 0 s 24= c 24-(u 2+ v 4) = 8-(0+0) =8 ³ 0 s 42= c 42-(u 4+ v 2) = 0-(0+2) = -2

s 13= c 13-(u 1+ v 3) = 6-(1+4) =1 ³ 0 s 32= c 32-(u 3+ v 2) = 5-(3+2) = 0 s 43= c 43-(u 4+ v 3) = 0-(0+4) = -4

s 21= c 21-(u 2+ v 1) = 5-(0+0) =5 ³ 0 s 34= c 34-(u 3+ v 4) = 9-(3+0) = 6 ³ 0 s 44= c 44-(u 4+ v 4) = 0-(0+0) = 0

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

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

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

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

min (x 33, x 41)=min (220, 110)=110.

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

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

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

.

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

u 1=5 u 3=7 v 1= -4 v 3= 0

u 2=4 u 4=0 v 2= -2 v 4= -4

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

s 11=7-(5-4) =6 ³ 0 s 24=8-(4-4) = 8 ³ 0 s 41=0-(0-4) = 4 ³ 0

s 13=6-(5+0) =1 ³ 0 s 32=5-(7-2) = 0 s 42=0-(0-2) =2 ³ 0

s 21=5-(4-4) =5 ³ 0 s 34=9-(7-4) = 6 ³ 0 s 44=0-(0-4) = 4 ³ 0

 

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

.

 

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

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

Ответ: , f min=2800 ден.ед.

,

 




Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 331; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.015 сек.