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

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

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= 44*100+41*50+42*1250+43*2000+26*550+

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

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

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

Таблица 12

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

№		1	2	3	4	5(ф)
		144	141	142	144	122
1	100	44 100	41 - 50	42 1250	46 + 2	0 22
2	101	43 2000	40 0	40 -1	0 -43	0 -21
3	1 15	28 -1	26 550	27 0 0	29 0	0 -7
5	1 22	18 -4	+ 19 1300	17 -3	- 22 304	0 896
6	9 8	43 -3	40 -3	44 800	45 -1	0 -24

План не оптимален, так как в клетке (1;4) =2.

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

+(100*1400+101*2000+115*550+122*2500+98*800)=225838

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

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

Таблица 13

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

№		1	2	3	4	5(ф)
		144	143	142	146	124
1	100	44 100	41 -2	42 - 1250	46 + 50	0 -24
2	101	43 2000	40 -2	40 -1	0 -45	0 -23
3	117	28 1	- 26 550	27 + 2	29 0	0 -7
5	124	18 -2	+ 19 1350	17 -1 -1	- 22 254	0 896
6	9 8	43 -3	40 -5	44 800	45 -3	0 -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=225938.

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

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

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

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

Таблица 14

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

№		1	2	3	4	5(ф)
		144	141	142	146	122
1	100	44 100	41 0	42 996	46 304	0 -22
2	101	43 2000	40 0	40 -1	0 -45	0 -21
3	115	28 -1	26 296	27 254	29 -2	0 -7
5	122	18 -4	19 1604	17 -3	22 -2	0 896
6	9 8	43 -3	40 -3	44 800	45 -3	0 -24

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

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

1. 100+996+304=1400

2. 2000 =2000

3. 296+254 =550

5. 1604+896 =2500

6. 800 =800

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

1. 100+2000 =2100

2. 296+1604 =1900

3. 996+254+800=2050

4. 304 =304

5. 896 =896

; 2*254=508; Z₃=225938+508=226446

Z_k=44*100+42*996+46*304+43*2000+26*296+27*254+19*1604+44*800=226446.

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

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

Формализованное представление оптимального решения задачи приведено в табл.15. Это не окончательное решение, т.к. в нем не учтены дополнительные условия и присутствует фиктивный столбец.

Таблица 15

Формализованное представление оптимального решения задачи

№	1	2	3	4	5(ф)
1	44 100	41	42 996	46 304	0
2	43 2000	40	40	0	0
3	28	26 296	27 254	29	0
5	18	19 1604	17	22	0 896
6	43	40	44 800	45	0

Формирование окончательного решения задачи

В начале учтем первое дополнительное условие.

, для этого восстановим значения величин А₃ и В₃, увеличим на 550 переменную . В результате получим табл.16.

Таблица 16

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

j i	1	2	3	4	5(ф)	Ai
1	44 100	41	42 996	46 304	0	1400
2	43 2000	40	40	0	0	2000
3	28	26 296	27 804	29	0	1100
5	18	19 1604	17	22	0 896	2500
6	43	40	44 800	45	0	800
Bj	2100	1900	2600	304	896	7800 7800

Теперь учтем второе дополнительное условие.

. Для этого разблокируем оценку с₂₄ и придадим ей первоначальное значение с₂₄=45; восстановим значения А₂ и В₄ и внесем в клетку (2,4) переменную х₂₄=300 (табл.17).

Таблица 17

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

i j	1	2	3	4	5(ф)	Ai
1	44 100	41	42 996	46 304	0	1400
2	43 2000	40	40	45 300	0	2300
3	28	26 296	27 804	29	0	1100
5	18	19 1604	17	22	0 896	2500
6	43	40	44 800	45	0	800
Bj	2100	1900	2600	604	896	8100 8100

Учет 3-го дополнительного ограничения .

Для этого дополним предыдущую таблицу выброшенной ранее четвертой строкой, в которой запишем указанное значение переменной х₄₄. Кроме того восстановим первоначальные значения величин А₄ и В₄. В результате получим табл.18.

Таблица 18

Решение задачи с учетом 3-го дополнительного условия

i j	1	2	3	4	5(ф)	Ai
1	44 100	41	42 996	46 304	0	1400
2	43 2000	40	40	45 300	0	2300
3	28	26 296	27 804	29	0	1100
4	67	65	66	69 950	0	950
5	18	19 1604	17	22	0 896	2500
6	43	40	44 800	45	0	800
Bj	2100	1900	2600	1554	896	9050 9050

4-е дополнительное ограничение - выполняется автоматически.

Отметим, что учет дополнительных ограничений не нарушает граничных условий. Представленное в табл.18 решение нельзя считать окончательным, т.к. в таблице содержится 5-й фиктивный столбец, введенный для сбалансированности задачи. Введение фиктивного столбца соответствует избытку произведенных кормов гороха. Учитывая это и вычеркивая из последней таблицы 5-ый фиктивный столбец, получим окончательное решение, представленное в табл.19.

Таблица 19

Окончательное решение задачи

№	Культуры	Урожайности культур по участкам (ц.к.е./га)				Площадь
п/п		I	II	III	IV	посева, га
1	Кукуруза на силос	44 100	41	42 996	46 304	1400
2	Одн.травы на з/к	43 2000	40	40	45 300	2300
3	Одн. травы на сено	28	26 296	27 804	29	1100
4	Картофель	67	65	66	69 950	950
5	Горох	18	19 1604	17	22	1604 (896)
6	Мн. травы на сено	43	40	44 800	45	800
	Площади участков, га	2100	1900	2600	1554	8154 (896) 8154

Подсчитаем значение целевой функции для ответа:

Z=44*100+42*996+46*304+43*2000+45*300+26*296+27*804+69*950+19*1604+44*800=320346.

Ответ задачи: максимальный сбор кормов будет равен 320346 ц к.е. при следующем распределении кормовых культур по участкам:

кукуруза на силос 100 га на 1 участке, 996 га на 3 участке и 304 га на 4 участке;

однолетние травы на зеленый корм 2000 га на 1 участке и 300 га на 4 участке;

однолетние травы на сено 296 га на 2 участке, 804 га на 3 участке;

картофель 950 га на 4 участке;

горох 1604 га на 2 участке;

многолетние травы на сено 800 га на 3 участке.

Задачи для лабораторных и самостоятельных работ

Задача № 1

Распределить посевы кормовых культур по участкам земли различного плодородия таким образом, чтобы сбор корма (в кормовых единицах) был максимальным.

Таблица 20