Решение транспортной задачи_11 класс

Информатика и ИКТ 11 класс

§ 3.4.2

Задача составления плана перевозок от поставщиков к потребителям с помощью некоторых транспортных средств.
Составленный план должен обеспечивать выполнение таких условий, как:
• полное удовлетворение спроса потребителей;
• вывоз всей продукции от поставщика;
• минимизация транспортных затрат.

Известно, что на складах имеется запас муки в количестве 45, 100, 20, 75 мешков.
А магазины имеют потребность в этом товаре в количестве 30, 80, 95, 35 мешков.

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

В m пунктах отправления (складах) А1, А2, ..., Аm находится однородный груз в количестве а1, а2, ..., ат единиц соответственно.
Потребность в этом грузе в n пунктах назначения (магазинах) В1, В2, ..., Вп составляет bl b2, ..., bп соответственно.
Будем считать, что сумма запасов на складах равна суммарным потребностям в магазинах, т.е.

Такая модель называется замкнутой.

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

Суммарные затраты являются целевой функцией.

Табличная модель

Ячейки, выделенные фоном, содержат удельные стоимости перевозок Cij;.

Запас муки

Потребность в магазине

Математический анализ

Проверим замкнутость модели

Для этого просуммируем все запасы муки на складах: 45 + 100 + 20 + 75 = 240.
Найдем суммарные потребности магазинов в муке: 30 + 80 + 95 + 35 = 240.

Ограничения

Математический анализ

Весь груз со складов должен быть вывезен.

удовлетворению спроса магазинов отвечает выполнение системы уравнений:

удовлетворению спроса магазинов отвечает выполнение системы уравнений:

удовлетворяет спроса магазинов

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

Z = С11  Х11 +... +С14  Х14 +С21  Х21 +... +С24  Х24 +С31  Х31 + ... + С34  Х34 + С41  Х41 +... + C44  Х44.

удовлетворению спроса магазинов отвечает выполнение системы уравнений:

удовлетворению спроса магазинов отвечает выполнение системы уравнений:

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

Первое ограничение – по уровню потребления:
второе – по уровню запасов