Главная | Обратная связь | Поможем написать вашу работу!

Транспортная задача линейного программирования; её применение на АТ.

Сокращение дальности перевозок является важнейшим путём уменьшения расходов на доставку груза потребителям. При сложившемся размещении производства этого достигают установлением более правильных схем перевозок в форме закрепления потребителей за поставщиками однородного или взаимозаменяемого груза. В литературе этот процесс называется транспортной задачей линейного программирования. В пределах города (района) имеется, как правило, несколько поставщиков одного и того же продукта, значит принципиально возможно большое количество вариантов закрепления потребителей за поставщиками. Составление наилучшей схемы перевозок в этом случае является непростым делом: из-за большого количества возможных вариантов найти оптимальное решение путём простого перебора их и сравнение практически не возможно – внедрение математических методов позволяет составить оптимальные схемы перевозок.

Рассмотрим и сформулируем в математической форме условие транспортной задачи:

Потребителям Б₁, Б₂, … Б_j, … Б_n требуется груз количеством b₁, b₂, … b_j … b_n [т], который находится у поставщиков A₁, A₂, … A_i, … A_m количеством a₁, a₂, … a_i, … a_m [т]. Так как все поставщики производят один и тот же продукт, то каждый из них может удовлетворить запросы любого потребителя. Расстояния между пунктами потребления и назначения известны и составляют l_ij км.

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

Для решения задачи необходимо равенство общей потребности получателей наличию грузов у изготовителя. Обозначим через Х_ij – количество тонн груза, предназначенного к отправке из пункта А_i в пункт Б_j, тогда количеству груза, планируемого к перевозке из всех пунктов отправления А_i в один пункт назначения Б_j составит

x₁_j + x₂_j + x₃_j + … + x_nj =

так как потребность конкретного пункта назначения – b_j, то тогда должно соблюдаться равенство:

= b_j;

так как сказанное справедливо для любого пункта назначения, то образуется система уравнений с «n»-количеством уравнений:

(1)

более коротко эту систему можно записать:

(2)

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

так как запасы конкретного пункта отправления – a_i, отсюда:

всё это справедливо для любого пункта отправления, т.е.

(3)

или

(4)

при рассмотрении условий задачи следует, сто суммарная транспортная работа будет:

Р = l₁₁*x₁₁ + l₁₂*x₁₂ + … + l_ij*x_ij + … + l_mn*x_mn;

или

[т*км] (5)

Любая перевозка НЕ МОЖЕТ быть выражена отрицательным числом - .

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

, (6)

, (7)

(8)

Уравнение (6) обеспечивает грузом всех потребителей, уравнение (7) гарантирует полный вывоз груза из всех пунктов отправления, уравнение (8) гарантирует неотрицательность перевозок.

Для совместности уравнений (6) и (7) требуется, чтобы сумма потребностей всех получателей равнялась сумме запасов грузов во всех пунктах отправления:

(9)

Уравнение (9) не только необходимо, но и достаточно для совместности уравнений (6) и (7). Поскольку уравнения (6), (7) и (8) содержат неизвестные (i и j) только в 1-ой степени, а показатель l_ij в уравнении (5) не зависит от переменной, сформулированные задачи (5), (6), (7) и (8) являются транспортной задачей линейного программирования.

Уравнения и неравенства (6), (7) и (8), с помощью которых записаны условия задачи, иногда называют ограничениями задачи.

План перевозок грузов, отвечающий требованиям (6), (7) и (8) называют допустимым исходным планом.

Допустимый план, обеспечивающий минимум транспортной работы называют оптимальным планом.

Уравнение (5), выражающее цель решения называется целевой функцией или критерием оптимальности.

Запись задачи, отвечающая условию (9) называется закрытой моделью.

Разработано несколько методов решения транспортной задачи линейного программирования. Наиболее распространён – метод потенциалов.

Общая схема метода потенциалов.

В начале составляется допустимый исходный план задачи, который исследуется на потенциальность. Если при проверке оказывается, что составленный план оптимален, то решение закончено, иначе – при помощи специального приёма осуществляется переход к новому (лучшему) плану, этот план также исследуется на оптимальность и, если надо, вновь оптимизируется до тех пор, пока не будет найдено решение. Сущность этого метода содержит 3 важных момента:

1. указывается способ составления исходного допустимого плана:

2. Устанавливается признак, позволяющий отличить оптимальный план от неоптимального;

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

Метод потенциалов реализуется с помощью строго регламентированного метода вычисления. При этом все вычисления производятся в таблице (матрице), предварительно составленной по условиям задач.

⇐ Предыдущая 35 36 37 38 39 40 414243 44 Следующая ⇒