Поиск оптимального плана перевозок

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

ЗАДАНИЕ ДЛЯ ЛАБОРОТОРНОЙ РАБОТЫ НА ТЕМУ: «ПОИСК ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК».

Задание - сформировать математическую постановку транспортной задачи линейного программирования, найти решение транспортной задачи с помощью надстройки пакета Microsoft Excel «Поиск решения», проанализировать объём перевозок и теневые цены по отчёту по устойчивости решения задачи.

Задача: Вариант 14. Найдите решение транспортной задачи, исходные данные которой определяются таблицей и матрицей D.

где С - № варианта;

транспортный задача перевозка программирование

Матрица D

14) .

1. Математическая постановка задачи. Рассмотрим следующую задачу.

Найдите решение транспортной задачи, исходные данные которой определяются таблицей 1 и матрицей

.

Таблица 1

Исходные данные транспортной задачи

Числа в матрице D определяют граничное количество груза, которое можно перевезти с данного пункта отправления в соответственный пункт назначения.

Символ ? означает, что на перевозки с данного пункта отправления в соответствующий пункт назначения не имеет ограничений.

Постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза с m пунктов отправления А₁, А₂, А₃ в n пункты назначения В₁, В₂, В₃, В₄, В₅. При этом в качестве критерия оптимальности обычно берётся либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, как критерий оптимальности которой взята минимальная стоимость перевозок всех грузов. Обозначим через с_ij тарифы перевозок единиц грузов с i-го пункта отправления в j-й пункт назначения, через a_i - запасы груза в i-ом пункте отправления, через b_j - потребности в грузе в j-м пункте назначения, через d_ij - пропускные возможности груза с i-того отправления в j-й пункт назначения, а через x_ij - количество единиц груза, перевезенного с i-того пункта отправления в j-тый пункт назначения. Тогда математическая постановка задачи приобретает вид:

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

2. Поиск оптимального плана перевозок. Найдём суммарные запасы и суммарные потребности.

Как видно на рис. 1., суммарные потребности превышают суммарные запасы на 28 единиц, поэтому задача является открытой и должна быть приведена к закрытому виду путём введения фиктивного пункта отправления А₄ с запасом, равным 28.

Рис. 1 Таблица исходных данных транспортной задачи

G7 = СУММ(G3:G5)

H6 = СУММ(B6:F6)

Рис. 2 Таблица для расчётов транспортной задачи

G3 = СУММ(B3:F3)

B3 = СУММ(B9:B12)

C3 = СУММ(C9:C12)

D3 = СУММ(D9:D12)

E3 = СУММ(E9:E12)

F3 = СУММ(F9:F12)

G9 = СУММ(B9:F9)

G10 = СУММ(B10:F10)

G11 = СУММ(B11:F11)

G12 = СУММ(B12:F12)

J8 = СУММПРОИЗВ(B9:F11;B3:F5)

Рис. 3 Окно «Поиск решения» с условиями транспортной задачи

Рис. 4 Результаты окна «Поиска решений» с условиями транспортной задачи

Таким образом, оптимальный план перевозок груза с трёх (реальных) пунктов отправления к пяти пунктам назначения, при котором минимизируется функция совокупных затрат на перевозки (F = 7090), имеет следующий вид:

Стоит отметить, что потребность в пункте назначения B₄ не удовлетворена в размере 28 единиц соответственно.

3. Анализ отчёта по устойчивости. В первой таблице отчёта (рис. 5), которая имеет название «Ячейки переменных», в столбце «Приведенная Стоимость» представлены значения, на которые увеличится целевая функция (стоимость перевозок) при увеличении объёма перевозок на данном маршруте.

Рис. 5 Таблица «Ячейки переменных» отчёта по устойчивости транспортной задачи

Из первой таблицы отчёта видно, на какую величину следует снизить затраты на перевозку в неиспользуемых направлениях, чтобы перевозить грузы в этих направлениях стало выгодно.

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

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

Рис. 6 Таблица «Ограничения» отчёта по устойчивости транспортной задачи

В столбце «Тень Цена» для пунктов отправления и назначения приведена величина, на которую изменится значения целевой функции при изменении запаса пункта отправления или потребления пункта назначения соответственно на единицу.

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