Решение транспортных задач с помощью MS Excel

РЕШЕНИЕ ТРАНСПОРТНЫХ ЗАДАЧ С ПОМОЩЬЮ  MICROSOFT EXCEL

Наше время характерно стремительным развитием компьютерной техники. Следовательно, мощным потоком программного обеспечения. Компьютерные технологии проникают во все сферы человеческой деятельности. Современный человек должен иметь не просто минимальные знания по информационным технологиям, а быть по настоящему подготовленным пользователем.

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

Рассмотрим следующую транспортную задачу. Для строительства четырех объектов используется кирпич, изготавливаемый на трех заводах. Ежедневно каждый из заводов может изготовить 100, 150 и 50 условных единиц кирпича (предложение поставщиков). Потребности в кирпиче  на каждом из строящихся объектов ежедневно составляют 75, 80, 60 и 85 условных единиц (спрос потребителей). Тарифы перевозок одной условной единицы кирпича с каждого из заводов к каждому из строящихся объектов задаются матрицей транспортных расходов С.

В левом верхнем углу произвольной (i,j) клетки стоит коэффициент затрат – затраты на перевозку единицы груза от i –го поставщика к j-му потребителю. Задача формулируется следующим образом: найти объемы перевозок для каждой пары «поставщик - потребитель» так, чтобы: мощности всех поставщиков были реализованы, спросы всех потребителей были удовлетворены, суммарные затраты на перевозку были бы минимальны. Обозначим через xijобъем перевозки от i –го поставщика к j-му потребителю. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных xij. Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляются для каждого столбца таблицы поставок:

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести ограничение не отрицательности переменных:

xij ≥0.

Суммарные затраты F на перевозку выражаются через коэффициенты затрат следующим образом:

Для математической постановки транспортной задачи в общей постановке обозначим через сij коэффициенты затрат, через Mi – мощности поставщиков, через Nj – мощности потребителей, (i=1,2,…,m)., (j=1,2,…,n), m – число поставщиков, n – число потребителей. Тогда система ограничений примет вид:

                                                  (1)

Система (7) включает в себя уравнения баланса по строкам и по столбцам.

При этом суммарная мощность поставщиков равна суммарной мощности потребителей, т.е.

Целевая функция в данном случае следующая:

                                  (2)

Таким образом, на множестве неотрицательных решений системы ограничений (1) найти такое решение, при котором значение целевой функции (2) будет минимально.

Рабочий лист EXCEL с введенными исходными данными для решения транспортной задачи  показан на рис 1.

Рис.1

Затем настраиваем программу «Поиск решения» как показано на рис. 2

Рис.2

В появившемся окне "Поиск решения" установите курсор на кнопку "Выполнить" и щелкните левой клавишей мыши.

После того как на рабочем листе появилось решение (рис.3) в появившемся диалоговом окне "Результаты поиска решения" (рис.4) установите курсор на переключатель "Восстановить исходные значения" и щелкните левой клавишей мыши. Для завершения расчетов щелкните на кнопке ОК.

Рис.3

Рис.4

Таким образом, мы нашли решение рассматриваемой транспортной задачи.

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

Транспортная задача. 

Транспортная задача является наиболее популярной задачей линейного программирования и широко освещена в учебниках и справочниках. Популярнейшим методом аналитического решения является метод потенциалов. Справочная система Excel содержит описание решения, но на наш взгляд она освещена крайне плохо, и не является простой в понимании, осмыслении сделанного и увиденного. Мы предлагаем свою методику решения. 

Целью решения транспортной задачи является нахождение плана грузоперевозок, чтобы общие затраты по перевозкам были минимальными. 

Пусть задана классическая транспортная задача с тремя поставщиками и пятью потребителями. 

Оформим лист Excel'я следующим образом: 

В ячейки (B4:F6) заносится матрица цен, далее в ячейки (B11:F13) помещаются любые значения больше нуля. В ячейках (G11:G13), вычисляются суммы ячеек (B11:F11; B12:F12; B13:F13) соответственно. В (B14:F14), вычисляются суммы ячеек (B11:B13; C11:C13; D11:D13; E11:E13; F11:F13) соответственно. В ячейку F16 записывается следующая формула: "=СУММПРОИЗВ (B11:F13;B4:F6)", вычисляющая произведение соответствующих элементов массивов, а затем суммирует получившиеся значения. 

Далее выделив ячейки (B11:F13) вызываем формат ячеек и в закладке "Число", выставляем число десятичных знаков равным нулю. 

Оформим окно поиска решений следующим образом:

1. Установить целевую ячейку    F16

2. Равной:                      Минимальному значению

3. Изменяя ячейки:                      B11:F13

4. Ограничения:                 B11:F13 >= 0    B14 = 100               C14 = 130

                                D14 = 80                E14 = 190               F14 = 100

                                G11 = 200               G12 = 175               G13 = 225

Нажимаем кнопку: "Выполнить" После нажатия кнопки лист Excel'я должен выглядеть следующим образом: 

Итак из ячейки F16 мы видим, что минимальные затраты на перевозку составляют: 1610 ед. А в ячейках (B11:F13) был получен план грузоперевозок. 

Задания для самостоятельного решения: 

1.
 

2.
 

3.
 

4.
 

5.
 

6.
 

7.
 

 

8.
 

9.
 

Решение транспортных задач в среде Excel

Продолжение темы, начатой в "КВ" №21/2005

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

Постановка задачи

Компания, где Василий нашел вакантное место курьера, имеет два склада, на которых хранится товар, и три магазинчика - конторы, где этот товар реализуется. Задача Васи заключается в строгом выполнении плана, который он получает каждый день. В качестве транспортного средства он использует старый, но выносливый советский велосипед, который не позволяет перевозить всю партию за раз. Поэтому нашему ненасытному другу приходится мотаться туда-сюда. На что он опять копит? Что же он там перевозит? Не ждите от меня ответов на эти вопросы, если б знал - давно бы уже сказал бы.

И тут Василий, изнывая от мучительных болей в ногах и предвидя жесткий выговор со стороны начальства за невыполнение работы в намеченный срок, задумался: можно ли составить с учетом выдаваемого ему плана такой маршрут движения, чтобы на выполнение всего задания уходило минимум времени и сил. Конечно, можно! Этим мы сейчас и займемся.

Составление математической модели

Сначала необходимо проделать подготовительную работу, а именно - определить тарифы на каждом участке будущего оптимального плана перевозок. Поскольку Вася заинтересован в том, чтобы делать свою работу максимально быстро, то в качестве тарифов в данной задаче выступает время, потраченное на перевозку единицы товара из n-го склада в m-ую контору. При помощи карты Минска (CityInfo) с учетом времени на перекур и на подкачку шин, Вася оценил среднее время перевозки товара из каждого склада в каждую контору. В результате была составлена таблица 1.

Данная транспортная задача относится к типу задач с неправильным балансом (47<>50), но нас это не должно смущать. Я вас уверяю, мы ничего не будем решать вручную. Хотелось бы отметить, что в реальной жизни транспортные задачи с правильным балансом встречаются не очень часто. Далее задачу необходимо, как говорится, формализировать, т.е. записать в виде уравнений (формул). Пусть X - количество единиц товара, перевозимых из каждого склада в каждую контору. Тогда X11 - количество единиц товара, перевозимых из первого склада в первую контору, X12 - количество единиц товара, перевозимых из первого склада во вторую контору, и т.д. (такие предложения пишутся простым копированием, если вы не знали.;) Поскольку задача с неправильным балансом, то необходимо ввести также фиктивную контору. Все переменные представлены в таблице 2.