Физический смысл целевой функции транспортной задачи по критерию стоимости

1. Физический смысл целевой функции транспортной задачи по критерию стоимости

В Ы П ОЛ Н И Л А
С Т УД Е Н Т К А Г Р У П П Ы С - 1 8 4 1
Ж А В Р И Д Е К АТ Е Р И Н А

2. Транспортная задача - это

математическая задача по нахождению оптимального распределения
поставок однородного «товара» (груза, вещества) между пунктами
отправления и назначения при заданных, численно выраженных
затратах (стоимостях, расходах) на перевозку.
Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781 году.
Прогресс в решении проблемы был достигнут во время Великой Отечественной войны советским
математиком и экономистом Леонидом Канторовичем. Поэтому иногда эта проблема называется
транспортной задачей Монжа — Канторовича.

3.

Различают два типа транспортных задач:
• по критерию стоимости (план перевозок оптимален, если достигнут минимум
затрат на его реализацию);
• по критерию времени (план оптимален, если на его реализацию затрачивается
минимум времени).

4.

Однородный груз сосредоточен у m
поставщиков в объемах
.
Данный груз необходимо доставить n
потребителям в объемах
.
Известны
(
)–
стоимости перевозки единицы груза от
каждого i-го поставщика каждому j-му
потребителю.
Требуется составить такой план
перевозок, при котором запасы всех
поставщиков вывозятся полностью,
запросы всех потребителей
удовлетворяются полностью и
суммарные затраты на перевозку всех
грузов минимальны.
b1
b2
….
bn
a1
С11
С12
….
С1n
a2
С21
С22
….
C2n
….
….
….
….
….
am
Сm1
Сm2
….
Cmn

5.

Переменными (неизвестными) транспортной задачи являются
(
перевозок от каждого i-го поставщика каждому j-му потребителю.
Эти переменные могут быть записаны в виде матрицы перевозок
) – объемы
Математическая модель транспортной задачи в общем случае имеет вид:
Целевая функция задачи выражает требование обеспечить минимум суммарных затрат на
перевозку всех грузов.
- Равенство описывает тот факт, что
запасы всех m поставщиков вывозятся
полностью.
- Выражает требование полностью
удовлетворить запросы всех n
потребителей.

6.

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

7.

ai \bj
50
70
80
90
9
5
3
Решение:
1) Введем переменные задачи (матрицу
перевозок):
2) Запишем матрицу стоимостей:
110
4
6
8
3) Целевая функция задачи:
4) Составим систему ограничений.
Сумма перевозок, стоящих в первой строке матрицы Х, должна
равняться запасам первого поставщика, а сумма перевозок во Данная функция, определяющая суммарные
второй строке матрицы Х – запасам второго поставщика:
затраты на все перевозки, должна достигать
минимального значения.
Это означает, что запасы всех поставщиков вывозятся
полностью

8.

Суммы перевозок, стоящих в каждом столбце матрицы Х, должны быть равны запросам
соответствующих потребителей:
Это означает, что запросы потребителей удовлетворяются полностью.
Ответ:
Целевая функция задачи –
Ограничения: