Поиск оптимальных решений в задачах о перевозках

(транспортных задачах)

Цель работы: научиться составлять математические модели задач о перевозках (транспортных задачах); сформировать навыки исследования полученных моделей в среде табличного процессора MS Excel с помощью надстройки Поиск решения пакета Анализ данных.

Задания и методические указания по их выполнению

Постановка задачи. Рассмотрим пример задачи о перевозках, которую также часто называют транспортной задачей. Пусть в ГУФСИН по некоторому субъекту Российской Федерации имеется следственных изоляторов (поставщики), из которых необходимо отправить осуждённых в исправительных учреждений (потребители). Известны затраты на перевозку одного человека от каждого поставщика к каждому потребителю. Необходимо так спланировать перевозки осуждённых из следственных изоляторов в исправительные учреждения, чтобы суммарные затраты были минимальными.

Составление математической модели задачи

Введём обозначения:

– следственные изоляторы,

– исправительные учреждения,

– количество осуждённых для перевозки в ,

– количество осуждённых, которое может принять ,

– затраты (ден. ед.) на перевозку одного человека из в ;

– количество осуждённых, доставляемых из в .

В данном случае задача имеет размерность

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

Задачу (1), (2) можно решить аналитически с помощью математических методов (например, распределительный метод и метод потенциалов) без привлечения компьютерных технологий. Однако в реальных условиях при большой размерности задачи её решение «вручную» может оказаться очень громоздким, требующим больших временных затрат и большого числа итераций. Использование возможностей MS Excel позволяет решить транспортную задачу практически любой размерности каждому человеку, не имеющему даже представления о математических методах решения задач такого класса.