pmii098

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

Замечание 2.18. Нельзя рассматривать как вершины клетки, где горизонтальные и вертикальные отрезки контура пересекаются.

В вершинах контура расставляются поочередно знаки «+»

и«-», начиная со знака «+» в выбранной свободной клетке. Величина перераспределяемой поставки определяется как

наименьшая из величин поставок в вершинах контура со знаком «-». На эту величину увеличиваются поставки в вершинах со знаком «+» и уменьшаются поставки в вершинах со знаком «-». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится. После чего переходят ко второму этапу.

Замечание 2.19. Если величина перераспределяемой поставки равна поставкам не в одной, а в нескольких вершинах контура со знаком «-», то освобождается только одна клетка, обычно с наибольшей стоимостью перевозки, а все другие такие клетки остаются занятыми с нулевой поставкой.

Пример 2.10. Рассмотрим работу алгоритма на данных, приведенных в примере 2.8. Начальный план перевозок этой задачи получен методом северо-западного угла (табл. 2.12). Применяя далее алгоритм решения задачи, найдем потенциалы поставщиков и потребителей. Полагая и, пользуясь соотношением (2.13), определяем потенциалы:

{

Результаты расчета потенциалов представлены в таблице

2.13.

81

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

Чтобы улучшить неоптимальный план перевозок, выберем клетку таблицы поставок с наибольшей по абсолютной величине отрицательной оценкой (это клетка (3, 2)).

Строим замкнутый контур (табл. 2.14) и находим величину перераспределяемой поставки. Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со знаком «-»:

( )

82

84

[ ],

то найденный план перевозок является оптимальным. Суммарные минимальные затраты на перевозку апельсин:

Эти минимальные затраты достигаются при следующих объемах перевозок:

Остальные неизвестные равны нулю.

2.4.3. Транспортная задача с нарушенным балансом

Если баланс (2.12) не выполняется, то ограничения (2.9) или (2.10) имеют вид неравенств типа «меньше или равно». Транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом потенциалов ее сводят к закрытой задаче.

85

Случай 1. Если суммарная мощность потребителей больше суммарной мощности поставщиков

∑∑

то в рассмотрение вводится «фиктивный поставщик» ((m+1)-й) с потребностью

∑∑

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

Случай 2. Если суммарная мощность поставщиков больше суммарной мощности потребителей

∑∑

то в рассмотрение вводится «фиктивный потребитель» ((n+1)-й) с потребностью

∑∑

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

Пример 2.11. Три плодовых хозяйства поставляют апельсины в ящиках четырем оптовым покупателям. Ежедневная потребность этих покупателей составляет 45, 35, 55 и 65 ящиков

86

соответственно. Плодовые хозяйства могут ежедневно поставлять 40, 60 и 90 ящиков апельсинов соответственно. Транспортные расходы на один ящик апельсинов приведены в таблице.

Требуется найти оптимальный план поставок.

Построение модели

1) Обозначим количество ящиков, перевозимых из i-го хозяйства в j-й пункт потребления через .

2) Проверим равенство суммарного производства апельсинов и суммарного спроса

(45+35+55+65) > (40+60+90),

откуда следует вывод – задача открытого типа, поскольку спрос на апельсины превышает объем их производства.

3) Суммарные затраты в рублях на ежедневную перевозку апельсинов определяются по формуле

.

4) Запишем ограничения задачи. Баланс по строкам и по столбцам имеет вид:

{

87

{

( )

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

Для решения открытой транспортной задачи сведем ее к закрытой. Поскольку суммарный спрос потребителей больше, чем суммарная мощность поставщиков введем «фиктивного» поставщика и в таблицу поставок добавим дополнительную строку так, чтобы задача стала закрытой. Для этого мощность «фиктивного» поставщика следует принять равной 10 = 200 - 190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Так как информация об этих издержках отсутствует, примем их равными нулю (табл. 2.18).

Таблица 2.18 Таблица поставок с введенным «фиктивным» поставщиком

После введения «фиктивного» поставщика задача решается как закрытая (см. пример 2.10).

88

2.4.4. Решение транспортной задачи средствами табличного процессора Excel

Транспортная задача вводится и решается в Excel аналогично задаче линейного программирования. Специфика ввода условия транспортной задачи состоит лишь в удобстве матричного задания переменных задачи и коэффициентов целевой функции.

Решение транспортной задачи в Excel состоит из следующих шагов:

1.создание формы для ввода условий задачи;

2.ввод исходных данных;

3.определение целевой функции;

4.ввод ограничений;

5.проведение расчетов.

Применение информационных технологий Excel для решения транспортной задачи рассмотрим на примере 2.8.

Экранная форма для ввода условий задачи вместе с введенными в нее исходными данными представлена на рис. 2.19.

Рис. 2.19. Экранная форма задачи

89

В массив B3:E5 введены значения стоимости перевозок единицы груза. В ячейки B14:E14 введены величины спроса потребителей, в H9:H11 – запасов поставщиков. Массив B9:E11 отведен под значения неизвестных (объемы перевозок).

В затененные области введем формулы для целевой функции и линейных ограничений (рис. 2.20). В ячейку G3 запишем целевую функцию, используя функцию СУММПРОИЗВ (B3:E5; B9:E11). В диапазоне H9:H11 запишем ограничения по поставщикам, а в ячейках B14:E14 ограничения по потребителям. Для наглядности покажем знаки соотношений в ограничениях, ячейки G9:G11 и В13:Е13. Так как модель закрытая, то все знаки в форме равенств. Подготовленная таким образом информация в режиме чисел представлена на рис. 2.21.

Рис. 2.20. Экранная форма задачи в режиме формул

90