Рис. 41

Подзадача b

z = 5x + 6y ->max

10x + 7y £ 35, 5x + 14y<35, x>3, y>0.

Замечание. Отбрасываемая полоса выбирается из следующих соображений: мы намерены искать нужную нам точку среди целых точек, расположенных не слишком далеко от точки С, доставляющей максимум целевой функции.

Решая каждую из подзадач как задачу линейного программирования и пользуясь наглядно-геометрическим методом, получаем, что максимум целевой функции w = 5х + 6у в подзадаче а достигается в точке (7,

wc=2o (wj=15, hv=10),

а в подзадаче Ъ - в точке Е,

Ни точка G, ни точка £не являются целыми. Это вынуждает нас повторить наши предыдущие действия, но теперь уже по отношению к подзадачам а и Ъ.

Удаляя в подзадаче а вместе с точкой

все точки, попадающие в полосу

1<у<2,

мы переходим к подзадачам аа и ab (рис. 42). Подзадача аа

z= 5х + 6у > max 10х + 7у <35, 5х + 14у<35, 0<х£2, 0<у<1

Подзадача аЪ

z = 5х + 6у -* max 10х + 7у<35, 5х + 14д><35, 0<х<2, у>2.

Поступая аналогичным образом в подзадаче Ъ - удаляя вместе с точкой

все точки, попадающие в полосу

0<у<1,

мы переходим к подзадачам Ъа и ЪЪ (см. рис. 42). Подзадача Ъа

z = 5х + 6у -* max 10х + ly < 35, 5х + 14д><35, х>3, у = 0.

Подзадача ЪЪ

z = 5x + 6y ->max 10х + 7у <35, 5х + 14у<35, х>3, у>1

Вновь решая каждую из подзадач как задачу линейного программирования и пользуясь наглядно-геометрическим методом, получаем, что максимум целевой функции w = 5х + 6у в подзадаче аа достигается в целой точке /,

wf = 16, (wF = 10, wH = 6), в подзадаче аЪ - в точке К>

**=19, =15, wj =12), а в подзадаче Ъа - в точке Л,