Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Пример 13Сталеплавильная компания располагает 3 заводами М1, М2, М3, производящими за некоторый период времени 50, 30, 20 тыс тонн стали. Свою продукцию предприятие поставляет 4 потребителям С1, С2, С3, С4, потребности которых за тот же период времени составляют 12, 15, 25, 36 тыс. тонн стали. Стоимость перевозки 1 тыс. тонн стали с завода М1 потребителям равна 15, 19, 19, 15 ден.ед. соответственно; аналогичные стоимости перевоза с завода М2 равны 19, 18, 18, 10 ден.ед., а с завода М3 – 14, 16, 20, 18 ден. ед. Найти оптимальный план перевозок, при котором общие затраты на перевозку будут минимальны. Решение. Пусть запланировано перевести хij тонн стали. Стоимость перевозки будет равна сijxij, тогда целевая функция будет иметь вид: f(x)= min Ранг системы линейных уравнений: m+n -1 =3+5-1 = 7 Таблица 4.14
Исходный план перевозок имеет суммарную стоимость: f(x)=19·7+19·25+15·6+0·12+10·30+14·12+16·8=1294 ден. ед.
Находим потенциалы по формуле сij=ai+bj с15 = а1+б5 с14 = а1+б4 с13 = а1+б3 с12 = а1+б2 с32 = а3+б2 с24 = а2+б4 с31=а3+б1 б5=0-0=0. б4=15-0=15. б3=19-0=19. б2=19-0=19. а3=16-19= -3. а2=10-15= -5. б1=14-(-3)=17. Для каждой свободной клетки определяем относительные оценки по формуле ∆ij= сij-(ai+bj). ∆11=15-(0+17)=-2 ∆21=19-(-5+17)=7 ∆22= 18-(-5+19)=4 ∆23=18-(-5+19)=4 ∆25=0-(-5+0)=5 ∆33=20-(-3+19)=4 ∆34=18-(-3+15)=6 ∆35=0-(-3+0)=3
Матрица оценок:
Проанализировав матрицу оценок видно, что не выполняется условие ∆ij ≥0. Наименьшая отрицательная оценка по абсолютной величине равняется 2. Для этой клетки строим цикл. Q = 7. Теперь выполним сдвиг по циклу на число Q = 7. Таблица 4.15.
Находим потенциалы по формуле сij=ai+bj аналогично первому случаю. Для каждой свободной клетки определяем относительные оценки по формуле ∆ij= сij-(ai+bj) аналогично первому случаю. Матрица оценок:
Так как оценки всех свободных клеток строго больше 0, т.е. любой другой план будет менее оптимален. Это говорит о единственности оптимального плана. Поскольку все ∆ij ≥0, то задача решена и оптимальный план перевозок имеет суммарную стоимость: f(x)=15·7+19·25+15·6+0·12+10·30+14·5+16·15=1280 ден.ед.
|