Минимизация стоимости перевозок (стр. 1 из 2)

‚ ваҐе еа Ё«Ёй е Ј®ао祣® Ґ¦Ґ¤Ґў® еа пвбп 180, 350 Ё 20 в. ЎҐ§Ё .
ќв®в ЎҐ§Ё Ґ¦Ґ¤Ґў® Ї®«гз ов Їпвм § Їа ў®зле бв жЁ© ў Є®«ЁзҐc⢥ а ў®¬
ᮮ⢥вб⢥® 110, 90, 120, 80, Ё 150 в. ЎҐ§Ё .
‘в®Ё¬®бвм ЇҐаҐў®§®Є 1 в. ЎҐ§Ё б еа Ё«Ёй Є § Їа ў®зл¬ бв жЁп¬ § ¤ ов
¬ ваЁжҐ©.

( 7 12 4 6 5 )
‘ = ( 1 8 6 5 3 )
( 6 13 8 7 4 )

‘®бв ўЁвм в Є®© Ї« ЇҐаҐў®§®Є ЎҐ§Ё ЇаЁ Є®в®а®¬ ®Ўй п бв®Ё¬®бвм ЇҐаҐў®§®Є
пў«пҐвбп ¬ЁЁ¬ «м®©.

28

КП.2203 81-16

ВВЕДЕНИЕ.

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

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

При решении практических операционных задач находят эффективное применение различных оптимизационных моделей и методов оптимизации, основанные на использовании математического программирования.

При использовании электронно-вычислительной техники возрастает эффективность операционных методов анализа и решения задач оптимизации в сфере организационного управления.

Применение электронно-вычислительной техники позволяет решать сложные задачи, математическая постановка, которых сопряжена с необходимостью рассмотрения “крупномасштабных” моделей, содержащих большое число ограничений. При решение такого рода задач без применений электронно-вычислительной техники невозможно. Использование этой техники приводит к ускорению темпов производства, что и требуется для развития экономики математических методов.

1. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ.

В трёх хранилищах горючего ежедневно хранится 180, 350 и 20т бензина.

Этот бензин ежедневно получают пять станций в количествах равных соответственно 110, 90, 120, и 150т бензина. Стоимость перевозок 1т бензина с хранилищ к заправочным станциям задают матрицей:

Составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.

2. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ. ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.

m – хранилища, в которых хранятся бензин (i=1,2…m);

Ai – ресурсы в хранилищах;

n – заправочные станции j–ого вида (j=1,2…n);

Bj – заявки АЗС;

Cij – стоимость перевозок 1т бензина из i-го хранилища на j-ую заправочную станцию;

xij – перевозки бензина, т.е. количество бензина перевозимого i-го хранилища в j-ую заправочную станцию;

Балансовое ограничение:

2. Плановые ограничения:

(j=1,2…n)

3. Неотрицательность переменных:

xij>=0 (4)

4. Целевая функция:

3. ВЫБОР МЕТОДА РЕАЛИЗАЦИИ МОДЕЛИ И ОБОСНОВАНИЕ ВЫБОРА.

Симплекс-метод является универсальным и применим для решения любых задач. Однако существуют некоторые частные типы задач линейного программирования, которые в силу некоторых особенностей своей структуры допускают решение более простыми методами. Для решения моей задачи целесообразно использовать транспортную задачу линейного программирования (ТЗЛП) методом потенциалов.

3.1. Алгоритм решения ТЗЛП методом потенциалом.

Строим закрытую модель ТЗЛП, а именно: сумма всех заказов должна равняться сумме всех заявок:

Если соблюдать модель условно, то такая модель называется закрытой.

Если условие не соблюдать, то такая модель ТЗЛП с неправильным балансом.

В этом случае может быть два варианта:

а) ТЗ с избытком запаса

вводим фиктивного потребителя (фиктивный столбец), которым приписываем заявку, равную разности запасов и заявок:

Сiф=0, ( i=1,2…m) – стоимость фиктивных перевозок равна нулю.

Это означает, что если в какой-либо ячейке фиктивного столбца по плану будет стоять перевозки xij, то фактически эти перевозки останутся не отправленными. Вводят Bф с его заявкой bф, мы уравниваем баланс ТЗ, и теперь эту задачу можно решать как обычную ТЗ.

б) ТЗ с избытком заявок

вводим фиктивного поставщика (фиктивная строка), которым описываем заказчика aф:

Сij=0 (j=1,2…n)

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

Составляем первый опорный план перевозок, в которых обеспечены

m+n-1 базисных клеток, по методу северо-западного угла.

Допустим, план называется опорным, если в нем отличных от нуля не более чем

r=m+n-1 базисных переменных (перевозок), а остальные равны нулю.

План (xij) называется оптимальным, если он среди всех допустимых планов приводит к наименьшей стоимости всех перевозок.

Таблица 2.

Транспортная таблица.

ПО/ПН	B1	B2	… Bn	ЗАПАСЫ ai
A1 A2 … Am	C11 C21 … Cm1	C12 C22 … Cm2	… C1n … C2n … … … Cmn	a1 a2 … am
ЗАЯВКИ bJ	b1	b2	… bn

ПН – пункт назначения;

ПО – пункт отправления.

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

Не учитывая стоимости перевозок и единицы груза, производим удовлетворение потребностей 1-ого потребителя В1 за счет запаса поставщика А1, начиная с верхнего левого угла.

Для этого сравниваем а1 с b1. Меньший из объемов записываем в клетку А1В1.

Процесс продолжаем до тех пор, пока не удовлетворим всех потребностей за счет запасов. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце – заявке.

Клетки таблицы, в которых не нулевые перевозки являются базисными, и их число удовлетворяет условию r=m+n-1. Остальные клиенты свободные в них стоят нулевые перевозки, их число равно (n-1)*(m-1). Полученное решение является не только допустимым, но и опорным решением ТЗ.

Если число базисных клеток r

m+n-1, то вводим r бесконечно малых фиктивных перевозок, например .

Для первого плана строим систему платежей. Предположим, что каждый из пунктов отправления А: вносит за перевозки единицы, какую-то сумму i, какому-то третьему лицу; в свою очередь каждый из пунктов значения Bj так же вносит за перевозку единицы груза этому же лицу сумму j. i и j называются платежами. Обозначим сумму этих платежей:

Si,j=i+j, (12)

( i=1,2…m, j=1,2…n )

и назовем псевдостоимостью.

Теорема платежей:

Если:

а) для базисных клеток (xi,j>0) i+j=Si,j=Ci,j (псевдостоимость равна стоимости);

б) для свободных клеток (xi,j0) i+j=Si,j>0 (псевдостоимость больше стоимости), то план не является оптимальным.

Если же первое условие выполняется, а второе Si,jCi,j, то план является оптимальным и никаким образом улучшен быть не может.

С помощью базисных клеток, в которых сумма этих платежей равна Si,j=Ci,j=i+j (i=1,2…m j=1,2…n), а число базисных клеток равно r, то первый платеж значением произвольно (например, 1=0).

Находим псевдостоимость для всех свободных ячеек, и если в каждой свободной клетке Si,jCi,j, то план оптимален и считаем целевую функцию.

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

4. СИМВОЛЬНАЯ СХЕМА АЛГОРИТМОВ.

Процедура balans.

Процедура north_west_angle.

Процедура PEpsilon.

Процедура psevdostoimost.

Процедура Pmax.Процедура Px1.

Процедура Pschet.