Способ аппроксимации Фогеля

СПОСОБ ДВОЙНОГО ПРЕДПОЧТЕНИЯ

Очень удобен при решении распределительных задач вручную и может дать наилучшие результаты, В матрице затрат (табл. 6) находится клетка с минимальным элементом в каждой строке. Клетки, имеющие минимальные элементы, отмечаем звездочкой. Затем ищем клетки с минимальными затратами в столбцах и помечаем звездочками. В клетки, имеющие две звездочки, размещаем максимально возмож­ные объемы работ. Затем, в клетки, помеченные одной звездочкой, размещаем оставшиеся объемы работ. Если объемы работ не размещены полностью на этом этапе, то ищутся клетки, не помеченные звездоч­кой, но с наименьшими значениями, куда и вносится оставшийся объем работ.

Таблица 6.

Комплект машин	Приведенные затраты Cij на выполнение единицы объема работ по объектам строительстваBJ	Годовая выработка машин,Пi
Bl	B2	B3	B4
А1					24 **
А2			18 *
А3			10 **
А4	3 **						8 *
Годовой объем работ,YJ

В результате построения опорного плана способом двойного предпочтения целевая функция будет равна:

У = 3∙ 30 + 10∙22 + 24∙14 + 56∙1 +72∙19 +30∙4 +8∙11 = 2278.

В большинстве случаев дает опорный план самый близкий к опти­мальному. Поэтому его рекомендуют использовать при расчетах вруч­ную по матрицам большого размера. При данном способе, ищутся раз­ности в каждой строке и в каждом столбце матрицы (таблица 6) между наименьшей и ближайшей к ней по величине приведенных затрат. Раз­ности по строкам записываются справа в столбце разностей, разности по столбцам - в строке разностей (внизу). В нашем случае для строки А 1 разность (Al В2 - А1/ВЗ) - 38 - 24 = 14 и т.д. После проведения расчетов по столбцу и строке выбирают максимальную разность и выделяют ее (38). В сроке (или столбце), где помечена максимальная разность, находится наименьшее значение приведенных затрат, куда и вносится максимально-возможный объем работ. В нашем случае в строке - А2 клетка- А2В2 размещаем объем работ равный 20. т,е, всей годовой выработке комплекта машин А2. Поскольку годовая выработка комплекта машин А2 исчерпана, строку А2 исключаем из дальнейших расчетов, для чего отметим все клетки этой строки звездочками. После этого снова вычисляем разности по столбцам и строкам., не принимая во внимание приведенные затраты., имеющие объемы работ и помеченные звездочками,

Во втором расчетном случае (по второй строке и столбцу раз­ностей наибольшее значение разности - (В3=76), по столбцу ВЗ ищем наименьшее значение приведенных затрат (клетка А1ВЗ = 24) в которую помещаем объем работ равный 14. и выводим из дальнейших расчетов строку А1. помечая звездочками клетки соответствующей строки.

Таким образом, проводим все расчеты до полного распределения объема работ по клеткам матрицы, что соответствует распределению машин по объектам строительства с указанным объемом работ на каж­дом объекте

табл. 7 см. на сл. странице.

Окончательно целевая функция равна:

У = 24∙14 + 18∙20 + 19∙23 + 10∙2 + 100∙1 + 3∙7 + 8∙34 =1546

В качестве опорного (начального) плана для решения нашей задачи выберем наиболее удачный (имеющий наименьшее значение целевой функции У - 1546) т. е. способ аппроксимации Фогеля. После этого переходим ко второму этапу решения распредели­тельной задачи.

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

1. Распределительный метод

2. Метод потенциалов и другие.

Основой вычислительного процесса (алгоритма) этих методов является определение критерия оптимальности

Р ij = С ij – К ij

Таблица 7

Комплект машин

Приведенные затраты Cij на выполнение единицы объема работ по объектам строительстваBJ

Годовая выработка машин,Пi

Столбец разностей

Bl

B2

B3

B4

А1

-

-

-

-

-

-

-

А2

-

-

-

-

-

-

-

-

А3

-

-

А4

-

-

-

Годовой объем работ,YJ

Строки Разно-стей

-

-

-

-

-

-

-

где: С ij - затраты связанные с выполнением единицы объема

работ i комплектом машин на J объекте.

К ij - расчетные затраты, связанные с выполнением единицы

объема работ i комплектом машин на J объекте, определяемые для

клеток, в которые не распределены объемы работ.

Если все Р ij ≥ 0, то данный опорный план оптимален, если нет, то с помощью этого критерия можно указать способ улучшения данного опорного плана.

Для этого необходимо:

1. Составить и решить систему уравнений с некоторыми переменными

У j - П i = С ij

При этом использовать те индексы ij на пересечении которых в соот­ветствующих клетках распределены объемы работ.

Для нашей задачи система уравнений будет выглядеть так:

УЗ - П1 = 24

У2 - П2 = 18

У1 - ПЗ = 19

У2 - ПЗ = 10

УЗ - ПЗ = 100

У1 - П4 = 3

У4 - П4 = 8

Имеем 7 уравнений и 8 неизвестных, поэтому одному из неизвестных желательно наиболее часто встречающемуся в уравнениях, дать произвольное значение, как правило, для облегчения счета равное нулю, В нашей системе уравнений наиболее часто встречающееся неизвестное – П 3.

Положим П 3 = 0. Решая последовательно соответствующие уравне­ния, получим:

УЗ - П1 = 24, У1 = 19 П1 = 76

У 2 - П2 = 18, У2= 10 П2 = - 8

У1 - 0 = 19, УЗ= 100 П3 = 0

У2 - 0 = 10, У4= 24 П4 = 16

УЗ - 0 = 100,

У1 - П4 = 3,

У4 - П4 = 8.

2. Определить значения

К ij = У j - П i

При этом используются те индексы, на пересечении которых в соответствующих клетках не распределены объемы работ:

К11 = У1 - П1 = 19 - 76 = - 57

К12 = У2 - П1 = 10 - 76 = - 66

К14 = У4 - П1 = 24 - 76 = - 52

К21 = У1 - П2 = 19 + 8 = 27

К23 = УЗ - П2 = 100+ 8 = 108

К24 = У4 - П2 = 24 + 8 = 32

К34 = У4 – ПЗ = 24 - 0 = 24

К42 = У2 - П4 = 10 - 16 = - 6

К43 = УЗ - П4 = 100- 16 = 84

3. Определить значения Р i j = С ij - К ij и проверитьусловие

оптимальности, если все Р i j ≥ 0, то исходный план оптимален, Если некоторые Р < 0, то переходят к новому опорному плану.

Р11 = С11 - К11 = 70 + 57 = 127

Р12 = С12 - К12 = 38 + 66 = 104

Р14 = С14 - К14 = 92 + 52 = 144

Р21 = С21 - К21 = 58 + 27 = 31

Р23 = С23 - К23 = 56 - 108 = -52

Р24 = С24 - К24 = 72 - 32 = 40

Р34 = С34 - К34 = 30 - 24 = 6

Р42 = С42 - К42 = 36 + б = 42

Р43 = С43 - К43 = 121- 84 = 37

В нашем случае Р23 < 0 - переходим к новому опорному плану.

4. Построить новый опорный план, которому отвечает меньшее значение целевой функции. Для чего в опорный план вводится пере­менная Х ij, которой отвечает наименьшее отрицательное значение Р23. Вводя новую переменную одновременно изменяют другие пере­менные по меньшей мере в трех заполненных клетках (чтобы не на­рушить итоговые величины в строках и столбцах таблицы).

Для этого строят многоугольник, в котором одна из вершин находится в свободной клетке, для которой Р23 < 0 и имеет наименьшее значение, а остальные - в заполненных объемами работ (загружены)* при этом все углы многоугольника должны быть прямыми (многоу­гольник отмеченный пунктирной линией в таблице 7). В пределах клеток, лежащих в вершинах многоугольника Рис. 1 а, производят перераспределение объемов работ. Если для свободной клетки поста­вить знак +, а в следующей вершине -, затем + и т.д. поочередно изменяя знак, то в свободную клетку переносится меньшее из чисел стоящих в клетках с отрицательными знаками. В результате она иск­лючается из опорного базиса как базисная переменная. Одновременно необходимо установить равновесие по всему многоугольнику.

_ В2 В3 + В2 В3

			19 18
	1 100

+ а) _ б)

Рис. 1

Используя правило перераспределения объемов работ в пределах многоугольника, проводим распределение объемов работ Рис. 1,б. После чего сумма объемов работ по строкам и столбцам должна ос­таться без измения. В нашем примере многоугольник имеет прос­той вид, На практике при решении задач большой размерности мно­гоугольник может принимать самые замысловатые виды, образуя мно­жество пересекающихся линий. Проводя соответствующие изменения в исходном опорном плане, окончательно получим новый опорный план таблица 8.

Суммарные затраты на выполнение объемов работ (целевая функция) У = 24 ∙ 14 + 18 ∙ 19 + 56 ∙ 1 + 19 ∙ 23 + 10 ∙ 3 + 3 ∙ 7 + 8 ∙ 34 = 1494.

По сравнению с исходным планом (у - 1546) суммарные затраты на выполнение всех объемов работ уменьшились на 3,3 %.

Нахождением нового опорного плана заканчивается первое прибли­жение. Дальше начинается повторение операций с новой матрицей таблица 8.

Таблица 8

Комплект машин	Приведенные затраты Cij на выполнение единицы объема работ по объектам строительстваBJ	Годовая выработка машин,Пi
Bl	B2	B3	B4
А1
А2
А3
А4
Годовой объем работ,YJ

1. Составить и решить систему уравнений (для клеток с распреде­ленными объемами работ).

У j - П i = С ij

УЗ - П1 = 24: У2 - П2 = 18: УЗ - П2 = 56

У1 - ПЗ = 19: У2 - ПЗ = 10: У1 - П4 = 3

У4 – П4 = 8:

П1 = 32: П2 = 0: ПЗ = 8: П4 = 24:

У1 = 27: У2 = 18: УЗ = 56: У4 = 32.

2. Определить значения (для клеток с нераспределенными объемами работ).

К ij = У j - П i

К11 = У1 – П1 = 27 - 32 = -5

К12 = У2 - П1= 18 – 32 = - 14

К14 = У4 - П1 = 32 - 32 = 0

К21 = У1 - П2 = 27 – 0 = 27

К24 = У4 - П2 = 32 - 0 = 32

КЗЗ = УЗ - П3 = 56 – 8 = 48

К34 = У4 – ПЗ = 32 – 8 = 24

К42 = У2 - П4 = 18 – 24 = -6

К43 = УЗ - П4 = 56 – 24 = 32

3. Определить значения.

Р i j = С ij - К ij

Р11 = С11 - К11 = 70 + 5 = 75: Р12 = С12 - К12 = 38 + 14 = 52:

Р14 = С14 - К14 = 92- 0 = 92: Р21 = С21 - К21 = 58 - 27 = 31:

Р24 = С24 - К24 = 72 - 32 = 40: РЗЗ = СЗЗ - КЗЗ = 100- 48 = 52:

Р34 =С34 - К34 = 30 - 24 = 6: Р42 = С42 - К42 = 36 + 6 = 42:
Р43 = С43 - К43 = 121 - 32 = 89

В нашем случае Р i j > 0. т,е. опорный план оптимален, задача
решена и расстановка машин по объектам строительства соответсвует
ТАБЛИЦЕ 8.

Дата добавления: 2014-01-03