5. Решение задачи способом двойного предпочтения

Очень удобен при решении задач вручную и может дать наилучшие результаты. В табл. 3.2.6 по строкам, начиная с 1-й, ищем клетку с наименьшим стоимостным элементом и помечаем звездочкой. Затем ищем клетки с минимальными стоимостными значениями по столбцам и также помечаем звездочками.

В клетки, имеющие две звездочки, помещаем максимально возможный объем работ. В клетки с одной звездочкой и в другие, не отмеченные, но с возможно меньшей стоимостью, - остальной объем работ.

Таблица 3.2.6

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, руб./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	**16/18	18
А2	32	**18/14	48	71	14
А3	19	36	**18/20	44	20
А4	**18/19	24/7	55	67	26
А5	69	28/12	36/3	*18/16	31
А6	41	56	*24/23	32	23
Vj тыс. м3	19	33	46	34	132

Суммарные затраты:

Y = 16×18 + 18×14 + 18×20 + 18×19 +24×7 +28×12+

+ 36×3 + 18×16 + 24×23=2694 тыс. руб.

6. Решение задачи способом аппроксимации Фогеля

В большинстве случаев дает опорный план, самый близкий к оптимальному. При данном способе ищутся разности в каждой строке и в каждом столбце матрицы между наименьшей стоимостью и ближайшей к ней по величине ( табл. 3.2.7).

Разности по строкам записываются справа в столбце разности, по столбцам – внизу в строке разностей.

Из всех разностей по строке и столбцу ищем максимальную (14) и в соответствующую клетку по строке с наименьшем стоимостным элементом

(А₂ В₂) ставим максимально возможный объем работ.

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

Таблица 3.2.7

Марка		Затраты				Пi, тыс.м3	Столбцы разностей
		В1	В2	В3	В4		1	2	3	4	5	6	7	8
А1		20/ 15	38/*	51/*	16/ 3	18	4	4	4	18	-	-	-	-
А2		32/*	18/14	48/*	71/*	14	14	-	-	-	-	-	-	-
А3		19/*	36/*	18/20	44/*	20	1	1	1	1	1	1	-	-
А4		18/ 4	24/19	55/3	67/*	26	6	6	6	6	6	6	6	37
А5		69/*	28/*	36/*	18/31	31	10	10	-	-	-	-	-	-
А6		41/*	56/*	24/23	32/*	23	8	8	8	17	17	-	-	-
Vj, т.м3		19	33	46	34	132
Строки разностей	1	1	6	6	2
	2	1	4	6	2
	3	1	12	6	16
	4	1	12	6	-
	5	1	12	6	-
	6	1	12	37	-
	7	18	24	-	-
	8	18	-	-	-

Суммарные затраты:

Y = 20×15 + 16×3 + 18×14 + 18×20 + 18×4 + 24×19 + 55×3 + 18×31 + 24×23 = 2763 тыс.р.

Из шести способов наилучший результат получен способами 2, 3, 4, 5, т.е. Y = 2694 тыс. руб. Соответственно в клетках, где распределены объемы работ – это и есть объекты, на которых должны работать бульдозеры в планируемом периоде.

После этого переходим ко второму этапу решения задачи.

Здесь производится проверка на оптимальность решения или продолжается последовательное улучшение опорного плана. Существует несколько способов улучшения опорного плана. Остановимся на распределительном методе.

В качестве исходного плана принимаем одну из матриц с наименьшими затратами. Например, табл. 3.2.5.

Таблица 3.2.5

Марка бульдозера	Затраты на выполнение единицы работы Сij по объектам Вj, руб./м3				Пi, тыс. м3
	В1	В2	В3	В4
А1	20	38	51	16/18 (1)	18
А2	32	18/14 (2)	48	71	14
А3	19	36	18/20 (3)	44	20
А4	18/19 (4)	24/7 (6)	55	67	26
А5	69	28/12 (8)	36/3 (9)	18/16 (5)	31
А6	41	56	24/23 (7)	32	23
Vj тыс. м3	19	33	46	34	132

Суммарные затраты: Y = 2694 тыс.руб.

1. Проверка на оптимальность решения начинается с решения системы уравнений вида

.

При этом нужно использовать индексы i,j для клеток, на пересечении которых распределены объемы работ.

V₄ - П₁ → 16; V₂ - П₄ → 24;

V₂ - П₂ → 18; V₂ - П₅ → 28;

V₃ - П₃ → 18; V₃ - П₅ → 36;

V₁ - П₄ → 18; V₄ - П₅ → 18; V₃ - П₆ → 24.

Для решения данной системы неизвестному значению, наиболее часто встречающемуся, дается произвольное значение, примем: П₅ = 0;

V₁ = 22; V₂=28; V₃= 36; V₄=18;

П₁ = 2; П₂ = 10; П₃ = 18; П₄ = 4;

П₅ = 0; П₆ = 12.

2. Далее определяются значения:

.

При этом используются индексы i,j, на пересечении которых не распределены объемы работ, а значения Vj и Пi берутся из найденных выше.

Z_1.1 =V₁ – П₁ = 22 - 2 = 20,

Z_1.2 =V₂ – П₁ = 28 - 2 = 26,

Z_1.3 =V₃ – П₁ = 36 - 2 = 34,

Z_2.1 =V₁ – П₂ = 22 - 10 = 12,

Z_2.3 =V₃ – П₂ = 36 - 10 = 26,

Z_2.4 =V₄ – П₂ = 18 - 10 = 8,

Z_3.1 =V₁ – П₃ = 22 - 18 = 4,

Z_3.2 =V₂ – П₃ = 28 - 18 = 10,

Z_3.4 =V₄ – П₃ = 18 - 18 = 0,

Z_4.3 =V₃ – П₄ = 36 - 4 = 32,

Z_4.4 =V₄ – П₄ = 18 - 4 = 14,

Z_5.1 =V₁ – П₅ = 22 - 0 = 22,

Z_6.1 =V₁ – П₆ = 22 - 12 = 10,

Z_6.2 =V₂ – П₆ = 28 - 12 = 16,

Z_6.4 =V₄ – П₆ = 18 - 12 = 6.

3. Определяем значения δij по формуле

,

условия индексов i и j определяют по шагу 2, Сij – берётся из табл. 3.2.8,

Zij – по выше найденному.

δ_1.1 = С_1.1 - Z_1.1 = 20 - 20 = 0;

δ_1.2 = С_1.2 - Z_1.2 = 38 – 26 = 12;

δ_1.3 = С_1.3 - Z_1.3 = 51 – 34 = 17;

δ_2.1 = С_2.1 – Z_2.1 = 32 – 12 = 20;

δ_2.3 = С_2.3 – Z_2.3 = 48 – 26 = 22;

δ_2.4 = С_2.4 – Z_2.4 = 71 – 8 = 63;

δ_3.1 = С_3.1 – Z_3.1 = 19 – 4 = 15;

δ_3.2 = С_3.2 – Z_3.2 = 36 – 10 = 26;

δ_3.4 = С_3.4 – Z_3.4 = 44 – 0 = 44;

δ_4.3 = С_4.3 – Z_4.3 = 55 – 32 = 23;

δ_4.4 = С_4.4 – Z_4.4 = 76 – 14 = 62;

δ_5.1 = С_5.1 – Z_5.1 = 69 – 22 = 47;

δ_6.1 = С_6.1 – Z_6.1 = 41 – 10 = 31;

δ_6.2 = С_6.2 – Z_6.2 = 56 – 16 = 40;

δ_6.4 = С_6.4 – Z_6.4 = 32 – 6 = 26.

Если в процессе решения δij ≥0, то исходный план оптимален, Если δij<0 хотя бы в одном выражении, то данный опорный план подлежит последовательному улучшению. В этом случае ведется перестановка объемов работ в следующей последовательности:

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

Для этого строят многоугольник, в котором одна из вершин находится в свободной клетке, для которой Р ij < 0 и имеет наименьшее значение, а остальные – в заполненных объемами работ (загружены)* при этом все углы многоугольника должны быть прямыми (многоугольник, отмеченный пунктирной линией в рассматриваемой таблице).

Например, в пределах клеток, лежащих в вершинах многоугольника (рис. 3.2.1, а), производят перераспределение объемов работ. Если для свободной клетки поставить знак + , а в следующей вершине - , затем + и т.д., поочередно изменяя знак, то в свободную клетку переносится меньшее из чисел, стоящих в клетках с отрицательными знаками. В результате она исключается из опорного базиса как базисная переменная.

Одновременно необходимо установить равновесие по всему многоугольнику.

_ В2 В3 + В2 В3

20 1 8	56		1 9 18	1 56
2 10	1 100		3 10	100

+ а) _ б)

Рис. 3.2.1. Перераспределение объемов работ

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