Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Метод минимального элемента
|
|
В этом случае учитывается стоимость перевозок. Заполнение начинается с клетки, имеющей минимальную стоимость перевозки (если таких клеток несколько, то выбирают первую по порядку).
| Поставщики | Мощность поставщиков | Потребители и их спрос | |||||||
| B 1 | B 2 | B 3 | B 4 | ||||||
| A1 | |||||||||
| A2 | |||||||||
| A3 | |||||||||
| A4 |
Число заполненных клеток m+n-1=7, затраты наперевозку
S= 20*1+30*2+60*1+10*4+70*6+10*4+30*0=640.
Общая стоимость перевозки меньше, чем в предыдущем способе, но это не означает, что так бывает всегда, что способ лучше. Далее этот первоначальный план нужно улучшать. Для этого предназначен метод потенциалов. Потенциалы клетки - это целые числа, Ui и Vi, такие, что их сумма равна Ci., их истинной стоимости
Находим сумму потенциалов для занятых клеток из системы уравнений Ui+Vi= Ci.
| Поставщики | Мощность поставщиков | Потребители и их спрос | ||||||||
| B 1 | B 2 | B 3 | B 4 | |||||||
| U | ||||||||||
| A1 | -1 | U1=0 | ||||||||
| -1 | ||||||||||
| A2 | U2=2 | |||||||||
| -1 | -1 | |||||||||
| A3 | U3=2 | |||||||||
| -4 | ||||||||||
| A4 | -3 | -5 | -2 | U4=-4 | ||||||
| V | V1 =4 | V2=4 | V3=-1 | V4=2 |
V1 +U1 = 1 V2 + U3 = 6 V2 + U4 = 0 V3 + U2 = 1 V4 + U1 = 2 V4 + U2 = 4
V4 + U3 = 4
Решаем систему в целых числах. Поскольку число уравнений на единицу меньше числа неизвестных, то зададимся любым значением одного из Ui и Vi Пусть U1 =0. Решением системы будет следующее:
V1 = 1 U1 = 0
V2= 4 U2 = 2
V3 = -1 U3 = 2
V4 = 2 U4 = -4
Затем находим для свободных клеток косвенные стоимости перевозок как сумму соответствующих потенциалов. (в таблице это числа, находящиеся под стоимостями перевозок), далее находим для свободных клеток разность истинных и косвенных стоимостей перевозок (записываем ниже разностей).
План считается оптимальным, если не будет отрицательных разностей, а у нас их три, значит план нуждается в улучшении, то есть нужно построить новый план, для которого значение критерия должно быть меньше, чем для имеющегося. Если клеток с отрицательными разностями несколько, то выбирается клетка с максимальной по абсолютной величине разностью, если все разности равны (как у нас), то рассматриваем клетки с отрицательными разностями по порядку.
Занимаем эту клетку, ставим в нее (.) и начинаем строить цикл так, чтобы он прошел по занятым клеткам и имел вид прямоугольников. Расставляем знаки (+) и (-) по углам цикла, начиная с выбранной клетки - для нее (+). Затем из 2 клеток с (-) (-30 и -70) выбираем меньшее число по абсолютной величине (30) и от него в новом плане, соблюдая знаки, движемся по циклу, причем в клетках со знаком (+) это число прибавляем, а в клетках со знаком (-) -вычитаем.
| Поставщики | Мощность поставщиков | Потребители и их спрос | ||||||||
| B 1 | B 2 | B 3 | B 4 | |||||||
| U | ||||||||||
| A1 | -2 | U1=0 | ||||||||
| A2 | U2=3 | |||||||||
| -2 | -1 | |||||||||
| A3 | U3=3 | |||||||||
| A4 | -2 | -5 | -3 | U4=-3 | ||||||
| V | V1 =1 | V2=3 | V3=-2 | V4=1 |
Опять получены 2 клетки с отрицательными разностями, следовательно, план можно еще улучшить.
Из 2 отрицательных наименьшее число - 1.
| Поставщики | Мощность поставщиков | Потребители и их спрос | ||||||||
| B 1 | B 2 | B 3 | B 4 | |||||||
| U | ||||||||||
| A1 | U1=0 | |||||||||
| A2 | U2=11 | |||||||||
| A3 | U3=3 | |||||||||
| A4 | -2 | -3 | -2 | U4=-3 | ||||||
| V | V1 =1 | V2=3 | V3=0 | V4=1 |
Для этого плана нет клеток с отрицательными разностями, следовательно, этот план оптимальный, окончательный. Для него стоимость перевозки
S=10*1+10*2+40*3+30*60+30*0+60*1+50*4=590.
Date: 2015-06-11; view: 569; Нарушение авторских прав