 |
Математическая модель транспортной задачи
|
|
|
|
Обозначим через V1, V2, V3, V4 объемы производства предприятий, а через W1, W2, W3, W4, W5, W6 – объемы потребления населенных пунктов. Через Pij (i=1,…, 4; j=1,…,6) обозначим цену перевозки единицы товара i-го предприятия j-му потребителю. Например, P23 – цена перевозки единицы продукции второго предприятия в третий населенный пункт. Через Xij (i=1,…, 4; j=1,…,6) обозначим объем продукции, поставляемой i-м предприятием j-му потребителю. Тогда стоимость перевозки Xij единиц продукции i-го предприятия j-му потребителю равна Pij*Xij. Стоимость перевозок всей продукции i-го предприятия потребителям равна Pi1*Xi1 + Pi2*Xi2 + … + Pi6*Xi6.
Полная стоимость перевозок всей продукции от поставщиков к потребителям является целевой функцией транспортной задача и подлежит минимизации:
Z = P11*X11 + P12*X12 + … + P16*X16 +
+ P21*X21 + P22*X22 + … + P26*X26 +
+ …+
+ P41*X41 + P42*X42 + … + P46*X46 min.
Ограничениями задачи являются балансовые равенства для всех для все поставщиков:
X11+X12+X13+X14+X15+X16=V1,
X21+X22+X23+X24+X25+X26=V2,
X31+X32+X33+X34+X35+X36=V3,
X41+X42+X43+X44+X45+X46=V4,
и всех потребителей:
X11+X21+X31+X41=W1,
X12+X22+X32+X42=W2,
X13+X23+X33+X43=W3,
X14+X24+X34+X44=W4,
X15+X25+X35+X45=W5,
X16+X26+X36+X46=W6.
Последним набором ограничений транспортной задачи являются условия неотрицательности переменных, то есть
Xij 0 для всех i=1,…, 4; j=1,…,6.
Заметим, что в более общей несбалансированной задаче в первой группе ограничений знаки равенства = должны быть заменены на знаки неравенства, которые означают что производитель не может поставить больше товара, чем произвел его. Соответственно во второй группе ограничений знаки равенства = должны быть заменены на знаки неравенства, которые означают что при корректной постановке задачи исключается недопоставка. При этом предполагается, что общая потребность в товарах не может быть больше, чем их запасы в пунктах отправления.
|
|
|
Решение задачи в Excel
Запустим программу, сохраним документ под названием, например, Задача4, дадим рабочему листу название, например, Транспорт.
Для решения введем данные в ячейки рабочего листа документе программы Excel (см. ниже). Если в наличии имеется готовая таблица, выполненная, например, в документе программы Word, то просто скопируем ее в буфер обмена, затем на рабочем листе документа программы выделим ячейку А1 и нажмем кнопку Вставить на панели инструментов. После этого необходимо, может быть скорректировать шрифт и размеры ячеек, подобно тому, как это сделано на рисунке ниже. Кроме того, на всякий случай выделить блоки ячеек со скопированными числовыми данными через меню Формат -Ячейки в открывшемся диалоговом окне Формат ячеек на вкладке Число в пометить в окошке Числовые форматы пункт Числовой и нажать на кнопку ОК. Это требуется для того, чтобы скопированную из документа программы Word, вообще говоря, текстовую информацию программа Excel воспринимала именно как числа.
В том случае, если требуется ввести исходные данные вручную, можно сделать это в следующем порядке. В ячейку А1 введем текст Стоимость перевозки единицы продукции. Хотя текст значительно превышает размеры ячейки на это не стоит обращать внимания, поскольку временное исчезновение части текста происходит лишь при выделении или редактировании перекрываемых этим текстом ячеек. Для того, чтобы рабочий лист имел приличный и удобный вид, иногда требуется корректировать его геометрию. Больше на этом останавливаться не будем. В ячейки А6, G1, G6, А8, G8, A13, G13, A17, G17 для наглядности вводим текст, например, как показано ниже. Текст не оказывает никакого влияния (если, конечно, ячейки с текстом не перемещать, удалять и т.п., что может повлиять на адреса, стоящие в формулах) на решение задачи, а служит лишь для удобства и лучшего понимания процесса решения и полученных результатов.
|
|
|
В ячейки А2:F5 вводим цены перевозок продукции от поставщиков к потребителям. Например, выделим ячейку А2, наберем с клавиатуры число и нажмем клавишу Enter. Никаких знаков равенства перед числом ставить не следует. Таким же образом введем и остальные данные исходной таблицы транспортной задачи, в том числе, объемы производства и общие объемы поставок потребителям.
Перейдем теперь ко вводу переменных и функций задачи. В блок ячеек А9:F12 введем массив переменных. Поскольку их очень много, не будем им давать им (то есть содержащим их ячейкам) специальных имен типа Х12, тем более, что в качестве имен нельзя употреблять наборы символов, совпадающие с адресами других ячеек (в рабочем листе имеется ячейка с адресом Х12). Оставим для этих переменных уже имеющиеся имена (или адреса) ячеек А9:F12. Выделим ячейку А9 и введем символы =0 (равно нулю), задавая этой переменной нулевое начальное значение. Во избежание дальнейших неприятностей обязательно нажмите клавишу Enter. То же самое проделаем с ячейками А10, А11, …, В9,…, В12, …,F 9,…, F12, то есть со всеми ячейками блока А9:F12.
Теперь для решения задачи и контроля результатов ячейки А15:F15 введем формулы подсчета суммарных поставок потребителям. Выделим ячейку А15 и вызовем Мастер функций, нажав на кнопку Вставка функций, находящуюся на панели инструментов и обозначенную значком fx. В появившемся диалоговом окне Мастера функций в окошке Категории щелкнем мышью на строке Математические, а затем в окошке Функция с помощью полосы прокрутки найдем и выделим щелчком функцию СУММ и нажмем кнопку ОК.
Появится новое диалоговое окно Мастера функций. В этом окне имеется два поля ввода аргументов функций, обозначенных Число 1 и Число 2. При необходимости появится третье, четвертое и т.д. Синтаксис функции СУММ допускает до 30 аргументов. В качестве аргумента можно использовать не одно число (ячейку), а целый блок, в частности программа уже предложила в качестве первого аргумента блок ячеек А9:А14, но слегка ошиблась. Мы ее подправим и вставим А9:А12. В этом случае в ячейке А15 будет находиться сумма чисел из ячеек А9:А12, то есть сумма поставок товара от всех производителей в первый населенный пункт. Теперь нажмем кнопку ОК.
|
|
|
Окно закрылось и в ячейке А15 появилось число 0, так как в ячейках блока ячеек А9:А12 в данный момент также стоят нули. В строке формул, находящейся сразу над рабочим листом справа появилась требуемая формула =СУММ(А9:А12) (если в данный момент выделена ячейка А15). Ту же процедуру ввода функций можно было бы повторить и для ячеек В15, С15, D15, E15, F15. Однако этого не требуется. Достаточно просто скопировать формулу из ячейки А15 в эти ячейки. Для этого щелкнем мышью на ячейке А15 и на панели инструментов нажмем кнопку Скопировать. Ячейка А15 станет выделенной «движущейся» рамкой. Щелкнем на ячейке В15 и нажмем на панели инструментов кнопку Вставить. Формула скопирована в ячейку В15, причем в формулу автоматически внесены необходимые исправления, то есть в ячейку В15 записана требуемая формула: =СУММ(В9:В12). Аналогичную операцию копирования проделаем для ячеек С15, D15, E15, F15. После ввода формул во всех перечисленных ячейках должны появиться нули.
Формулу в ячейку А15 можно было бы вписать, не используя мастер функций, просто вписав в нее набор символов =СУММ(А9:А12), начав его со знака равенства и набирая адрес блока ячеек А9:А12 латинскими(!!!) буквами. Мы воспользовались Мастером функций с учебными целями. Кроме того, пользователь не всегда помнит наизусть точное написание, синтаксис, количество, порядок следования и формат аргументов. Поэтому зачастую без Мастера функций невозможно обойтись.
Для себя и для возможных других пользователей внесем в ячейку А14 поясняющий текст СУММ(А9:А12) (без знака равенства!!!). Внесение аналогичных поясняющих надписей в ячейки В14 и т.д. нецелесообразно, так как может потребовать перекройки всего рабочего листа и будет загромождать его излишней информацией. Хотя это дело вкуса.
Для вычисления суммарных объемов производства (или суммарных поставок каждого поставщика) в ячейки G9:G12 впишем таким же образом аналогичные формулы. В ячейку G9 введем формулу =СУММ(А9:F9). Для разнообразия сделаем это с клавиатуры, вписывая указанный набор символов, причем символы СУММ наберем кириллицей, а (А9:F9) – латинскими буквами. Затем скопируем эту формулу в ячейки G10, G11, G12. Программа Excel внесет в копируемые формулы нужные коррективы.
|
|
|
В ячейке G15 вычислим суммарный объем поставок по всем потребителям с помощью формулы =СУММ(А15:F15). В ячейку G14 внесем поясняющий текст СУММ(А15:F15) без знака равенства.
Перейдем, наконец, к вычислению целевой функции задачи. Начнем с вычисления стоимости перевозок для каждого потребителя. В ячейку А19 поместим функцию, вычисляющую сумму произведений цен перевозки единицы товара от каждого поставщика на количество поставляемого товара. Такие вычисления выполняет функция СУММПРОИЗВ с подходящими аргументами. С помощью Мастера функций или с клавиатуры введем в А19 формулу =СУММПРОИЗВ(А2:А5,А9:А12). После этого скопируем обычным образом эту формулу в ячейки В19, …, F19. При правильном вводе формулы в ячейках должны появиться нули. Для пояснения в ячейку А18 впишем, опуская знак равенства, текст СУММПРОИЗВ(А2:А5,А9:А12).
В ячейке G19 вычислим значение целевой функции задачи. Эту роль может выполнить аналогичная формула =СУММПРОИЗВ(А2:F5,А9:F12), вычисляющая суммы произведений содержимого блоков ячеек А2:F5 и А9:F12. Однако, можно просто сложить стоимости перевозок по всем потребителям, то есть содержимое блока ячеек А19:F19. Остановимся на этом варианте и введем в ячейку G19 формулу =СУММ(А19:F19). В ячейку А18 впишем поясняющий текст СУММ(А19:F19).
|
|
|
