Методика и порядок выполнения работы 4

Построение и анализ моделей задач транспортного типа

Цель и содержание: Научиться строить и анализировать модели транспортной задачи, находить первоначальный опорный план различными методами и оптимальное решение с использованием инструментального средства «Поиск решения».

Теоретическое обоснование

Изучите теоретический материал по данной теме, используя материал изложенный ниже.

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

Сформулируем математическую модель транспортной задачи.

Некоторый однородный продукт, сосредоточенный у т поставщиков А в количестве а_i (i = 1, 2, ..., т) единиц соответственно, необходимо доставить п потребителям В в количестве b_j (j = 1, 2, ..., n) единиц. Известна стоимость C_ij перевозки единицы груза от i-го поставщика к j-у потребителю. Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить потребности и имеющий минимальную стоимость.

Обозначим через x_ij количество единиц груза, запланированных к перевозке от i-го поставщика к j-у потребителю; тогда условие задачи можно записать в виде таблицы 4.1, которую в дальнейшем называют матрицей планирования.

Таблица 4.1 – Матрица планирования

Составим математическую модель задачи. Так как от i-го поставщика к j-у потребителю запланировано к перевозке x_ij единиц груза, то стоимость перевозки составит c_ijx_ij. Стоимость всего плана выразится двойной суммой:

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

а) все грузы должны быть вывезены, то есть,

, (i = 1, 2, ..., m),

эти уравнения получаются из строк таблицы 4.1;

б) все потребности должны быть удовлетворены, то есть,

, (j = 1, 2, ..., n),

уравнения получаются из столбцов таблицы 4.1.

Таким образом, математическая модель транспортной задачи имеет следующий вид. Найти наименьшее значение функции:

(4.1)

при ограничениях:

(4.2)

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, то есть

.

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

Рассмотрим пример построения математической модели транспортной задачи и методы построения опорного плана.

Пример. Четыре предприятия могут производить некоторую однородную продукцию в количестве соответственно 100, 250, 200 и 300. На эту продукцию есть заказ от пяти потребителей соответственно в количестве 200, 200, 100, 100 и 250. Затраты с производством и доставкой единицы продукции задаются матрицей:

.

Составьте математическую модель задачи и найдите опорный план перевозок методом северо-западного угла, при котором общая стоимость перевозок является минимальной.