ЗАДАЧА 2. Пиловочное сырье, сосредоточенное на четырех леспромхозах, необходимо доставить на пять лесозаводов

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

Теория

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

Заданы следующие условия:

Таблица 2.1.

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

Математическая модель задачи строится следующим образом. Обозначим через x_ij объем перевозок от i-го поставщика к j-му потребителю. Функция цели (суммарные транспортные расходы), которую надо минимизировать, задается соотношением:

где c_ij – стоимость перевозки единицы продукции от i-го поставщика к j-му потребителю, m – число поставщиков, n – число потребителей.

Неизвестные x_ij в задаче должны удовлетворять следующим ограничениям:

l Объемы перевозок не могут быть отрицательными.

l Так модель сбалансирована, то вся продукция должна быть вывезена из леспромхозов, а потребности всех потребителей должны быть полностью удовлетворены.

На языке математики это выглядит так:

где a_i – запас сырья у i-го леспромхоза, b_j – потребности j-го лесозавода.

Выполнение работы

Решим эту задачу на компьютере, воспользовавшись средством поиска решений Excel. Исходная таблица изображена на рис. 2.1.

В ячейки A1: E4 введены стоимости перевозок. Неизвестные будут вычисляться в ячейках A6: E9. Запасы сырья в леспромхозах введены в ячейки G6: G9, потребности лесозаводов – в ячейки A11: E11.

В ячейку F10 введена целевая функция =СУММПРОИЗВ(A1: E4; A6: E9).

В ячейки F6: F9 введены формулы сумм по строкам:

=СУММ(A6: E6)

=СУММ(A7: E7)

=СУММ(A8: E8)

=СУММ(A9: E9),

в ячейки A10: E10 введены формулы сумм по столбцам

=СУММ(A6: A9)

=СУММ(B6: B9)

=СУММ(C6: C9)

=СУММ(D6: D9)

=СУММ(E6: E9).

Исходные данные введены, можно приступать к поиску решения. Выберем команду меню Сервис, Поиск решения. Откроется окно, в которое мы занесем условия задачи (рис. 2.2).

Нажмем кнопку Выполнить. Решение будет найдено (рис. 2.3)

Рис. 2.3

Варианты контрольных заданий

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.