Методы нахождения первоначального базисного распределения поставок плана транспортной задачи
С.
И. НиколаеваБиблиографическое описание статьи для цитирования:
Николаева
С.
И. Методы нахождения первоначального базисного распределения поставок плана транспортной задачи // Научно-методический электронный журнал «Концепт». –
2013. – Т. 3. – С.
1551–1555. – URL:
http://e-koncept.ru/2013/53313.htm.
Аннотация. Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального) по стоимости плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно
сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок.
Ключевые слова:
линейное программирование, транспортная задачи, базисный план, программа «оптимал», симплексный метод
Текст статьи
Николаева Светлана Ивановнавысшая квалификационная категория, преподаватель математики и информатики, бюджетное образовательное учреждение Чувашской Республики среднего профессионального образования «Алатырский сельскохозяйственный техникум» Минобразования Чувашии, г. Алатырь Чувашская Республикаperemenka@umi.ru
Методы нахожденияпервоначального базисного распределения поставок транспортной задачиАннотацияТранспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального) по стоимости плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок. При решении транспортной задачи необходимо:Обеспечить всех потребителей ресурсамиРаспределить все произведенные ресурсыПереместить ресурсы от производителей к потребителям с наименьшими затратамиОт каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.Цель:Выявить наиболее оптимальный метод нахождения опорного плана транспортной задачи
Цель определяет задачи:Познакомиться с основными методами нахождения базисного распределения поставок;Рассмотреть алгоритмы методов нахождения опорного плана;Проанализировать преимущества и недостатки каждого метода нахождения опорного плана транспортной задачиИзучив основные методы нахождения базисного плана транспортной задачи, проанализировав их преимущества и недостатки, можно сделать выводы:1)Наиболее простым алгоритмом нахождения базисного плана является метод «северозападного угла», но он является наиболее далеким от оптимального.2)Метод Фогеля является достаточно трудоемким, но позволяет получить наименьшие суммарные затраты перевозок3)Для нахождения базисного плана методом Фогеля и симплексным методом можно воспользоваться возможностями программы «Оптимал» и электронной таблицы EXCEL, что ускорит расчеты.
Итак, наиболее близким к оптимальному плану решения транспортной задачи является метод Фогеля. Во многих случаях опорный план транспортной задачи, составленный именно этим методом также является и оптимальным.
Ключевые слова
транспортная задачи, базисный план, программа «Оптимал», симплексный метод, линейное программирование
Список цитируемой литературы:1.Баумоль У. Экономическая теория и исследование операций. –М.; Наука, 2004.2.Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. Димитровград, 2002.3.Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебноепособие. Димитровград, 20024.Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. М.: Высшая школа, 20045.Исследование операций в экономике; Под ред. проф. Н.Ш. Кремера ЮНИТИ 20036.Красс М. Математика для экономических специальностей. Учебник. 3е изд., перераб и доп. М, Экономист, 2004.
ВведениеВ повседневной жизни мы часто сталкиваемся с необходимостью решать оптимизационные задачи. Например, заходя в магазин, мы стоим перед дилеммой максимального удовлетворения своих потребностей, соизмеряя их с возможностями нашего кошелька. Любой менеджер постоянно решает разнообразные проблемы, начиная с планирования штата сотрудников, фонда зарплаты и заканчивая составлением оптимального плана производства, планированием рекламной кампании по продвижению продукции и оптимизацией капиталовложений.Командиры на военных сборах решают задачи оптимального указания целей и наведения оружия на эти цели в расчете на максимальное поражение противника. Менеджер по транспортным перевозкам решает задачу минимизации транспортных издержек в условиях наиболее полного удовлетворения интересов производителей и потребителей.
Данная статьяпосвящена знакомству с одной из самых популярных и продвинутых экономикоматематических моделей транспортной задаче. Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального) по стоимости плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок. При решении транспортной задачи необходимо:Обеспечить всех потребителей ресурсамиРаспределить все произведенные ресурсыПереместить ресурсы от производителей к потребителям с наименьшими затратамиОт каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.Цель работы:Выявить наиболее оптимальный метод нахождения опорного плана транспортной задачи
Цель работы определяет задачи:Познакомиться с основными методами нахождения базисного распределения поставок;Рассмотреть алгоритмы методов нахождения опорного плана;Проанализировать преимущества и недостатки каждого метода нахождения опорного плана транспортной задачи
1.Общая постановка транспортной задачиОбщая постановка транспортнойзадачисостоит в определении оптимального плана перевозок некоторого однородного груза из тпунктов отправления в ппунктов назначения .При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из iго пункта отправления в jйпункт назначения, через –запасы груза в iм пункте отправления, через –потребности в грузе в j–м пункте назначения, а через –количество единиц груза, перевозимого из iго пункта отправления в jйпункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции (1) при условиях (2) (3) (4) Поскольку переменные удовлетворяют системам уравнений (2) и (3) и условию неотрицательности(4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 1. Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планомтранспортной задачи. Определение 2. План , при котором функция (1) принимает свое минимальное значение, называется оптимальнымпланомтранспортной задачи. Обычно исходные данные транспортной задачи записывают в виде таблицы 1. Таблица 1. Исходные данные транспортной задачи
Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е. (5) то модель такой транспортной задачи называется закрытой.Если же указанное условие не выполняется, то модель транспортной задачи называется открытой. [1]Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство(5). В случае превышения запаса над потребностью, т. е. вводится фиктивный (n+1)–йпункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (5). Аналогично, привводится фиктивный (m+1)–йпункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (5). Число переменных в транспортной задаче с тпунктами отправления и ппунктами назначения равно пт, а число уравнений в системах (2) и (3) равно п+т.Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно п+т–1. Следовательно, опорный план транспортной задачи может иметь не более п + т–1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности п+т–1, то план является невырожденным, а если меньше –то вырожденным. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Транспортные задачи бывают:1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)[1]
2. Методы нахождения опорного плана транспортной задачи
2.1. Симплексный метод
Симплексметодэто итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.Транспортная задача относится к задачам линейного программирования. Одним из методов нахождения опорного плана является симплексный метод.Идея симплексметода относительно проста.[2]
Рассмотрим задачу:Фирма должна отправить некоторое количество кроватей с трёх складов в четыре магазина. На складах имеется соответственно 60, 120и 100кроватей, а для четырехмагазинов требуется соответственно 20, 110, 40и 110кроватей. Стоимости перевозок задаются матрицей:1 2531652
6374
Как следует спланировать перевозку, чтобы её стоимость была минимальной?[3]Решение:Построим экономикоматематическую модель задачи.Данная транспортная задача является закрытой, так как суммарная мощность поставщиков равна суммарной мощности потребителей.Таблица 2. Данные транспортной задачиПоставщикиМощность поставщиковПотребители и их спрос123420110401101601253
21201652
31006374
Пусть Xijпоставка клетки (i,j). Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:
Х11+Х12+Х13+Х14=60Х21+Х22+Х23+Х24=120Х31+Х32+Х33+Х34=100
Чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляются для каждого столбца поставок:
Х11+Х21+Х31=20Х12+Х22+Х32=110Х13+Х23+Х33=40Х14+Х24+Х34=110
Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому Xij≥0, (i=1,2,3,j=1,2,3,4).Суммарные затраты на перевозку выражаются через коэффициенты затрат и поставки следующим образом:F=1Х11+2Х12+5Х13+3Х14+1Х21+6Х22+5Х23+2Х24+6Х31+3Х32+7Х33+4Х34 minДля решения задачи воспользуемся возможностями электронной таблицы EXCELи найдем значения переменных с помощью Поиска решения.
Рисунок 1. Решение транспортной задачи симплексным методом с помощью EXCEL
Рисунок 2. Ответы транспортной задачи симплексным методом с помощью EXCEL
Суммарные затраты равны:1420ден. ед.
2.2. Метод «Северозападного» угла
При использовании «Северозападного» метода опорный план начинают строить с левого верхнего (северозападного угла) матрицы перевозок по следующему алгоритму:1)Первому потребителю назначается ресурс от первого производителя. При этом возможны следующие варианты:Запрос первого потребителя удовлетворен не полностью, тогда недостающий ресурс первому потребителю добавляют от второго производителя и при необходимости от третьего производителя, до тех пор пока потребности первого потребителя не будут полностью удовлетворены.Запрос первого потребителя удовлетворен полностью. Остаток ресурса от первого производителя назначают второму потребителю, а при необходимости и третьему потребителю.Запрос первого потребителя обеспечен полностью ресурсом первого производителя и ресурс первого производителя израсходован полностью. Далее переходим к обеспечению запроса второго потребителя.2)Затем обеспечивают потребности второго потребителя по образцу первого потребителя. И так далее пока не будут обеспечены запросы всех потребителей.[4]
Рассмотрим нахождение базисногоплана транспортной задачи с помощью «северозападного угла»:Дадим переменной Х11максимально возможное значение, или максимально возможную поставку вклетку (1,1) –«северозападный» угол таблицы поставок: Х11=min(60,20)=20.После этого спрос 1 потребителя будет полностью удовлетворен, в результате чего первый столбецвыпадет из рассмотрения. В таблице поставок найдем новый «северозападный» уголклетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1 поставщик уже отдал 20 единиц груза и у него осталось только 40=6020 единиц груза, получаем, что Х12=min(40,110)=40. После этого мощность 1 поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы. В оставшейся таблице снова находим «северозападный» угол и т.д. В результате получаем исходное распределение поставок:
Таблица 3. Нахождение базисного плана транспортной задачи методом «северозападного угла»
ПоставщикиМощность поставщиковПотребители и их спрос123420110401101601
202
4053
212016
705
402
1031006374
100
Суммарные затраты: F=1*20+2*40+6*70+5*40+2*10+4*100=1140 Число заполненных клеток в полученном распределении оказалось равным m+n1=3+41=6, то есть числу базисных переменных.Существенный недостаток этого метода состоит в том, что он построен без учета значений коэффициентов затрат задачи.[5]
2.3. Метод наименьших затрат
Суть метода состоит в том, что в матрице стоимостей С = {сij}выбирается стоимость минимальной перевозки сij. Затем назначается максимальный объем ресурса от производителя iк потребителю jдля данной перевозки. При этом возможны три варианта:1) производитель iимеет ресурса больше, чем надо потребителю j.В этом случае удовлетворяется полностью заявка потребителя j', а остаток произведенного ресурса будет распределен после. Так как потребность потребителя jудовлетворена полностью, то исключается из рассмотрения столбецматрицы стоимости, принадлежащий jму потребителю;2) производитель iимеет ресурса меньше, чем надо потребителю jВ этом случае весь имеющийся ресурс производителя iназначается потребителю jНедостающая часть ресурса потребителю jбудет назначена потом. Так как весь ресурс производителя iисчерпан полностью, то из рассмотрения удаляется строка матрицы стоимости, принадлежащая производителю i3) производитель iимеет ресурса столько, сколько надо потребителю j.В этом случае, аналогично рассмотренным выше случаям, из рассмотрения удаляются и строка, и столбецматрицы стоимости.Затем из матрицы стоимостей выбирается следующая минимальная стоимость перевозки ресурса от производителя к потребителю, удовлетворяются потребности следующего потребителя ресурса (полностью или частично) и удаляется из рассмотрения очередная строка или столбец матрицы стоимостей. Процесс повторяется до тех пор, пока не будет распределен полностью весь произведенный ресурс между всеми потребителями. Так как ресурса произведено ровно столько, сколько нужно потребителям, то задача распределения будет обязательно выполнена.[4]
Рассмотрим нахождение базисного плана транспортной задачи с помощьюметода наименьших затрат:Находим в таблице поставок клетки с наименьшим коэффициентом затрат. Таких клеток две
(1,1) и (2,1), с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1,1) Х11=min(60,20)=20 идля клетки (2,1) Х21=min(120,20)=20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам в клетку (2,1). В результате спрос первого потребителя удовлетворен и первый столбец таблицы поставок выпадает из последующего рассмотрения.В оставшейся таблицу наименьшим коэффициентом затрат обладают две клетки: С12=С24=2. Сравним максимально возможные поставки этих двух клеток: для клетки (1,2) Х12=min(60,110)=60, для клетки (2,4) Х24=(12020;110)=100. Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: Х24=100. При этом из рассмотрениявыпадет строка таблицы поставок.
Аналогично заполним все оставшиеся клетки таблицы:
Таблица 4. Нахождение базисного плана транспортной задачи с помощью метода наименьших затрат
ПоставщикиМощность поставщиковПотребители и их спрос123420110401101601 2 6053
21201 206
5
2
100310063 507 404
10
Суммарные затраты: F=1*20+2*60+3*50+2*100+7*40+4*10=810
Как и ожидалось, при использовании метода «северозападного» угла суммарные затраты больше, чем при применении метода наименьших затрат. Таким образом, во втором случае мы находимся ближе к оптимуму, чем в первом.[5]
2.3.Метод Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).[5]Так как метод Фогеля достаточно трудоемкий и требует много времени для решения, воспользуемся специальной программой «Оптимал». Данная программная система предназначена для ускорения процесса обучения студентов решению транспортных задач. Заполним таблицу: Рисунок 3. Заполнение таблицы в программе «Оптимал» для нахождения базисного распределения методом Фогеля
Найдем опорный план методом ФогеляРисунок 4. Нахождение опорного плана транспортной задачи методом Фогеля
Получим: Рисунок 5. Ответы решения транспортной задачи методом Фогеля
Суммарные затраты равны 760 ден. ед.Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальныйплан. Заключение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования задачи о назначениях, сетевые, календарного планирования.Изучив основные методы нахождения базисного плана транспортной задачи, проанализировав их преимущества и недостатки, можно сделать выводы:4)Наиболее простым алгоритмом нахождения базисногоплана является метод «северозападного угла», но он является наиболее далеким от оптимального.5)Метод Фогеляявляется достаточно трудоемким, но позволяет получить наименьшие суммарные затраты перевозок6)Для нахождения базисного плана методом Фогеля и симплексным методом можно воспользоваться возможностями программы «Оптимал» и электронной таблицы EXCEL, чтоускорит расчеты.
Итак, наиболее близким к оптимальному плану решения транспортной задачи является метод Фогеля. Во многих случаях опорный план транспортной задачи, составленный именно этим методомтакже является и оптимальным.
Методы нахожденияпервоначального базисного распределения поставок транспортной задачиАннотацияТранспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального) по стоимости плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок. При решении транспортной задачи необходимо:Обеспечить всех потребителей ресурсамиРаспределить все произведенные ресурсыПереместить ресурсы от производителей к потребителям с наименьшими затратамиОт каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.Цель:Выявить наиболее оптимальный метод нахождения опорного плана транспортной задачи
Цель определяет задачи:Познакомиться с основными методами нахождения базисного распределения поставок;Рассмотреть алгоритмы методов нахождения опорного плана;Проанализировать преимущества и недостатки каждого метода нахождения опорного плана транспортной задачиИзучив основные методы нахождения базисного плана транспортной задачи, проанализировав их преимущества и недостатки, можно сделать выводы:1)Наиболее простым алгоритмом нахождения базисного плана является метод «северозападного угла», но он является наиболее далеким от оптимального.2)Метод Фогеля является достаточно трудоемким, но позволяет получить наименьшие суммарные затраты перевозок3)Для нахождения базисного плана методом Фогеля и симплексным методом можно воспользоваться возможностями программы «Оптимал» и электронной таблицы EXCEL, что ускорит расчеты.
Итак, наиболее близким к оптимальному плану решения транспортной задачи является метод Фогеля. Во многих случаях опорный план транспортной задачи, составленный именно этим методом также является и оптимальным.
Ключевые слова
транспортная задачи, базисный план, программа «Оптимал», симплексный метод, линейное программирование
Список цитируемой литературы:1.Баумоль У. Экономическая теория и исследование операций. –М.; Наука, 2004.2.Павлова Т.Н, Ракова О.А. Линейное программирование. Учебное пособие. Димитровград, 2002.3.Павлова Т.Н, Ракова О.А. Решение задач линейного программирования. Учебноепособие. Димитровград, 20024.Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие для ВУЗов. М.: Высшая школа, 20045.Исследование операций в экономике; Под ред. проф. Н.Ш. Кремера ЮНИТИ 20036.Красс М. Математика для экономических специальностей. Учебник. 3е изд., перераб и доп. М, Экономист, 2004.
ВведениеВ повседневной жизни мы часто сталкиваемся с необходимостью решать оптимизационные задачи. Например, заходя в магазин, мы стоим перед дилеммой максимального удовлетворения своих потребностей, соизмеряя их с возможностями нашего кошелька. Любой менеджер постоянно решает разнообразные проблемы, начиная с планирования штата сотрудников, фонда зарплаты и заканчивая составлением оптимального плана производства, планированием рекламной кампании по продвижению продукции и оптимизацией капиталовложений.Командиры на военных сборах решают задачи оптимального указания целей и наведения оружия на эти цели в расчете на максимальное поражение противника. Менеджер по транспортным перевозкам решает задачу минимизации транспортных издержек в условиях наиболее полного удовлетворения интересов производителей и потребителей.
Данная статьяпосвящена знакомству с одной из самых популярных и продвинутых экономикоматематических моделей транспортной задаче. Транспортная задача относится к классу задач линейного программирования. Транспортная задача решает проблему нахождения оптимального (минимального) по стоимости плана распределения и перемещения ресурсов от производителей к потребителям. Проблема оптимизации стоимости перевозок актуальна и на сегодняшний день, так как позволяет фирмам и предприятиям существенно сократить расходы на транспорт. Правильная организация перевозок позволяет устранить встречные и дублирующие перевозки, сократить количество дальних перевозок. При решении транспортной задачи необходимо:Обеспечить всех потребителей ресурсамиРаспределить все произведенные ресурсыПереместить ресурсы от производителей к потребителям с наименьшими затратамиОт каждого производителя ресурс может перемещаться к любому потребителю и измеряться в одних единицах измерения.Цель работы:Выявить наиболее оптимальный метод нахождения опорного плана транспортной задачи
Цель работы определяет задачи:Познакомиться с основными методами нахождения базисного распределения поставок;Рассмотреть алгоритмы методов нахождения опорного плана;Проанализировать преимущества и недостатки каждого метода нахождения опорного плана транспортной задачи
1.Общая постановка транспортной задачиОбщая постановка транспортнойзадачисостоит в определении оптимального плана перевозок некоторого однородного груза из тпунктов отправления в ппунктов назначения .При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из iго пункта отправления в jйпункт назначения, через –запасы груза в iм пункте отправления, через –потребности в грузе в j–м пункте назначения, а через –количество единиц груза, перевозимого из iго пункта отправления в jйпункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции (1) при условиях (2) (3) (4) Поскольку переменные удовлетворяют системам уравнений (2) и (3) и условию неотрицательности(4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.
Определение 1. Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планомтранспортной задачи. Определение 2. План , при котором функция (1) принимает свое минимальное значение, называется оптимальнымпланомтранспортной задачи. Обычно исходные данные транспортной задачи записывают в виде таблицы 1. Таблица 1. Исходные данные транспортной задачи
Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е. (5) то модель такой транспортной задачи называется закрытой.Если же указанное условие не выполняется, то модель транспортной задачи называется открытой. [1]Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т. е. чтобы выполнялось равенство(5). В случае превышения запаса над потребностью, т. е. вводится фиктивный (n+1)–йпункт назначения с потребностью и соответствующие тарифы считаются равными нулю: Полученная задача является транспортной задачей, для которой выполняется равенство (5). Аналогично, привводится фиктивный (m+1)–йпункт отправления с запасом груза и тарифы полагаются равными нулю: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (5). Число переменных в транспортной задаче с тпунктами отправления и ппунктами назначения равно пт, а число уравнений в системах (2) и (3) равно п+т.Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно п+т–1. Следовательно, опорный план транспортной задачи может иметь не более п + т–1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности п+т–1, то план является невырожденным, а если меньше –то вырожденным. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Транспортные задачи бывают:1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)[1]
2. Методы нахождения опорного плана транспортной задачи
2.1. Симплексный метод
Симплексметодэто итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.Транспортная задача относится к задачам линейного программирования. Одним из методов нахождения опорного плана является симплексный метод.Идея симплексметода относительно проста.[2]
Рассмотрим задачу:Фирма должна отправить некоторое количество кроватей с трёх складов в четыре магазина. На складах имеется соответственно 60, 120и 100кроватей, а для четырехмагазинов требуется соответственно 20, 110, 40и 110кроватей. Стоимости перевозок задаются матрицей:1 2531652
6374
Как следует спланировать перевозку, чтобы её стоимость была минимальной?[3]Решение:Построим экономикоматематическую модель задачи.Данная транспортная задача является закрытой, так как суммарная мощность поставщиков равна суммарной мощности потребителей.Таблица 2. Данные транспортной задачиПоставщикиМощность поставщиковПотребители и их спрос123420110401101601253
21201652
31006374
Пусть Xijпоставка клетки (i,j). Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:
Х11+Х12+Х13+Х14=60Х21+Х22+Х23+Х24=120Х31+Х32+Х33+Х34=100
Чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляются для каждого столбца поставок:
Х11+Х21+Х31=20Х12+Х22+Х32=110Х13+Х23+Х33=40Х14+Х24+Х34=110
Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому Xij≥0, (i=1,2,3,j=1,2,3,4).Суммарные затраты на перевозку выражаются через коэффициенты затрат и поставки следующим образом:F=1Х11+2Х12+5Х13+3Х14+1Х21+6Х22+5Х23+2Х24+6Х31+3Х32+7Х33+4Х34 minДля решения задачи воспользуемся возможностями электронной таблицы EXCELи найдем значения переменных с помощью Поиска решения.
Рисунок 1. Решение транспортной задачи симплексным методом с помощью EXCEL
Рисунок 2. Ответы транспортной задачи симплексным методом с помощью EXCEL
Суммарные затраты равны:1420ден. ед.
2.2. Метод «Северозападного» угла
При использовании «Северозападного» метода опорный план начинают строить с левого верхнего (северозападного угла) матрицы перевозок по следующему алгоритму:1)Первому потребителю назначается ресурс от первого производителя. При этом возможны следующие варианты:Запрос первого потребителя удовлетворен не полностью, тогда недостающий ресурс первому потребителю добавляют от второго производителя и при необходимости от третьего производителя, до тех пор пока потребности первого потребителя не будут полностью удовлетворены.Запрос первого потребителя удовлетворен полностью. Остаток ресурса от первого производителя назначают второму потребителю, а при необходимости и третьему потребителю.Запрос первого потребителя обеспечен полностью ресурсом первого производителя и ресурс первого производителя израсходован полностью. Далее переходим к обеспечению запроса второго потребителя.2)Затем обеспечивают потребности второго потребителя по образцу первого потребителя. И так далее пока не будут обеспечены запросы всех потребителей.[4]
Рассмотрим нахождение базисногоплана транспортной задачи с помощью «северозападного угла»:Дадим переменной Х11максимально возможное значение, или максимально возможную поставку вклетку (1,1) –«северозападный» угол таблицы поставок: Х11=min(60,20)=20.После этого спрос 1 потребителя будет полностью удовлетворен, в результате чего первый столбецвыпадет из рассмотрения. В таблице поставок найдем новый «северозападный» уголклетку (1,2) и дадим в нее максимально возможное значение. Учитывая, что 1 поставщик уже отдал 20 единиц груза и у него осталось только 40=6020 единиц груза, получаем, что Х12=min(40,110)=40. После этого мощность 1 поставщика полностью реализована и из рассмотрения выпадет первая строка таблицы. В оставшейся таблице снова находим «северозападный» угол и т.д. В результате получаем исходное распределение поставок:
Таблица 3. Нахождение базисного плана транспортной задачи методом «северозападного угла»
ПоставщикиМощность поставщиковПотребители и их спрос123420110401101601
202
4053
212016
705
402
1031006374
100
Суммарные затраты: F=1*20+2*40+6*70+5*40+2*10+4*100=1140 Число заполненных клеток в полученном распределении оказалось равным m+n1=3+41=6, то есть числу базисных переменных.Существенный недостаток этого метода состоит в том, что он построен без учета значений коэффициентов затрат задачи.[5]
2.3. Метод наименьших затрат
Суть метода состоит в том, что в матрице стоимостей С = {сij}выбирается стоимость минимальной перевозки сij. Затем назначается максимальный объем ресурса от производителя iк потребителю jдля данной перевозки. При этом возможны три варианта:1) производитель iимеет ресурса больше, чем надо потребителю j.В этом случае удовлетворяется полностью заявка потребителя j', а остаток произведенного ресурса будет распределен после. Так как потребность потребителя jудовлетворена полностью, то исключается из рассмотрения столбецматрицы стоимости, принадлежащий jму потребителю;2) производитель iимеет ресурса меньше, чем надо потребителю jВ этом случае весь имеющийся ресурс производителя iназначается потребителю jНедостающая часть ресурса потребителю jбудет назначена потом. Так как весь ресурс производителя iисчерпан полностью, то из рассмотрения удаляется строка матрицы стоимости, принадлежащая производителю i3) производитель iимеет ресурса столько, сколько надо потребителю j.В этом случае, аналогично рассмотренным выше случаям, из рассмотрения удаляются и строка, и столбецматрицы стоимости.Затем из матрицы стоимостей выбирается следующая минимальная стоимость перевозки ресурса от производителя к потребителю, удовлетворяются потребности следующего потребителя ресурса (полностью или частично) и удаляется из рассмотрения очередная строка или столбец матрицы стоимостей. Процесс повторяется до тех пор, пока не будет распределен полностью весь произведенный ресурс между всеми потребителями. Так как ресурса произведено ровно столько, сколько нужно потребителям, то задача распределения будет обязательно выполнена.[4]
Рассмотрим нахождение базисного плана транспортной задачи с помощьюметода наименьших затрат:Находим в таблице поставок клетки с наименьшим коэффициентом затрат. Таких клеток две
(1,1) и (2,1), с коэффициентами затрат, равными 1. Сравним максимально возможные поставки для этих клеток: для клетки (1,1) Х11=min(60,20)=20 идля клетки (2,1) Х21=min(120,20)=20. Так как они совпадают, то максимально возможную поставку даем в любую из них. Например, даем поставку, равную 20 единицам в клетку (2,1). В результате спрос первого потребителя удовлетворен и первый столбец таблицы поставок выпадает из последующего рассмотрения.В оставшейся таблицу наименьшим коэффициентом затрат обладают две клетки: С12=С24=2. Сравним максимально возможные поставки этих двух клеток: для клетки (1,2) Х12=min(60,110)=60, для клетки (2,4) Х24=(12020;110)=100. Даем поставку в клетку (2,4), для которой максимально возможная поставка оказалась больше: Х24=100. При этом из рассмотрениявыпадет строка таблицы поставок.
Аналогично заполним все оставшиеся клетки таблицы:
Таблица 4. Нахождение базисного плана транспортной задачи с помощью метода наименьших затрат
ПоставщикиМощность поставщиковПотребители и их спрос123420110401101601 2 6053
21201 206
5
2
100310063 507 404
10
Суммарные затраты: F=1*20+2*60+3*50+2*100+7*40+4*10=810
Как и ожидалось, при использовании метода «северозападного» угла суммарные затраты больше, чем при применении метода наименьших затрат. Таким образом, во втором случае мы находимся ближе к оптимуму, чем в первом.[5]
2.3.Метод Фогеля
При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).[5]Так как метод Фогеля достаточно трудоемкий и требует много времени для решения, воспользуемся специальной программой «Оптимал». Данная программная система предназначена для ускорения процесса обучения студентов решению транспортных задач. Заполним таблицу: Рисунок 3. Заполнение таблицы в программе «Оптимал» для нахождения базисного распределения методом Фогеля
Найдем опорный план методом ФогеляРисунок 4. Нахождение опорного плана транспортной задачи методом Фогеля
Получим: Рисунок 5. Ответы решения транспортной задачи методом Фогеля
Суммарные затраты равны 760 ден. ед.Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальныйплан. Заключение
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования задачи о назначениях, сетевые, календарного планирования.Изучив основные методы нахождения базисного плана транспортной задачи, проанализировав их преимущества и недостатки, можно сделать выводы:4)Наиболее простым алгоритмом нахождения базисногоплана является метод «северозападного угла», но он является наиболее далеким от оптимального.5)Метод Фогеляявляется достаточно трудоемким, но позволяет получить наименьшие суммарные затраты перевозок6)Для нахождения базисного плана методом Фогеля и симплексным методом можно воспользоваться возможностями программы «Оптимал» и электронной таблицы EXCEL, чтоускорит расчеты.
Итак, наиболее близким к оптимальному плану решения транспортной задачи является метод Фогеля. Во многих случаях опорный план транспортной задачи, составленный именно этим методомтакже является и оптимальным.
