Оптимизация транспортных систем

Размещено на http://www.allbest.ru/

Оптимизация транспортных систем

Москва 2008

1. Назначение разработки, область применения и её ограничения

Программно-методическая разработка по теме «Оптимизация транспортных систем» предназначена для студентов бакалавриата, обучающихся по направлениям «Государственное и муниципальное управление», «Менеджмент», «Экономика и управление промышленным предприятием» и др. Пособие может быть использовано для изучения предметов «Основы математического моделирования социально-экономических процессов», «Экономико-математические методы и модели», «Программные средства решения экономических задач», и т.п. Пособие содержит описание компьютерной технологии моделирования и оптимизации сетевой транспортной системы, в которой определен критерий оптимизации. Цель пособия - поддержка изучения базовых компьютерных технологий моделирования социально-экономических систем на уровне основных понятий теории оптимизации линейных сетевых транспортных систем и практических методов решения задач их оптимизации в среде электронного табличного процессора EXCEL с применением программы «Поиск решения». Приведено детальное описание компьютерной модели задачи оптимизации транспортной системы в среде EXCEL, интерфейсы используемых программ EXCEL, схемы размещения исходных данных и промежуточных и окончательных результатов расчетов. Пособие может быть полезным также и для студентов магистратуры, аспирантов, преподавателей и всех, интересующихся применением компьютерных технологий для моделирования социально-экономических процессов и преподавания соответствующих дисциплин. оптимизация транспортный компьютерный

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

Математическая модель. Исходные данные задачи включают в себя два вектора - вектор запасов А и вектор заказов В, а также матрицу тарифов С. Аргументом задачи является план поставок - матрица Х. Элементы матрицы Х - объемы поставок от поставщика номер I заказчику номер J.

Целевая функция задачи - суммарные затраты на всю операцию в целом. Если по направлению IJ планируется перевозка груза в объеме XIJ по тарифу CIJ, то затраты на это будут равны произведению этих величин ZIJ=CIJ*XIJ. Суммарные расходы на отгрузку продукции поставщика I можно выразить в форме . Общий суммарный расход на всю операцию теперь можно определить как сумму затрат всех поставщиков.

Теперь опишем ограничения на объемы отгрузки и поставки продукции. Для поставщика I объем поставок заказчику J равен XIJ. Общий расчетный (планируемый) объем отгрузки XI можно записать в виде . Поскольку запас продукции поставщика I равен AI, то планируемый объем отгрузки для него не должен превышать этого запаса. То есть должно выполняться М неравенств .

Рассматривая заказчика J, потребность которого в продукции равна BJ, можно выразить объем планируемых для него поставок в виде . По условию задачи расчетный суммарный объем поставок для заказчика J не должен быть меньше его потребности BI, то есть . Объединяя выражения целевой функции и ограничений, получаем модель

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

Следуя правилам построения двойственной задачи, можно получить двойственную транспортную задачу в виде

Здесь W(Y) - целевая функция двойственной транспортной задачи, представляющая собой оценку выгодности всей операции в целом во внутренних ценах продукции Y. Вектор двойственных цен продукции Y состоит из двух блоков - первый блок длиной M элементов содержит характеристики поставщиков, второй блок длиной N элементов содержит характеристики заказчиков. Символом GI в выражении для целевой функции обозначены компоненты обобщенного вектора запасов, который составлен из двух блоков - вектора запасов А с обратным знаком и вектора заказов В. Левые части функциональных ограничений двойственной транспортной задачи представляют собой разности ценностей единицы продукции для пар заказчик J - поставщик I. Эти разности не должны превышать соответствующих тарифов. Внутренние цены должны быть неотрицательными.

В матричной форме пара взаимно двойственных задач будет иметь вид

Здесь введены вспомогательные элементы, использование которых позволит в дальнейшем разработать эффективную компьютерную технологию моделирования транспортной системы. Это вектор-индикатор готовности поставщиков IR, вектор-индикатор заказчиков IP, вектора двойственных оценок запасов поставщиков YR и потребностей заказчиков YP. Поскольку в расчетах используются специальные операции - поэлеметное произведение матриц и ортогональная сумма векторов, для них введены специальные обозначения: знак * для первой и знак для второй

Компьютерная модель. Исходные данные для построения компьютерной модели транспортной системы размещены в таблице 1 (см. рис.). Это вектор-индикатор поставщиков IR[G7:G9] и вектор запасов А[H7:H9], вектор-индикатор заказчиков IP[C10:F10] и вектор заказов В[C11:F11], а также матрица тарифов С[C7:F9

После размещения исходных данных выполняются следующие шаги.

1. Отвести блок для размещения матрицы плана перевозок Х[C16:F18].

2. Ввести в ячейки блока Х исходный тестовый план Х=1.

3. Отвести блок [G16:G18] для вычисления левых частей ресурсных ограничений DR=-XЧIP =-МУМНОЖ(C16:F18;ТРАНСП(C10:F10))

4. Отвести блок [C19:F19] для вычисления левых частей плановых ограничений DP= (IR )ТЧX =МУМНОЖ(ТРАНСП(G7:G9);C16:F18).

5. Отвести блок [C25:F27] для матрицы затрат Z =C7:F9*C16:F18.

6. Отвести блок [G25:G27] для суммарных затрат на отгрузку для каждого поставщика ZR= ZЧ IP =МУМНОЖ(C25:F27;ТРАНСП(C10:F10)).

7. Отвести блок [C28:F28] для суммарных затрат на поставку для каждого потребителя ZP= (IR )ТЧZ =МУМНОЖ(ТРАНСП(G7:G9);C25:F27).

8. Выделить ячейку [G28] для значения целевой функции транспортной задачи Z(X)= (IR )ТЧZЧ IP =МУМНОЖ(C25:F27;ТРАНСП(C10:F10))

9. Настроить и запустить программу «Поиск решения».

Рис.1. Компьютерная модель сетевой задачи

Настройки программы «ПОИСК РЕШЕНИЯ» и результаты расчетов показаны на рисунках. В соответствии с полученными результатами оптимальным будет план, предусматривающий поставку первым поставшиком 88 единиц продукции первому заказчику и 62 - третьему; второй поставщик поставляет 40 единиц второму заказчику и 40 - четвертому; третий поставщик поставляет 22 единицы первому заказчику, 20 второму и 18 - третьему. Общие расходы равны 1110

Рис.2. Компьютерная модель двойственной задачи.

Для исследования полученного плана перевозок компьютерная модель может быть дополнена блоком решения двойственной задачи. Для нее используются те же исходные данные. Особенность двойственной задачи в рассматриваемом формате технологии компьютерного моделирования является то, что аргументы Y разделены на 2 блока. Первый [G33:G35] включает оценки, соответствующие запасам поставщиков. Второй [C36:F36] - оценки заказов потребителей. Эти величины позволяют определить, каким образом можно, перераспределив запасы или изменив объемы потребления, уменьшить транспортные затраты. Такие данные важны при организации систем снабжения, связи, транспорта и пр.

Компьютерная технология включает в себя две основные операции. Вначале - программирование блока левых частей ограничений двойственной задачи [C33:F35]. В этот блок заносим формулу =C$36-$G33 . Затем в ячейку целевой функции двойственной задачи W(Y)[G36] заносим формулу

=-МУМНОЖ(ТРАНСП(G33:G35);H33:H35)+МУМНОЖ(C36:F36;ТРАНСП(C37:F37))

После настройки программы «ПОИСК РЕШЕНИЯ» получены результаты, показанные на рис. 2. Сравнение целевых функций исходной и двойственной задач показывают, что обе задачи решены верно и решения обеих задач оптимальны. Значения двойственных оценок запасов и объемов заказов показывают, что недефицитным ресурсом исследуемой транспортной системы являются запасы второго поставщика. Их двойственная оценка равна 0 и, следовательно, их увеличение не позволит уменьшить суммарные расходы на всю транспортную операцию. Запасы остальных поставщиков, как и объемы заказов всех заказчиков, критичны с точки зрения суммарных затрат. Следовательно, данная транспортная система может быть оптимизирована как за счет увеличения запасов поставщиков, так и за счет изменения заказов потребителей.

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

2. Используемые технические и программные средства

Для создания данного электронного продукта использовался персональный компьютер типа Intel Pentium IV c операционной системой Microsoft Windows XP Professional версия 2005 Service Pack 2. Использовался пакет MS-OFFICE с текстовым редактором MS-Word 2003 и MS-Excel 2003.

Размещено на Allbest.ru