Динамическое и линейное программирование
[pic]
и прирост прибыли составит:
[pic]
Сводка результатов по пунктам 1-3 приведена в таблице 2.
|Таблица 2. |
|[pic|30 |11 |45 |6 |B |[pic|[pic|[pic]|
|] | | | | | |] |] | |
|[pic|3 |2 |6 |0 |150 |0 |6 |50 |
|] | | | | | | | | |
| |4 |2 |3 |5 |130 |0 |3 |[pic]|
| |4 |3 |2 |4 |124 |8 |0 |0 |
|[pic|22 |0 |14 |0 |1290 | | |[pic]|
|] | | | | | | | | |
|[pic|0 |7 |0 |9 | | | | |
|] | | | | | | | | |
4. Транспортная задача
Транспортная задача – это задача о минимизации транспортных расходов,
связанных с обеспечением пунктов потребления определенным количеством
однородной продукции, производимой (хранимой) в нескольких пунктах
производства (хранения). В общем виде задача может быть сформулирована
следующим образом:
Однородный продукт, сосредоточенный в [pic] пунктах производства
(хранения), необходимо распределить между [pic] пунктами потребления.
Стоимость перевозки единицы продукции известна для всех маршрутов.
Необходимо составить такой план перевозок, при котором запросы всех пунктов
потребления были бы удовлетворены за счет имеющихся продуктов в пунктах
производства и общие транспортные расходы по доставке продуктов были бы
минимальными.
Примем следующие обозначения:
|[pic]|Номер пункта производства (хранения) (i=1,2,…,m) |
|[pic]|Номер пункта потребления (j=1,2,…,n) |
|[pic]|Количество продукта, имеющиеся в i-ом пункте |
| |производства |
|[pic]|Количество продукта, необходимое для j-го пункта |
| |потребления |
|[pic]|Стоимость перевозки единицы продукта из i-го пункта |
| |отправления в j-ый пункт назначения |
|[pic]|Количество груза, планируемого к перевозке от i-го |
| |пункта отправления в j-ый пункт назначения |
Тогда, при наличии баланса производства и потребления:
[pic]
математическая модель транспортной задачи будет выглядеть следующим
образом:
найти план перевозок
[pic], где [pic]; [pic]
минимизирующий общую стоимость всех перевозок
[pic]
при условии, что из любого пункта производства вывозиться весь продукт
|[pic], где [pic] |(4.1) |
и любому потребителю доставляется необходимое количества груза
|[pic], где [pic] |(4.2) |
причем, по смыслу задачи
[pic], …, [pic]
Для решения транспортной задачи чаще всего применяется метод потенциалов,
при котором вводят обозначение вектора симплексных множителей или
потенциалов:
[pic]
Тогда:
[pic], где [pic]; [pic]
Откуда следует:
[pic], где [pic]; [pic]
При этом один из потенциалов можно выбирать произвольно, т.к. в системе
(4.1) и (4.2) одно уравнение линейно зависит от остальных, а остальные
потенциалы находятся, что для базисных значений [pic].
Предположим, что однородный продукт, находящийся в трех пунктах
производства (m=3), необходимо доставить в четыре пункта потребления
(n=4). При этом матрица [pic] транспортных затрат на перевозку единицы
продукта из любого пункта отправления в любой пункт назначения, вектор
[pic] объемов запасов продукта в пунктах производства и вектор [pic]
объемов продукта, необходимых пунктам потребления, имеют вид:
|[pic] |[pic] |
|[pic] | |
Тогда получается, что общий объем продукта в пунктах производства
[pic] больше, чем требуется всем потребителям [pic], т.е. имеем открытую
модель транспортной задачи.
Для того чтобы превратить открытую модель транспортной задачи в закрытую,
необходимо ввести фиктивный пункт потребления с объемом потребления
[pic] единиц,
при этом тарифы на перевозку продукта в этот пункт потребления будут равны
нулю, т.к. фактического перемещения продукта не происходит.
Тогда, первое базисное допустимое решение легко построить по правилу
«северо-западного угла». А т.к. оценки базисных клеток транспортной таблицы
равны нулю, то, приняв, что [pic], первая транспортная таблица и потенциалы
имеют вид:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |30 |11 |9 |* | |[pic]| | |
|70 | | |36 |34 | |[pic]| | |
|30 | | | |2 |28 |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, соответствует клетке 14, то строим цикл пересчета: 14-13-23-24 и
производим перераспределение поставок вдоль цикла пресчета:
|[pic] |[pic] |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |9 |* |( |[pic]|[pic]|( |0 |9 |
| |36 |34 | |[pic]|[pic]| |45 |25 |
| | |[pic] | |
То получаем второе базисное допустимое решение и находим новые
потенциалы, полагая [pic]:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |30 |11 | |9 | |[pic]| | |
|70 | |* |45 |25 | |[pic]| | |
|30 | | | |2 |28 |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Т.к. теперь наибольшая положительная оценка всех свободных клеток
транспортной таблицы, соответствует клетке 22, то строим цикл пересчета: 22-
12-14-24 и производим перераспределение поставок вдоль цикла пресчета:
|[pic] |[pic] |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
|[pic] | |
| |11 |9 |( |[pic]|[pic]|( |0 |20 |
| |* |25 | |[pic]|[pic]| |11 |14 |
| | |[pic] | |
Отсюда получаем третье базисное допустимое решение и находим новые
потенциалы, принимая [pic]:
|[|[|30 |11 |45 |36 |28 | |[pic] |[pic] |
|p|p| | | | | | |[pic] |[pic] |
|i|i| | | | | | |[pic] |[pic] |
|c|c| | | | | | |[pic] |[pic] |
|]|]| | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
| | | | | | | | |[pic] |[pic] |
|50 |30 | | |20 | |[pic]| | |
|70 |* |11 |45 |14 | |[pic]| | |
|30 | | | |2 |28 |[pic]| | |
| |[pic|[pic|[pic|[pic|[pic| | | |
| |] |] |] |] |] | | | |
Т.к. наибольшая положительная оценка всех свободных клеток транспортной
таблицы, теперь соответствует клетке 21, то строим цикл пересчета: 21-11-14-
24 и производим перераспределение поставок вдоль цикла пресчета:
|[pic] |[pic] |
|[pic] | |
|[pic] | |
|[pic] |
| |  скачать работу |
Динамическое и линейное программирование |
