Определение опорного решения методом аппроксимации

Целевая функция:

Ограничения:

а) по строкам:

б) по столбцам:

Балансовое условие:

Условие неотрицательности переменных:

Таблица 8

Табличное представление исходных данных задачи

№ п/п	Культуры	Урожайности культур по участкам (ц.к.е./га)	Площадь посева, га
I	II	III	IV
	Кукуруза на силос	X₁₁	X₁₂	X₁₃	X₁₄
	Одн.травы на з/к	X₂₁	X₂₂	X₂₃	X₂₄
	Одн. травы на сено	X₃₁	X₃₂	X₃₃	X₃₄
	Картофель	X₄₁	X₄₂	X₄₃	X₄₄
	Горох	18 X₅₁	X₅₂	X₅₃	X₅₄
	Мн. травы на сено	X₆₁	X₆₂	X₆₃	X₆₄
	Площади участков, га

Проверка сбалансированности задачи

что не равно , задача несбалансирована, причем . Чтобы привести задачу к сбалансированному виду, вводим фиктивный участок с площадью, равной 896. Чтобы значение целевой функции не изменилось, урожайность по фиктивному участку примем равными нулю С_i₅=0, i=1,2,3,4,5,6. В результате исходная таблица примет вид табл.9.

Таблица 9

Приведение задачи к сбалансированному виду с помощью фиктивных объектов (строки или столбца)

№ п/п	Культуры	Урожайности культур по участкам (ц.к.е./га)	Площадь посева, га
I	II	III	IV	V(ф)
	Кукуруза на силос	X₁₁	X₁₂	X₁₃	X₁₄	X₁₅
	Одн.травы на з/к	X₂₁	X₂₂	X₂₃	X₂₄	X₂₅
	Одн. травы на сено	X₃₁	X₃₂	X₃₃	X₃₄	X₃₅
	Картофель	X₄₁	X₄₂	X₄₃	X₄₄	X₄₅
	Горох	18 X₅₁	X₅₂	X₅₃	X₅₄	X₅₅
	Мн. травы на сено	X₆₁	X₆₂	X₆₃	X₆₄	X₆₅
	Площади участков, га

Учет дополнительных ограничений

1) дополнительное ограничение типа

, для выполнения этого условия и должны быть уменьшены на 550. Определяем измененные значения A₃и B₃:

A₃^/=A₃-550=1100-550=550

B₃^/=B₃-550=2600-550=2050

2) дополнительное ограничение типа

определяем измененные значения A₂ и B₄

A₂^/=A₂-300=2300-300=2000

B₄^/=B₄-300=1554-300=1254;

дополнительно изменяем оценку С₂₄, проводим блокировку оценки, придаем ей невыгодное значение, при решении на максимум – минимальное значение, т.е. С₂₄=0.

, аналогично, уменьшаем A₄ и B₄ на 990, тогда

A₄^/=950-950=0, соответствующая строка 4 вычеркивается из исходной матрицы, а нумерация строк сохраняется при дальнейшем решении задачи.

B₄^//=1254-950=304.

3) дополнительное ограничение типа

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

В результате учета дополнительных условий получим следующую таблицу (табл.10).

Таблица 10

Табличное представление исходных данных задачи после учета дополнительных условий и требования сбалансированности

j i						A_i





B_j

Граничные условия

Развернутая запись

а) по строкам исходной матрицы:

X₁₁+X₁₂+X₁₃+X₁₄+X₁₅=1400

X₂₁+X₂₂+X₂₃+X₂₄+X₂₅=2000

X₃₁+X₃₂+X₃₃+X₃₄+X₃₅=550

X₅₁+X₅₂+X₅₃+X₅₄+X₅₅=2500

X₆₁+X₆₂+X₆₃+X₆₄+X₆₅=800

б) по столбцам исходной матрицы:

X₁₁+X₂₁+X₃₁+X₅₁+X₆₁=2100

X₁₂+X₂₂+X₃₂+X₅₂+X₆₂=1900

X₁₃+X₂₃+X₃₃+X₅₃+X₆₃=2050

X₁₄+X₂₄+X₃₄+X₅₄+X₆₄=304

X₁₅+X₂₅+X₃₅+X₅₅+X₆₅=896

в) балансовое условие: , после проведенных преобразований оно автоматически выполняется.

г) условие неотрицательности переменных:

Целевая функция задачи:

Необходимо найти такой план распределения посевов кормовых культур по участкам различного плодородия, т.е. такие значения величин (i=1,2,3,5,6; j=1,2,3,4,5), чтобы сбор кормов был максимальным.

Таблица 11

Получение опорного решения методом аппроксимации на максимум

j i

А_i

1300 50

41^*

3^*

26^*

2196 896

3^*

^*1

B_j

2^*

1^*

15^*

Проверка опорного решения на выполнение граничных условий.

а) по строкам:

1. 100+50+1250=1400

2. 2000 =2000

3. 550 =550

5. 1300+304+896=2500

6. 800 =800

б) по столбцам:

1. 100+2000 =2100

2. 50+550+1300=1900

3. 1250+800 =2050

4. 304 =304

5. 896 =896

Проверка на число занятых клеток.

;9=9, т.е. решение верное и невырожденное.

Вычисление значения целевой функции.

Z_k= 44*100+41*50+42*1250+43*200+26*550+

+19*1300+22*304+0*896+44*800=225870

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

Вычислим потенциалы. За первый потенциал возьмем =100, все остальные потенциалы вычисляем по формуле . Для свободных клеток вычисляем оценки . Результаты расчетов заносим в табл.12.

Таблица 12

Потенциалы и оценки для опорного решения задачи

№					5(ф)

1		-		+
2			-1	-43	-21
3	-1				-7
5	18 -4	-	-3	-
6	-3	-3		-1	-24

Z_k=144*2100+141*1900+142*2050+144*304+122*896-

-100*1400+101*2000+115*550+122*2500+98*800=2258358

Улучшение опорного плана

Строим замкнутый прямоугольный цикл с началом в свободной клетке с наибольшей оценкой (испытуемая клетка). Клетка (1,4) с оценкой =2 не удовлетворяет условию оптимальности. Для нее строим цикл в табл.12. Проставляем знаки «+» и «-», начиная с испытуемой клетки, ищем наименьшее значение х_ij среди отрицательных вершин. В данном случае х_min=50. Это тот ресурс, который перемещается по циклу и прибавляется или вычитается в зависимости от проставленных знаков в вершинах цикла. Таким образом, получаем новые значения переменных х_ij, т.е. новое решение задачи. Результаты описанных действий сведем в табл.13.

Таблица 13

Улучшенное на 2-м шаге решение задачи

№					5(ф)

1		-2	-	+	-24
2		-2	-1	-45	-23
3		-	+		-7
5	-2	+	-1	-
6	-3	-5		-3	-26

Полученное решение необходимо проверить на выполнение граничных условий.

а) по строкам:

1. 100+1250+50 =1400

2. 2000 =2000

3. 550 =550

5. 1350+254+896=2500

6. 800 =800

б) по столбцам:

1. 100+2000=2100

2. 550+1350=1900

3. 1250+800=2050

4. 50+254 =304

5.896 =896

Значение целевой функции определяется по формуле:

(для задачи на максимизацию должно выполняться условие: ).

2*50=100, где оценка испытуемой клетки, -перемещаемая поставка.

Z₂=225838+100=225938

Дополнительно для контроля значение целевой функции рассчитывается по формуле: 44*100+42*1250+46*50+43*2000+26*550+

+19*1350+22*254+44*800=221338.

Проверка на оптимальность

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

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

х_min=254 – ресурс, который будем перемещать по циклу в соответствии с проставленными знаками, в результате получим новые значения переменных, т.е. новое решение, которое представим в табл.14.

Таблица 14

Улучшенное на 3-м шаге решение задачи

№					5(ф)

1					-22
2			-1	-45	-21
3	-1			-2	-7
5	-4		-3	-2
6	-3	-3		-3