Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Имеется три поставщика и пять потребителей некоторой продукции. Количество груза , которое может отгрузить поставщик , стоимость перевозки из пункта в пункт единицы груза и потребности потребителей в грузе , заданы матрицей:
= .
Составить экономико-математическую модель задачи и найти методом потенциалов оптимальный план перевозки груза, при котором общие транспортные затраты будут наименьшими.
РЕШЕНИЕ
Строим математическую модель задачи. Через Хij обозначим объем продукции, доставленной от поставщика Ai (i=l,2,3) потребителю Bj (). Отметим, что в данном случае сумма количества продукции, которую могут отгрузить все поставщики, совпадает с суммой потребностей потребителей:
310+360+230=140+190+180+170+220 = 900.
Значит, задача закрытого типа и имеет решение. Математическая модель задачи принимает вид:
(1)
(2)
. (3)
Строим начальную распределительную таблицу:
Таблица 5
В1 | В2 | Вз | В4 | В5 | аi | Ui | |
А1 | -4 | ||||||
А2 | + 3 * | – 8 | |||||
A3 | – 1 | + 2 | -6 | ||||
Построенному опорному решению отвечают затраты:
Z1 = 90∙2+220∙1+100∙8+90∙6+170∙10+140∙1+90∙2 = 3760.
Проверим полученный опорный план на оптимальность. Для этого i-й строке и j-му столбцу ставим в соответствие числа Ui и Vj (потенциалы). Для каждой базисной переменной Хij потенциалы должны удовлетворять условию
Получаем систему:
Ui +Vj = Сij.
U1+V3 = 2, Так как система состоит из 7 уравнений, а неизвестных
U1+V5 = l, 8, то, чтобы найти численное решение этой системы, U2+V2 = 8, одно из неизвестных зададим произвольно, тогда
U2+V3 = 6, остальные переменные найдутся из системы однозначно.
U2+V4 = 10,
U3+V1 = 1,
U3+V2 = 2.
Пусть U2 = 0, тогда V2 = 8, V3 = 6, V4 = 10, U1 = -4, U3 = -6, V1 = 7, V5 = 5.
Теперь для небазисных переменных (свободных клеток) найдем оценки
Sij = Сij –(Ui +Vj): | |
S11 = 5 - (-4 + 7) = 2 | S21 = 3 - (0 + 7) = -4 |
S12 = 3 - (-4 + 8) = -1 | S25 = 5 - (0 + 5) = 0 |
S14 = 4 - (-4 + 10) = -2 | S33 = 3 - (-6 + 6) = 3 |
S35 = 4 - (-6 + 5) = 5 | S34= 5 - (-6 + 10) = l |
В силу критерия оптимальности опорного плана (все оценки Sij неотрицательны) делаем вывод, что построенный план не оптимален, т.к. среди оценок есть отрицательные. В базис введем переменную Х21 (отвечающую наибольшей по модулю отрицательной оценке) и строим замкнутый контур с вершинами в загруженных клетках. Присваиваем клеткам в вершинах контура поочередно по часовой стрелке знаки " + " и " – ", начиная с (2,1), которой присваиваем знак " + ". Выбираем наименьшее значение из клеток со знаком
" – " (min (140,100) = 100) и перераспределим продукцию вдоль контура: прибавляя 100 к значениям в клетках со знаком "+" и вычитая из значений в клетках со знаком " – ". В результате приходим к таблице 6.
Таблица 6
В1 | В2 | Вз | В4 | В5 | аi | Ui | |
А1 | -4 | ||||||
А2 | + 3 100 | – 10 | |||||
A3 | – 1 | + 5 * | -2 | ||||
Полученному решению отвечают затраты:
Z2 = 90∙2+220∙1+100∙3+90∙6+170∙10+40∙1+190∙2=3360.
Проверяем полученный план на оптимальность и получаем, что S34 = -3 < 0. Значит, решение не оптимальное и строим в таблице 6 новый цикл пересчета для клетки (3,4). Так как min(170,40)=40=Х31,то перераспределяем продукцию вдоль контура, прибавляя 40 к значениям в клетках со знаком " + " и вычитая из значений в клетках со знаком " – ". В результате получаем таблицу 7.
Таблица 7
В1 | В2 | Вз | В4 | В5 | аi | Ui | |
А1 | – 2 – | + 4 * | -4 | ||||
А2 | + 6 | – 10 130 | |||||
A3 | 190 | -5 | |||||
Полученному решению отвечают затраты:
Z3 = 90∙2+220∙l+140∙3+90∙6+130∙10+190∙2+40∙5=3240.
Аналогично предыдущему проверяем полученный план на оптимальность. Получаем, что S14 = - 2 < 0. Теперь для улучшения плана загрузим клетку (1,4). В итоге приходим к таблице 8.
Таблица 8
В1 | В2 | Вз | В4 | В5 | аi | Ui | |
А1 | + 4 | – 1 | -6 | ||||
А2 | б | – 10 | + 5 * | ||||
A3 | -5 | ||||||
Z4 = 90∙4+220∙l+140∙3+180∙6+40∙10+190∙2+40∙5=3060.
Среди оценок свободных клеток имеем S25 = -2<0, следовательно, полученный план перевозок не является оптимальным, и для его улучшения необходимо загрузить клетку (2,5). В итоге вычислений приходим к таблице 9.
Таблица 9
В1 | В2 | Вз | В4 | В5 | аi | Ui | |
А1 | -4 | ||||||
А2 | б | ||||||
A3 | -3 | ||||||
Z5 = 130∙4+180∙l+140∙3+180∙6+40∙5+190∙2+40∙5=2980.
Полученный план оказывается оптимальным, так как все оценки незагруженных клеток неотрицательны. По этому плану перевозок 1–й поставщик отправляет 130 ед. продукции потребителю В4 и 180 ед. – B5; 2–й поставщик – 140 ед. потребителю В1, 180 ед. потребителю B3 и 40 ед. потребителю В5; 3–й поставщик – 190 ед. потребителю B2 и 40 ед. потребителю В4.
Дата публикования: 2015-03-26; Прочитано: 190 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!