Лабораторные работы по Методам Оптимизации

Введение.

   Транспортная  задача – одна из распространенных задач линейного программирования. Ее цель - разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Все это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и так далее.

   Алгоритм  и методы решения транспортной задачи могут быть использованы при решении  некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. К таким задачам относятся следующие:

         - оптимальное закрепление за станками операций по обработке деталей. Задача позволяет опреде –лить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей;

         - оптимальные назначения или проблема выбора. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;

         - задача о сокращении производства с учетом суммарных расходов на изготовление и транспорти –ровку продукции;

         - увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.

Постановка  задачи

   Фирма имеет три магазина розничной торговли, расположенные в разных районах города (А, В, С). Поставки продукции в эти магазины осуществляются с четырех складов (1,2,3,4).

   Стоимости перевозок груза даны в таблице: 

 

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

Транспортная  задача

   Транспортная  задача ставится следующим образом: имеется m пунктов отправления А₁, А₂ , ..., А_m , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а₁, а₂, ... , а_m единиц. Имеется n пунктов назначения В₁ , В₂ , ... , В_n подавшие заявки соответственно на b₁ , b₂ , ... , b_n единиц груза. Известны стоимости С_ij перевозки единицы груза от каждого пункта отправления А_i до каждого пункта назначения В_j. Все числа С_ij, образующие прямоугольную таблицу, заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

   Данная  транспортная задача является задачей  с правильным балансом, так как  сумма потребностей магазинов и  количество товаров на складах одинаковы: 40 + 20 + 40 = 100, 30 + 25 + 15 + 30 = 100. 
 

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

   Перевозки расставляются следующим образом: магазин A подал заявку на 40 единиц груза. Удовлетворим эту заявку за счет запаса 30, имеющегося  в  пункте  № 1, и запишем перевозку 30 в клетке U₁,V₁. Но нам нужно поставить в A еще 10 единиц груза, чтобы полностью удовлетворить его потребность. Возьмем недостающие 10 единиц со склада № 2 и запишем перевозку 10 в клетку U₂,V₁. На складе № 2 у нас осталось еще 15 груза, направим их в магазин B. Недостающие 5 единиц добавим в B со склада № 3. Оставшийся там груз в количестве 10 направим в магазин C, в который недостающие 30 единиц груза привезем со склада № 4, где у нас как раз 30 единиц.

   В итоге у нас получилось такое  распределение перевозок: 

 

   Этот  план удовлетворяет балансовым условиям. При этом значение функции перевозок составит: 

L = 30 • 3 + 10 • 5 + 15 • 4 + 5 • 3 + 10 • 5 + 30 • 5 = 415. 

   Рассчитаем  для полученного плана потенциалы. Для удобства будем обозначать клетки комбинацией

(U_i; V_j), где i – номер строки, j – номер столбца.

   Пусть U₁ = 0. Тогда, чтобы выполнялось условие U_i + V_j = C_ij в клетке (U₁; V₁), нужно выполнить следующий расчет:

V₁ = C₁₁ – U₁ = 3 – 0 = 3.

Аналогично для  клетки (U₂; V₁), при уже известном V₁, рассчитаем U₂:

U₂ = C₂₁ – V₁ = 2.

   Следующая клетка с перевозками – (U₂; V₂), для нее известно U₂ = 2, а значит V₂ = 4 – 2 = 2. Анало –гично рассчитаем потенциалы остальных клеток:

U₃; V₂: V₂ = 2,        U₃ = 3 – 2 = 1.

U₃; V₃: U₃ = 1,        V₃ = 5 – 1 = 4.

U₄; V₃: V₃ = 4,       U₄ = 5 – 4 = 1.

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

   U_i + C_ij > V_j.

   Выполним  расчет для всех оставшихся свободных  клеток.

U₁; V₂: U₁ + С₁₂ = 0 + 1 = 1 < 2

U₁; V₃: U₁ + С₁₃ = 0 + 3 = 3 < 4

U₂; V₃: U₂ + С₂₃ = 2 + 2 = 4 ≥ 4

U₃; V₁: U₃ + С₃₁ = 1 + 4 = 5 > 3

U₄; V₁: U₄ + С₄₁ = 1 + 1 = 2 < 3

U₄; V₂: U₄ + С₄₂ = 1 + 5 = 6 > 2

   Условие оптимальности не выполняется. Чтобы  улучшить план, необходимо переместить  перевозку в клетку, где условие оптимальности нарушено больше всего, то есть разность V_j – (U_i+C_ij) максимальна. Такой клетки у нас нет, поскольку в трех клетках разность одинакова, поэтому выберем клетку, которая позволяет составить многоугольник, необходимый для выполнения перемещения. Это клетка – (U₁; V₂).

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

 

   L = 15 • 3 + 15 • 1 + 25 • 5 + 5 • 3 + 10 • 5 + 30 • 5= 400. 

   Повторим  проделанные в первом случае расчеты. Как и тогда при U₁ = 0  V₁ = 3.

U₁; V₂: U₁ = 0,         V₂ = 1 – 0 = 1.

U₂; V₁: V₁ = 3,         U₂ = 5 – 3 = 2.

U₃; V₂: V₂ = 1,        U₃ = 3 – 1 = 2.

 U₃; V₃: U₃ = 2,        V₃ = 5 – 2 = 3.

U₄; V₃: V₃ = 3,        U₄ = 5 – 3 = 2.

U₁; V₃: U₁ + С₁₃ = 0 + 3 = 3 ≥ 3

U₂; V₂: U₂ + С₂₂ = 2 + 4 = 6 > 1 

U₂; V₃: U₂ + С₂₃ = 2 + 2 = 4 > 3

U₃; V₁: U₃ + С₃₁ = 2 + 4 = 6 > 3

U₄; V₁: U₄ + С₄₁ = 2 + 1 = 3 ≥ 3

U₄; V₂: U₄ + С₄₂ = 2 + 5 = 7 > 3

   Как мы видим в последней таблице условие оптимальности выполняется для всех свободных клеток. Следовательно, это решение является оптимальным.

   Ответ: оптимальный план содержит шесть  перевозок:

         - с первого склада  – 15 единиц магазину А и  столько же магазину В;

         - со второго склада – 25 единиц магазину А;

         - с третьего склада  – 5 единиц магазину В и 10 единиц магазину С;

         - с четвертого склада – 30 единиц магазину С.

При этом общая сумма транспортных расходов минимальна и составляет 400 денежных единиц.

   Решим эту же задачу, но на этот раз изменим первоначальные значения. Пусть в клетке (U₁; V₃) количество поставок будет равно 1, а не 3, как было до этого.