Постановка и основные свойства транспортной задачи

  • Просмотров 309
  • Скачиваний 11
  • Размер файла 206
    Кб

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

Л.В. Канторовичем и М.К. Гавуриным. Постановка Т-задачи. Пусть в пунктах А1,…, Am производят некоторый однородный продукт, причем объем производства в пункте Ai составляет ai единиц, i = 1,…, m. Допустим, что данный продукт потребляют в пунктах B1., Bn, a объем потребления в пункте Вj составляет bj одиниць j = 1., n. Предположим, что из каждого пункта производства возможно транспортировка продукта в любой пунктпотребления. Транспортные

издержки по перевозке единицы продукции из пункта Ai в пункт Вj равны cij (i = 1., m; j = 1., n). Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей Вj полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны. Условия Т-задачи удобно представить в виде табл. 1.1. Таблица. 1.1. Пункт потребления Пункт производства B1 B2 . Bn Bj ai A1 C11 C12 . C1n a1 A2 C21 C22 . C2n a2 Am

Cm1 Cm2 . Cmn am Ai bj b1 b2 . bn Объем производства Объем потребления Пусть  количество продукта, перевозимого из пункта Ai в пункт В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) называют планом перевозок, а переменные  – перевозками. План , при котором целевая функция минимальна, называется оптимальным, а матрица С=  – матрицей транспортных затрат. Графический способ задания Т-задач