Контрольная работа: Транспортная задача с ограничениями возможных транспортных средств

Математическая модель транспортной задачи в общем случае имеет вид

(1.1)

i=1,2,…,m, (1.2)

j=1,2,…,n, (1.3)

i=1,2,…,m; j=1,2,…,n. (1.4)

Целевая функция задачи (1.1) выражает требования обеспечить минимум суммарных затрат на перевозку всех грузов. Первая группа из т уравнений (1.2) описывает тот факт, что запасы всех т поставщиков вывозятся полностью. Вторая группа из n уравнений (1.3) выражает требования полностью удовлетворить запросы всех n потребителей. Неравенства (1.4) являются условиями неотрицательности всех переменных задачи.

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

i=1,2,…,m; j=1,2,…,n, (1.5)

удовлетворяющее системе ограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающее минимум целевой функции (1.1).

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

. (1.6)

1.5 Транспортная задача с ограниченными возможностями транспортных средств

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

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

В целом ряде случаев оптимизации планирования перевозок приходится учитывать ограниченные возможности транспортных путей и средств. Поэтому математическую модель транспортной задачи:

(1.7)

i=1,2,…,m, (1.8)

j=1,2,…,n, (1.9)

(1.10)

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

Если обозначиться транспортные возможности между пунктами I и j через dij, то количество груза , которое может быть перевезено по этому направлению за планируемый период времени, не должно превышать транспортных возможностей, т.е.

(1.11)

Тогда ограничения 1.10, 1.11 объединяются, и модель задачи усложняется двусторонними ограничениями на переменные

(1.12)

При этом общая транспортная возможность дорог, соединяющих I -й пункт производства со всеми n пунктами потребления, должна быть ровна или больше количества продукции, предназначенной к постановке из этого i-го пункта всем n потребителя, т.е.

i=1,2,…,m, (1.13)

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

i=1,2,…,n, (1.14)

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

Путей некоторых преобразований условий ее можно свести к типу обычной транспортной задачи. Для этого пункт производства или потребления, для которых условия ограничены транспортные возможности, разбивается на два условных пункта. При этом следует подчеркнуть непременно один пункт.