Методические указания к заданию 6

Транспортные задачи являются частным случаем задач линейного программирования и формулируются следующим образом.

Имеется m предприятий-производителей (заводов, фабрик) с запасом произведенных товаров (продуктов, материалов, изделий, топлива). Кроме того, имеется n предприятий-потребителей (магазинов, рынков, бензозаправочных станций), у которых есть спрос на эти товары. Требуется оптимальным образом доставить товар (запасы) от производителей к потребителям.

Обозначим предприятия-производители символом A_i, а предприятия-потребители символом Bj.

Наличие товаров (запасов) на предприятиях-производителях описывается вектором:

.

Потребность товаров (спрос) на j -том предприятии-потребителе описывается вектором:

.

 

Стоимость перевозок единицы продукции между i -тым предприятием-производителем и j -тым предприятием-потребителем описывается матрицей:

 

.

 

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

где x_ij – количество товара, перевозимого от i -го производителя к j -му потребителю.

Для получения матрицы оптимальных перевозок необходимо минимизировать целевую функцию:

 

Рассмотрим конкретную транспортную задачу. Пусть дана матрица стоимости перевозок (тарифы):

.

Форма предыдущей матрицы (m = 3 и n = 4) говорит о том, что в данной задаче имеется 3 производителя продукции (например, завода) и 4 потребителя продукции (например, магазина). Одна из возможных схем размещения заводов и магазинов показана на рисунке.

 

Матрица стоимости перевозок может быть использована для формирования целевой функции:

 

Z(x)=7х₁₁+8х₁₂+х₁₃+2х₁₄+4х₂₁+5х₂₂+9х₂₃+8х₂₄+9х₃₁+2х₃₂+3х₃₃+6х_34.

 

Очевидно, что эту функцию необходимо минимизировать.

Кроме того, известен вектор предложений (вектор запасов, вектор произведенной продукции):

Вектор потребностей (спроса) имеет вид:

 

Другими словами, имеются ограничения предложения (6.1) и спроса (6.2). Ограничения предложения записываются так:

х₁₁+х₁₂+х₁₃+х₁₄=160

х₂₁+х₂₂+х₂₃+х₂₄=140 (6.1)

х₃₁+х₃₂+х₃₃+х₃₄=170

 

Ограничения спроса имеют вид:

х₁₁+х₂₁+х₃₁=120

х₁₂+х₂₂+х₃₂=50 (6.2)

х₁₃+х₂₃+х₃₃=190

х₁₄+х₂₄+х₃₄=110

 

Рассмотренную задачу можно представить и другим способом (в виде таблицы):

Таблица 6.1.

Предприятия	B1	B2	B3	B4	Запасы
A1
A2
A3
Потребности					Сумма 470

 

Таблицу следует трактовать следующим образом.

Стоимость перевозок единицы продукции между заводом A₂ и магазином B₃ равна 9 денежным единицам. На заводе A₂ имеется 140 единиц готовой продукции. Потребность магазина B₃ составляет 190 единиц продукции.

Итак, в рассматриваемой транспортной задаче задана ЦФ и известны ограничения. Требуется найти минимум ЦФ:

Рассмотрим программу для нахождения ЦФ и матрицы оптимальных перевозок (математическая система Mathcad). Комментарии выделены полужирным шрифтом.

ORIGIN:=1