В практике обычно при составлении экономико-математической модели задачи транспортного типа приходится вводить целый ряд дополнительных ограничений, вследствие чего поиск оптимального решения усложняется.
Рассмотрим наиболее часто встречающиеся случаи.
Нередко целесообразно минимизировать суммарные затраты на производство и транспортировку продукции. С подобной задачей можно столкнуться при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из отдаленного источника, но зато при меньшей его себестоимости. В таких задачах критерием оптимальности служит сумма затрат на производство единицы груза и на его перевозку.
Часто необходимо вводить ограничения, согласно которым, отдельные поставки от определенного поставщика определенному потребителю должны быть исключены (из-за отсутствия достаточного количества транспорта или необходимых условий хранения груза, чрезмерной перегрузки коммуникаций и т. п.). Значит, в матрице перевозок, содержащей оптимальный план, определенные клетки должны остаться свободными. Это достигается искусственным завышением показателей в клетках, перевозки через которые следует запретить, до значений, заведомо больших всех, с которыми их придется сравнивать в процессе решения задачи.
Иногда приходится учитывать ограничения по пропускной способности некоторых маршрутов. Если, например, по маршруту i-j можно провезти не более d единиц груза, то j- й столбец матрицы перевозок разбивается на два: j’-й и j’’. В первом спрос принимается равным разности между действительным спросом bj и ограничением d, во втором — равным ограничению d. Тарифы в обоих столбцах одинаковы и равны данным, но в первом в клетке, соответствующей ограничению, вместо истинного тарифа ставится искусственно завышенный тариф М (клетка блокируется). Затем задача решается обычным способом.
Может случиться, что некоторые поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет в условиях всей задачи. Тогда соответственно уменьшают запасы груза у поставщиков и спрос у потребителей и решают задачу относительно тех поставок, которые не обязательны.
Во многих задачах транспортного типа целевая функция максимизируется. Поэтому при составлении начального опорного плана в первую очередь стараются заполнять клетки, с наиболее высокими значениями показателя критерия оптимальности. Выбор клетки, подлежащей заполнению при переходе от одного опорного плана к другому, должен производиться не по отрицательной, а по положительной оценке. Оптимальным будет опорный план, которому в распределительной таблице сопутствуют свободные клетки с неположительными оценками.
2. Порядок выполнения работы
Решить транспортную задачу в матричной постановке (вариант задается преподавателем).
Имеется 5 поставщиков и 6 потребителей, их запас, потребности стоимости перевозки единицы груза от каждого поставщика каждому потребителю приведены в таблице. Необходимо учесть дополнительные условия:
1) от поставщика А1 к потребителю В1 необходимо перевезти не более 10*n единиц груза;
2) от поставщика А4 к потребителю В2 необходимо перевезти не менее 50+n единиц груза;
3) от поставщика А3 к потребителю В3 необходимо перевезти 15+n единиц груза;
4) от поставщика А5 к потребителю В6 поставка невозможна.
Требуется составить опорное решение методами минимального элемента, Фогеля, северо-западного угла. Опорное решение получить методом потенциалов из опорного, полученного методом северо-западного угла.
B1 | B2 | B3 | B4 | B5 | B6 | запас | |
A1 | 1+n | 2+n | 8+n | 11+n | 5+n | 7+n | 100+10*n |
A2 | 7+n | 5+n | 3+n | 4+n | 1+n | 1+n | 240-10*n |
A3 | 6+n | 9+n | 2+n | 3+n | 10+n | 3+n | 350-10*n |
A4 | 2+n | 13+n | 4+n | 5+n | 4+n | 2+n | 245+10*n |
A5 | 5+n | 10+n | 4+n | 8+n | 9+n | 1+n | 45+100*n |
Спрос | 45+10*n | 350-10*n | 210-10*n | 85+10*n | 125+10*n | 245-10*n |