Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Решение транспортных задач
В качестве примера приведем решение транспортной задачи ЛП с помощью таблицы. Транспортная таблица состоит из m строк и n столбцов. В правом верхнем углу каждой клетки будем ставить стоимость Сij перевозки единицы груза из Ai в Bj, а в центр клетки поместим перевозку Xij.
Таблица 5.6
Таблица 5.7
Составим опорный план. Можно применить метод «северо-западного угля». Пусть пункт В1 подал заявки на 18 единиц груза. Удовлетворим ее из запасов А1. После этого в нем остается еще 30-18=12 единиц груза. Отдадим их пункту В2. Но заявка этого пункта еще не удовлетворена. Выделим остаток 27-12 из запасов А2 и т.д. рассуждая аналогичным образом, составим таблицу 5.8. Полученный план перевозок является опорным, но вряд ли он является оптимальным в смысле стоимости перевозок.
Напомним, что прямая, которая имеет с областью, по крайней мере, одну общую точку, притом так, что вся область лежит по одну сторону от этой прямой, называется опорной по отношению к этой области. Таким образом, задача ЛП на геометрическом языке может быть сформулирована так: среди прямых уровня функции цели ¦ найти опорную по отношению к ОДР и притом так, чтобы вся область лежала со стороны больших значений ¦. Наш план - не оптимальный. Сразу видно, что его можно улучшить, если произвести в нем «циклическую перестановку», уменьшив перевозки в «дорогой» клетке (2.3) со стоимостью 12. но зато, увеличив перевозки в «дешевой» клетке (2.4) со стоимостью 6. чтобы план оставался опорным, мы должны при этом сделать одну из свободных клеток базисной, а одну из базисных - свободной. Сколько единиц груза можем мы перенести по циклу следующему циклу: (2.4) ®(3.4) ®(3.3) ®(2.3), увеличивая перевозки в нечетных вершинах цикла и уменьшая в четных? Очевидно, не больше 11 единиц (иначе перевозки в клетке (3.4) стали бы отрицательными). Также очевидно, что в результате циклического переноса допустимый план остается допустимым - баланс заявок и запасов не нарушается. Произведем перенос и запишем улучшенный план в таблицу 5.8. таблица 5.8
Таблица 5.9
посмотрим, что мы сэкономили. Общая стоимость плана в табл. 5.7 равна: ‡ 1=18´13+12´7+15´8+33´12+9´10+11´8+15´10+15´15=1287. Общая стоимость плана табл. 5.6 равна: ‡ 2=18´13+12´7+15´8+22´12+11´6+20´10+15´10+15´15=1243. Таким образом, нам удалось уменьшить стоимость перевозок на 44 единицы. Действительно алгебраическая сумма стоимостей, стоящих в вершинах цикла со знаком «+», если перевозки в этой вершине увеличиваются, и со знаком «-», если уменьшаются (так называемая «цена цикла»). в данном случае равна 6-8+10-12=-4. Значит, при переносе одной величины груза по этому циклу стоимость уменьшается на 4. А мы перенесем 11 единиц. Следовательно, цена цикла 4. 11=44. Попробуем еще раз улучшить план табл. 5.8 с помощью цикла (табл. 5.9) с ценой: 5-15+14-13=9. Перебрасывая 15 единиц груза, сокращаем стоимость на: 9. 15=135.
|