Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз
потребителям
.
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
|



;
|


,
|
Возможно вы искали - Дипломная работа: Прогнозування стану житлового фонду міста (на прикладі м. Тернопіль)
|
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены
.
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
Похожий материал - Контрольная работа: Программа имитационного моделирования работы банка
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок (Таблица 3. ):
Таблица 3. - План перевозок с указанием запасов и потребностей
Пункты Отправления | Пункты назначения | Запасы | |||
![]() | ![]() | … | ![]() | ||
![]() | ![]() | ![]() | … | ![]() | ![]() |
![]() | ![]() | ![]() | … | ![]() | ![]() |
… | … | … | … | … | … |
![]() | ![]() | ![]() | … | ![]() | ![]() |
Потребности | ![]() | ![]() | … | ![]() |
Очень интересно - Курсовая работа: Программирование на сетях или
|
Условие или
означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное
означает количество груза, перевозимого с базы
потребителю
: совокупность этих величин образует матрицу (матрицу перевозок).
Очевидно, переменные должны удовлетворять условиям:
|

Вам будет интересно - Дипломная работа: Проект оптимизации сводных показателей машиностроительного цеха
Система (3. ) содержит уравнений с
неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (3. ) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (3. ) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.
Такая структура системы (3. ) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием ,
.Перепишем систему (3. ) в виде
|

где символы и
означают суммирование по соответствующему индексу. Так, например,
Похожий материал - Курсовая работа: Проектирование модели для составления оптимального рациона кормления скота
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь ,
).
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные с помощью вертикальных уравнений, мы получаем уравнение