Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Простейшими транспортными задачами являются задачи о перевозках некоторого однородного груза из пунктов отправления (от поставщиков) в пункты назначения (к потребителям) при обеспечении минимальных затрат на перевозки.
Обычно начальные условия таких задач записывают в таблицу. Например, для k поставщиков и l потребителей такая задача имеет следующий вид:
Здесь показатели a ij означают затраты на перевозку единицы груза от i -го поставщика (i =1,2,…, k) к j -тому потребителю (j =1,2,…, l), Mi - мощность i -того поставщика в планируемый период, Nj - спрос j -того потребителя на этот же период. Обозначим через xij поставку (количество груза), которая планируется к перевозке от i -того поставщика к j -тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции
при ограничениях
(1) |
Если к этим ограничениям добавить еще одно:
(2) |
т.е. суммарная мощность поставщиков равна суммарному спросу потребителей, то соответствующая модель задачи называется закрытой.
Задачам, в которых ограничение (2) отсутствует, т.е.
,
первоначально соответствует открытая модель.
Отметим некоторые особенности экономико-математической модели транспортной задачи.
Система ограничений (1) сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные.
Матрица коэффициентов при переменных в системе (1) состоит только из единиц и нулей.
Система ограничений (1) включает k уравнений, связывающих поставки i-того поставщика с мощностью Mi (i =1,2,…, k) этого поставщика, и l уравнений, связывающих поставки j -тому потребителю со спросом Nj (j =1,2,…, l) этого потребителя. Заметим, что число k равно числу строк исходной таблицы, а число l - числу столбцов.
Число переменных x ij, входящих в целевую функцию и в систему уравнений (1), равно произведению kl, т.е. числу клеток таблицы.
Таким образом, система ограничений (1) есть система из k +l уравнений с kl переменными.
Любое решение транспортной задачи (x1 1, x 12,…, xkl) называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях.
Оптимальному решению транспортной задачи соответствует оптимальное распределение поставок, при котором целевая функция достигает своего минимума.
В ходе решения задачи и нужно получить это оптимальное распределение поставок, которому соответствует какое-то допустимое базисное решение системы ограничений (1).
Дата публикования: 2015-03-26; Прочитано: 289 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!