![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Переход от открытой ТЗ к закрытой ТЗ
Если задача является открытой, то необходимо провести процедуру закрытия задачи. С этой целью при a < b добавляем фиктивного поставщика A'm+1 с запасом груза a' m+1 = b – a. Если же a > b, то добавляем фиктивного потребителя B' n+1 с заказом груза b'n+1 = a – b. В обоих случаях соответствующие фиктивным объектам тарифы перевозок c'ij полагаем равными нулю. В результате суммарная стоимость перевозок z не изменяется. Решение ТЗ разбивается на два этапа: 1. Определение начального допустимого базисного решения (первоначального опорного плана) – первоначального распределения поставок. 2. Посроение последовательных итераций, улучшающих опорный план (каждый новый план не должен увеличивать сумарные затраты). Существует несколько способов нахождения опорного плана (исходного решения). 1) Метод «северо-западного» угла (диагональный метод) заключается в заполнении клеток таблицы таким образом, чтобы последовательно закрывались столбцы таблицы. Заполнение таблицы начнем с клетки (1, 1). Так как х11 = min{300, 200} = 200, то первый столбец закрыт, при этом остаток на базе А составляет 100 единиц. Рассмотрим заполнение второго столбца таблицы. Так как потребности пункта № 2 составляют 250 единиц, то они могут быть удовлетворены поставкой из базы А 100 единиц и из базы В 150 единиц. Таким образом, x12=min{300-200, 250} = 100, a х22 = min{250-x12, 250} = min{150, 250} = 150. Заполнение второго столбца закончено. Переходим к заполнению третьего столбца. Потребности пункта № 3 составляют 250 единиц, наличие на базе В составляет 350 - х22 = 200 единиц, поэтому удовлетворение потребности пункта № 3 возможно поставками с базы В 200 единиц и с базы С 50 единиц, т. е. х23=200, а х33 = min{250-x23, 250] = 50, остаток на базе С 400 - х33 = 400 - 50 = 350 единиц. Заполнение третьего столбца закончено. Переходим к заполнению четвертого столбца. Так как потребности пункта № 4 — 350 единиц, то они полностью удовлетворяются поставкой с базы С, поэтому х34 = 350 (табл. 1). Таблица 1 Остатки по столбцам и строкам равны нулю, следовательно, опорное решение построено. Этому опорному решению соответствуют затраты: L = 1∙ 200 + 2∙ 100 + 8∙ 150 + 4∙ 200 + 9∙ 50 +1∙ 350 = 3200 (денежных единиц). В методе «северо-западного» угла не учитывается величина затрат (стоимость перевозок), поэтому опорное решение может быть далеким от оптимального, что может привести к увеличению числа построений последовательных итераций, т. е. увеличению количества приближений к оптимальному решению. Этот недостаток может быть устранен методом «минимального элемента», который заключается в том, что при построении опорного решения (плана) учитывается величина затрат. Построим опорное решение данной задачи, применяя метод «минимального элемента».
2) Метод «минимального элемента» Построение опорного решения начнем с клетки, имеющей наименьшую стоимость. Таких клеток две: (1, 1) и (3, 4), значение стоимости в каждой из них равно 1. Рассмотрим клетку (1, 1). В эту клетку заносим значение х11 = 200, тем самым полностью закрывая первый столбец. В клетку (3, 4) заносим значение х34 = 350, закрывая четвертый столбец. Остатки по первой и третьей строкам равны соответственно 100 и 50 единицам (табл. 2).
|