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	1	2	3	4	5	Ai
1	44	41	42	46	0	1400
2	43	40	40	0	0	2000
3	28	26	27	29	0	550
5	18	19	17	22	0	2500
6	43	40	44	45	0	800
Bj	2100	1900	2050	304	896	7250 7250

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

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

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

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	1	2	3	4	5	Аi
1	44 100	41 50	42 1250	46	0	1400 1300 50	2	2	2	2	1	41*
2	43 2000	40	40	0	0	2000	3*
3	28	26 550	27	29	0	550	1	1	2	2	1	26*		26*
5	18	19 1300	17	22 304	0 896	2500 2196 896	3	3*	1	1	2	19		19
6	43	40	44	45	0	800	1	1	*1
Bj	2100 100	1900 1850 1300	2050 1250	304	896	7250 7250
	1	1	2	1	0
	1	1	2	1	0
	1	1	2*		0
	1*	1	2		0
		15	15*		0
		15
		7

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

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

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

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

№		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	115	28 -1	26 550	27 0	29 0	0 -7
5	122	18 -4	19 - 1300	17 -3	22 - 304	0 896
6	98	43 -3	40 -3	44 800	45 -1	0 -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-м шаге решение задачи

№		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	22 - 254	0 896
6	98	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=221338.

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

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

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

х_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	98	43 -3	40 -3	44 800	45 -3	0

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

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

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