14) Экономико – математическая модель транспортной задачи.
В различных местах оправки имеется однородный груз, который требуется доставить в несколько пунктов назначения. Известно, сколько груза отправляется из каждого пункта и сколько груза должно поступить в пункт назначения. Причём безразлично, какой именно отправитель будет доставлять груз тому или иному получателю. Требуется так организовать перевозки, чтобы обеспечить минимальный общий пробег груза, т. е. минимизировать затраты на транспортировку. Экономико-математическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.
Таблица 2.1
Экономико-математическая модель транспортной задачи
Примечание. Аi – название пункта отправления; Вj – название пункта назначения; ai – производственная мощность поставщиков; bj – спрос потребителей; m – число поставщиков; n – число потребителей; i – номер строки (i-й поставщик) i = 1…m; j – номер столбца (j-й потребитель) j = 1…n; cij – показатель критерия оптимальности, удельные затраты на транспортировку единицы продукции (себестоимость перевозок) от поставщика i до потребителя j; xij – количество продукции, перевозимое от поставщика i до потребителя j, план перевозок, распределение поставок, корреспонденция грузов.
Условия задачи в принятых обозначениях следующие.
Каждый поставщик должен дать ровно столько продукции, столько у него есть, т. е. сумма поставок по каждой строке должна будет равна мощности ai этой строки:
(2.1)
2. Каждый потребитель должен получить ровно столько продукции, сколько ему требуется, т. е. сумма поставок по каждому столбцу должна будет равна спросу bi этого столбца:
(2.2)
3. Из вышеприведённых условий (2.1) и (2.2) следует:
(2.3)
В случае если
,
то транспортная задача линейного
программирования называется открытой.
Если
,
то это несбалансированная задача с
дефицитом. Если
,
то это несбалансированная задача с
избытком. Чтобы определить суммарные
затраты на перевозки, достаточно
просуммировать произведения объёмов
каждой поставки на соответствующие им
удельные затраты на транспортировку.
План будет оптимальным, если эта сумма
(целевая функция F) будет сведена к
минимуму:
(2.4)
Транспортная задача является закрытой, если соблюдается условие (2.3). Если данное условие не соблюдается, то для приведения открытой транспортной задачи к закрытому виду вводится фиктивный потребитель ФВ или фиктивный поставщик ФА. Разница между производственной мощностью и спросом относится на его счёт. Расходы по доставке груза до фиктивного потребителя или фиктивного поставщика равны нулю, так как груз фактически не перевозится.
15) Нахождение первоначального базисного распределения поставок.
16) Критерий оптимальности базисного распределения поставок.
Как и в случае симплексного метода для определения оптимальности полученного базисного решения выразим целевую функцию через свободные переменные
F=F0+ ∑ Bij Xij . (5)
В выражении (5) суммирование ведется по свободным клеткам (i, j) . Коэффициент Bij при свободной переменной Xij называется оценкой соответствующей свободной клетки. Из выражения (5) следует, что оценка Bij равна приращению целевой функции ∆F при переводе в свободную клетку (i, j) единичной поставки (при этом значение переменной Xij увеличится с 0 до1). Очевидно, что, если Bij≥0 , то ∆F ≥0 , а если Bij<0 , то ∆F <0 .
Так как в транспортной задаче ищется минимум целевой функции, то критерий оптимальности формулируется следующим образом: базисное распределение поставок является оптимальным, если все оценки свободных клеток неотрицательны, то есть все Bij≥0.