3.1 Постановка транспортной задачи
для «Поиска решения»
Так как транспортная задача представляет собой задачу линейного программирования, она может быть решена симплекс-методом, который, в частности, реализован в надстройке «Поиск решения» универсального пакета Excel [3, 15].
Поставим для «Поиска решения» открытую модель задачи о холодильных установках:
min (25x11 + 14x12 + 18x21 + 8x22 + 12x31 + 6x32)
x11 + x12 120
x21 + x22 40
x31 + x32 90
x11 + x21+ x31 150
x12 + x22 + x32 90
Подготовим данные в Excel следующим образом (слева и вверху указаны номера строк и столбцов электронной таблицы):
A | B | C | D | |
в Лейпциг, шт. | в Лион, шт. | |||
Количество установок, перевозимых из Стокгольма | 0,00 | 0,00 | ||
Количество установок, перевозимых из Триеста | 0,00 | 0,00 | ||
Количество установок, перевозимых из Руана | 0,00 | 0,00 | ||
Стокгольме | Триесте | Руане | ||
Ограничение по выпуску продукции в | 0,00 | 0,00 | 0,00 | |
Лейпциг | Лион | |||
Ограничение по потребности центра сбыта | 0,00 | 0,00 | ||
ф.ст. | ||||
Общая стоимость перевозки, |
Здесь в диапазон ячеек В1:С3 введены коэффициенты целевой функции (строки соответствуют центрам производства, а столбцы – центрам сбыта).
В диапазоне В5:С7 находятся переменные. Так как это изменяемые ячейки, в них можно ничего не вводить (по умолчанию они равны нулю) или ввести любые числа, например, нули. Не следует только вводить в них текстовую информацию или присваивать им формат, например, текста или даты, с которым программа не сможет производить вычисления. Введенный слева и сверху текст предназначен для удобства чтения отчетов о решении. Например, переменную, которая находятся в ячейке В5, «Поиск решения» назовет «Количество установок, перевозимых из Стокгольма в Лейпциг, шт.», составив это название из текста, ближайшего к этой ячейке слева и сверху. Так и должна называться переменная x11.
В В9:D9 находятся формулы для левых частей первых трех ограничений. Чтобы их ввести, рекомендуется в любую ячейку ввести формулу =СУММ(B5:C5) (т.е. x11 + x12), которую затем скопировать протаскиванием на 2 строки вниз (при протаскивании номера строк изменятся). Полученные три формулы перенести* в нужные ячейки.
В строке 10 введены объемы производства холодильных установок, а в строке 13 – объема сбыта.
В В12 находится левая часть четвертого ограничения - формула =СУММ(B5:B7), которая скопирована в С12 (при этом получают левую часть пятого ограничения).
Имена ограничений будут образованы так же, как и имена переменных. Например, первое ограничение (ячейка В9) получит имя: «Ограничение по выпуску продукции в Стокгольме».
Ячейка В15 – целевая, и получит имя «Общая стоимость перевозки, ф.ст.». В нее введена формула целевой функции: =СУММПРОИЗВ(B1:C3;B5:C7).
В «Поиск решения» вводится следующая модель (рисунок 3):
Рисунок 3 – Модель «Поиска решения»
В «Параметрах» «Поиска решения» необходимо поставить флажки «Линейная модель» и «Неотрицательные значения». Ограничения целочисленности вводить не нужно. В данном случае при решении задачи симплекс-методом также всегда будет получено целочисленное решение, так как коэффициенты в ограничениях – нули и единицы (при преобразовании системы методом Гаусса ограничения будут умножаться или делиться на 1, и свободный член никогда не станет дробным).
В результате выполнения поиска в изменяемых ячейках появятся значения, соответствующие оптимальным перевозкам, а в целевой ячейке – наименьшие затраты.
Кроме того, программа предоставляет пользователю возможность ознакомиться с тремя типами отчетов о решении задачи.