Методы принятия упр. ...

5.1 Экономико-математическая модель транспортной задачи

Транспортная задача является частным случаем задачи линейного программирования. Формулируется следующим образом: заданы поставщики А_i и размеры их запасов, потребители В_j и размеры их заявок; известна стоимость перевозки единицы груза от каждого поставщика до каждого потребителя; требуется найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:

1. Мощности всех поставщиков были реализованы;

2. Спросы всех потребителей были удовлетворены;

3. Суммарные затраты на перевозку всех грузов были бы минимальны.

Математическая модель оптимизации плана распределения однородных грузов (ресурсов) называется распределительной или транспортной задачей.

Для построения математической модели транспортной задачи примем следующие обозначения:

m – количество поставщиков

i – номер поставщика

n- количество потребителей

j – номер потребителя

а_i – объем продукции у i-го поставщика

b_j – объем продукции необходимый j-му потребителю

С_ij – стоимость перевозки единицы продукции от i-го поставщика j-му потребителю.

х_ij – количество грузов перевозимых из i-го пункта отправления в –j-й пункт назначения.

При принятых обозначениях условие задачи можно записать в виде таблицы, которую в дальнейшем будем называть матрицей планирования:

Математическая формализация задачи

1) Ограничения по вывозке грузов из пунктов отправления:

х₁₁+х₁₂+…+х_1n =a₁

x₂₁+x₂₂+…+x_2n=a₂

… … … …

x_m1+x_m2+…+ x_mn=a_m

2) Ограничения по отправке грузов в пункты назначения

х₁₁+х₂₁+…+x_m1 =b₁

x₁₂+x₂₂+…+x_m2=b₂

… … … …

x_1n+x_2n+…+x_mn=b_n

3) Ограничения по неотрицательности переменных

х_ij >= 0

Критерий оптимизации - минимум транспортных затрат.

С = С₁₁х₁₁ + … +С_ijx_ij + …+…C_mnx_mn  min

Структурная модель задачи имеет следующий вид:

Равенство запасов потребностям есть необходимое и достаточное условие совместимости и, следовательно, разрешимости задачи.

При выполнении условий:

- модель называют закрытого типа.

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

Наиболее очевидными являются следующие отличительные особенности распределительных задач.

1. Условия задачи описываются только уравнениями (в симплексном методе ограничения задачи описывались неравенствами).

2. Все переменные выражаются в одних и тех же единицах измерения.

3. Во всех уравнениях коэффициенты при переменных равны единице.

4. Каждая переменная встречается только в двух уравнениях системы ограничений.

Указанные свойства распределительных задач позволили разработать специальные методы их решения. Это задача линейного программирования, но в силу некоторых свойств ее можно решать не симплексным методом, а более легким способом.