8 часов. Каждый стул приносит 1$ прибыли, а каждый стол - 3$. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 футами древесины и 400 часами рабочего времени и хочет получить максимальную прибыль?

Обозначив искомое количество стульев и столов через х и у соответственно, запишем условия задачи в виде формул. Имеем

z = jc + >>-> max Зх + 7>><420, 2х + 8д>£400, х>0, у>0.

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

Графическое решение задачи (рис. 39), казалось бы, подтверждает складывающееся впечатление,

X = 56, у =36, Zmzx = 164$.

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

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

Ответ отрицательный: в общем случае так поступать нельзя - мы можем либо вылезти за рамки ограничений, либо (если мы будем с округлением более осторожны) полученный целочисленный набор не будет оптимальным.

Условие целочисленное неизвестных заметно усложняет поиски оптимального решения и требует иных, более изощренных математических методов его поиска, тем более трудоемких, чем значительней число величин, подлежащих определению. Наиболее известными являются метод отсечений и метод ветвей и границ (см. [5], [7], [8]).

Ограничившись двумя неизвестными, покажем на примере, как можно решить задачу целочисленного программирования методом ветвей и границ.

Задача. Найти целые значения неизвестных х и у, обеспечивающие выполнение предъявленных ниже условий

Начнем с того, что решим поставленную задачу, опустив ограниче-

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

z = 5x+6y > max

10х + 7у<35, 5х + 14д> <35, х>0, у>0.

х, yGZ.

(1) Рис. 40

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

Ясно, что множество точек, абсцисса х которых удовлетворяет неравенству

2 <х< 3,

не содержит целочисленных решений исходной задачи, а значит, и искомой точки. Отбрасывая это множество (вместе с точкой С, доставляющей максимум целевой функции), мы заменяем четырехугольник ОАСВ на четырехугольник OFGB и треугольник DAE (рис. 41), а исходную задачу на две подзадачи а и Ь, отличающиеся одна от другой дополнительными ограничениями на абсциссу. Подзадача а

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