Математические методы

  • 18 янв. 2013 г.
  • 3230 Слова
Формулировка задачи

Существует транспортная компания “N”, перевозящая груз (например – пищевые продукты в упаковке: кофе, чай, минеральная вода, лимонад и др.), из двух складских помещений нескольким потребителям. Компания располагает грузовыми автомобилями грузоподъемностью 1 тонна. Коэффициент использования грузоподъемности для данного вида груза примем равным 1. Даны расстояния отгаража до складов, от гаража до клиентов, между складами и клиентами. Также указан объем груза на каждом складе и объем груза, который необходимо доставить каждому клиенту. Необходимо перевезти груз из 2-х складов (пункт А) 3-м клиентам (пункт В). Используя математические методы, нужно найти оптимальное закрепление потребителей за поставщиками, рассчитать рациональные маршруты для доставки всегогруза, найти необходимое количество автомобилей для перевозки всего груза. Исходные данные, обозначение и конкретизированное задание приведены ниже.




Теоретическая часть

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

Сначала определяем численные значения в таблице исходныхданных.

Для нахождения оптимального плана поставок необходимо использовать метод потенциалов. Недостатком данного метода является то, что необходимо иметь опорный план, который находится следующими методами:

- метод «северо-западного угла»

- метод «минимального тарифа»

- метод Фогеля.

Составим базисный опорный план методом северо-западного угла.

Для этогонеобходимо исходные данные занести в таблицу, представленную в пункте 1.1-1.2 решения данной работы.

Дадим переменной X11 максимальное значение, иными словами максимальную поставку в клетку (1;1) - «северо-западный угол». Потом ищем следующий «северо-западный угол» - это переменная X12. Даем ей максимально возможное значение. Переходим в ячейку (1;3) и помещаем туда возможную перевозкуХ13. После этого возможности первого поставщика (склада) полностью исчерпаны. Следовательно, первая строка выпадает из рассмотрения. Во второй строке остается только переменная X23, в которую мы делаем максимальную поставку для последнего пункта назначения.

Используем метод «минимального элемента по столбцу». Данный метод является более рациональным, т.к. учитывается минимальный тариф,в нашем случае минимальное расстояние, выбор которого минимизирует затраты.

Потребности и запасы совпадают, следовательно, мы имеем транспортную задачу закрытого типа.

Для поиска оптимального значения необходимо использовать метод потенциалов. Необходимое условие в этом методе - наличие любого допустимого решения (найденное любым из ранее рассмотренных способов).



Алгоритмрешения.
Возьмем существующий допустимый план (т.е. есть "свободные" ячейки - xy=0 и "занятые" ячейки -xy>0).
Проверим вырожденность исходного плана. Если число занятых клеток в опорном плане меньше чем (т + п - 1) , то не хватит числа уравнений для определения значений потенциалов, и необходимо дополнительно внести в свободные клетки таблицы нули, чтобы общее число занятых клеток было равно (т+ п - 1).
Для данного плана запишем условия потенциалов. В нашем случае должно быть занято 4 клетки. Поэтому выбираем второй опорный план, найденный методом минимального элемента (так как в этом случае величина транспортной работы меньше)
Берем занятые ячейки. (значение U соответствует А, значение V соответствует В):
U1+V1=2
U1+V3=29
U2+V2=8
U2+V3=18Решим полученную систему уравнений. Примем U1=0. Получаем:
U1=0, тогда
V1=2
V3=29
U2= -11
V2=19
Так как задача решается на минимум, то в свободных ячейках должно выполняться условие E ij >=0 (Xij=0).

[pic]

План оптимален, и не требует улучшения.

В оптимальном плане значение транспортной работы будет минимальным,...
tracking img