Решение транспортной задачи методом потенциалов

Матрица, отражающая особенности решаемой задачи, принимает следующий вид табл. На эти склады товары можно только за­возить. Зная V3, мы теперь можем найти U3: По аналогии вычисляем все оставшиеся потенциалы: 6. В следующем примере мы рассмотрим такую транспортную задачу, применение к которой метода «северо-западного» угла для нахождения опорного плана даст вырожденный опорный план. Сток Исток Запасы: 10 7 6 8 31 31 5 6 5 4 48 22 3 23 8 7 6 7 38 18 20 Заявки: 22 34 41 20 117 Перенесем единиц груза по циклу 2,4 +, 3,4 - , 3,3 +, 2,3 - , уменьшив этим значение целевой функции на 40 единиц. Таким образом, нами сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Считать, что маршрут транспортировки всего суммар­ного объема избытка товара может проходить через любой промежуточный пункт. Примем в качестве единицы измерения общего количества требуемой продук­ции всех видов какую-либо удобную общепринятую меру, напри­мер тонну. Эта дополнительная клетка находится в столбце, в котором была записана промежуточная рента. Все оставшиеся ресурсы по станциям погрузки распределяем между клетками третьего столбца в клетки А 1В 3 и А 2В 3. Перенести какое-то количество единиц груза по означенному циклу, это значит увеличить перевозки, стоящие в положительных вершинах цикла, на это количество единиц, а перевозки, стоящие в отрицательных вершинах уменьшить на то же количество.

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

Теперь мы более подробно рассмотрим особенности данной задачи как задачи линейного программирования и познакомимся с двумя методами ее решения — классическим методом решения транспортной задачи с помощью транспортной таблицы и методом потенциалов. Подробное описание метода и пример можно посмотреть Основа метода в нахождении разности по модулю между парой минимальных тарифов в каждой строке и столбце. Пусть имеется транспортная задача с балансовыми условиями Стоимость перевозки единицы груза из A i в B j равна C ij ; таблица стоимостей задана. Правило "северо-западного угла" При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Решение транспортной задачи Так как транспортная задача является задачей линейного программирования, то основные этапы ее решения будут такими: Iэтап. Математические модели в экономике. Любая задача транспортного типа, как задача линейно­го программирования, может быть решена симплекс-методом.

Запасные части для предприятий железнодорожного транспорта изготавливаются на заводах по ремонту подвижного состава и производству запасных частей и других специализированных предприятиях. Очевидно, что в общем случае опорный план, являясь допустимым, не является оптимальным. Иначе говоря, существует некоторый план с меньшим функционалом. Продолжая так, после конечного числа шагов заполняют все клетки, в которых помещены кружки с заключенными в них числами. Нераспределенных остатков по запасам для a 1 меньше см. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце - заявке. В вершинах укажем соответствующие объемы запасов и потребностей.

Если для всех небазисных клеток условие 3 выполняется, то рассматриваемый план будет оптимален. Общий принцип определения оптимального пла­на транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала на­ходят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. Вот именно в таких случаях и во множестве других приходится решать транспортную задачу. Перевозка единицы груза из пункта в пункт объективно стоит условных единиц. Сток Исток Запасы: 10 5 4 40 - e 20 20 e 6 4 5 23 23 7 3 6 20+ e 20 - e Заявки: 20 20 43 83 Чтобы избежать этого, нарушаем баланс запасов и заявок на e в 1 и 3 строках, не нарушая общего баланса. В нашем случае таковой является а 2,b 3 и обозначает загруженую клетку, которая должна стать свободной. Результаты этапа «Поиск решения» Как видно из рис. Предположим, что план x ij невырожденный число базисных клеток в таблице перевозок ровно m + n -1.

Нахождение опорного плана методом «северо-западного угла» Метод «северо-западного» угла реализует интерактивный поиск опорного решения. Первый i — номер поставщика, второй j — номер потребителя. Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. Правило "северо-западного угла" При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Наиболее часто применяются метод потенциалов модифицированный распредели­тельный метод и метод дифференциальных рент. Последовательность решения задачи 2. Отличие состоит только в том, что когда одна из отрицательных вершин цикла окажется в базисной клетке с нулевой перевозкой, нужно переносить по этому циклу нулевую перевозку.

Похожие документы
Карта сайта
Obi обои каталог
Исковое заявление по земельным спорам образец
Награда за информацию список преступников

Комментарии