Практическое занятие № 6

Наименование занятия: Решение транспортных задач

Цель занятия: Научиться решать транспортные задачи

Подготовка к занятию: Повторить теоретический материал по теме «Линейное программирование».

Литература:

1. Лобачева М.Е. Конспект лекций «Математические методы», 2013г.

2. Агальцов В.П. Математические методы в программировании, 2010г.

Перечень необходимых приборов, инструментов, материалов:ПЭВМ

Задание на занятие:

С помощью математической системы Mathcad решить транспортную задачу. Исходные данные приведены в таблице.

Вариант	Матрица стоимости перевозок	Матрица предложения	Матрица спроса
1
2
3
4
5
6
7
8
9
10

Порядок проведения занятия:

1. Получить допуск к работе.

2. Выполнить задание в соответствии со своим вариантом.

3. Ответить на контрольные вопросы.

Содержание отчета:

1. Наименование, цель работы, задание;

2. Выполненное задание;

3. Выводы по результатам выполненного задания;

4. Ответы на контрольные вопросы.

Контрольные вопросы для зачета:

1. К какому классу задач относится транспортная задача?

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

3. Приведите общую формулировку транспортной задачи.

4. Укажите общий алгоритм решения транспортных задач.

ПРИЛОЖЕНИЕ

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

Имеется 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.

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

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

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

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

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

х₂₁+х₂₂+х₂₃+х₂₄=140

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

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

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

х₁₂+х₂₂+х₃₂=50

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

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

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

Предприятия	B1	B2	B3	B4	Запасы
A1	7	8	1	2	160
A2	4	5	9	8	140
A3	9	2	3	6	170
Потребности	120	50	190	110	Сумма 470

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

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

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

Рассмотрим программу для нахождения ЦФ и матрицы оптимальных перевозок с помощью математической системы Mathcad.

ORIGIN:=1

Указываем число предприятий-производителей (заводов) и предприятий - потребителей (магазинов)

m:=3n:=4

Организуем циклы

j:=1..ni:=1..m

t_j:= 1s_i:= 1

Вводим матрицу стоимости перевозок, вектор запасов, вектор спроса

Вводим целевую функцию

x_m,n:=0

Given

x ≥ 0

x:=Minimize(Z,x)

Получим матрицу оптимальных перевозок

Определена стоимость оптимальных перевозок

Z(x) =1330