Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В общем виде задачу можно представить следующим образом: в т пунктах производства А1, А2, …, Ат имеется однородный груз в количестве соответственно а1, а2, …, ат. Этот груз необходимо доставить в п пунктов назначения В1, В2, …, Вп в количестве соответственно b1, b2, …, bn. Стоимость перевозки единицы груза (тариф) из пункта Аi в пункт Вj равна сij.
Требуется составить план перевозок, позволяющий вывезти все грузы и имеющий минимальную стоимость.
Определение 1. Если , то задача называется закрытой. Если , то открытой.
Обозначим через хij количество груза, перевозимого из пункта Аi в пункт Вj. Рассмотрим закрытую транспортную задачу. Её условия запишем в распределительную таблицу, которую будем использовать для нахождения решения.
Таблица 5.1
Bj Ai | B1 | B2 | … | Bj | … | Bn |
b1 | b2 | … | bj | … | bn | |
A1 a1 | c11 x11 | c12 x12 | … | c1j x1j | … | c1n x1n |
A2 a2 | c21 x21 | c22 x22 | … | c2j x2j | … | c2n x2n |
… | … | … | … | … | … | … |
Ai ai | ci1 xi1 | ci2 xi2 | … | cij xij | … | cin xin |
… | … | … | … | … | … | … |
Am am | cm1 xm1 | cm2 xm2 | … | cmj xmj | … | cmn xmn |
Математическая модель закрытой транспортной задачи имеет вид
при ограничениях:
Оптимальным решением задачи является матрица
,
которая удовлетворяет системе ограничений и доставляет минимум целевой функции. Для решения транспортной задачи разработан специальный метод, имеющий те же этапы, что и симплексный метод, а именно:
- нахождение исходного опорного решения;
- проверка этого решения на оптимальность;
- переход от одного опорного решения к другому.
Дата публикования: 2015-03-26; Прочитано: 279 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!