Контрольная работа: Постановка и основные свойства транспортной задачи

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О.Н. Толстым [18; 59].

Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л.В. Канторовичем и М.К. Гавуриным.

Постановка Т-задачи. Пусть в пунктах А₁ ,…,A_m производят некоторый однородный продукт, причем объем производства в пункте A_i составляет a_i единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B₁ ., B_n , a объем потребления в пункте В_j составляет b_j одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные издержки по перевозке единицы продукции из пункта A_i в пункт В_j равны c_ij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей В_j полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.

Условия Т-задачи удобно представить в виде табл. 1.1.

Таблица. 1.1.

Пусть количество продукта, перевозимого из пункта A_i в пункт В_j .

Требуется определить множество переменных , i = 1., m, j = 1., n, удовлетворяющих условиям

(1.1)

Очень интересно - Контрольная работа: Применение методов линейного программирования для оптимизации стоимости перевозок

(1.2)

и таких, что целевая функция

(1.3)

достигает минимального значения.

Условие (1.1) гарантирует полный вывоз продукта из всех пунктов производства, а (1.2) означает полное удовлетворение спроса во всех пунктах потребления.

Вам будет интересно - Дипломная работа: Прогнозування стану житлового фонду міста (на прикладі м. Тернопіль)

Таким образом, Т-задача представляет собой задачу ЛП с числом переменных, и (m + n) числом ограничений равенств.

Переменные удобно задавать в виде матрицы

(1.4)

Матрицу X , удовлетворяющую условиям Т-задачи (1.1) и (1.2) называют планом перевозок, а переменные – перевозками. План , при котором целевая функция минимальна, называется оптимальным, а матрица С = – матрицей транспортных затрат.

Графический способ задания Т-задач показан на рис. 1

Похожий материал - Контрольная работа: Программа имитационного моделирования работы банка

Рис. 1

Отрезок A _i B _j называют коммуникацией. На всех коммуникациях ставят величины перевозок x_ij .

Вектор P _ij , компоненты которого состоят из коэффициентов при переменных x_ij в ограничениях (3.1.1) и (3.1.2), называют вектором коммуникаций: