Лучший вариант

13

3. Литовченко

Лучший вариант

Представьте себе, что вы — директор школьи-интерната, и вам нужно составить меню для столовой на неделю. Детальное составление меню, конечно, дело повара, но вот проследить за тем, что денег будет истрачно не слишком много, нужно вам.

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

Рассмотрим такой пример. Пусть меню уже почти полностью составлено, и вам нужно проследить только за тем, чтобы в нем оказалось достаточно витаминов А и С, причем на складе есть вшни и абрикосы. Один таблица с двумя фруктами А (гв1 кг) и С (гв1 кг)

Вишни 3 150
Абрикосы 24 75

$$\begin{cases} 0,003x + 0,024y \geq 6, \\ 0,15x + 0,075y \geq 75, \\ x \geq 0, y \geq 0, \end{cases}$$

и $z = 0,25x + 0,3y$ было бы минимальным. На плоскости $xOy$ легко указыть множество точек $M$, удовлетворяющих системе (рис. 1). Его называют многоугольником решений системы. Ясно, что прямые $z = 0,25x + 0,3y$ при различных $z$ параллельных одному и тому же направлению, причем прирост $z$ они удаляются от начала координат. Поэтому нам нужно найти ту из прямых этого направления, которая имеет с многоугольником $M$ общую точку и близке всего к началу координат. Легко сообщить, что такая прямая не должна пересекать $M$ по внутренним точкам — тогда бы она не была самой «низкой» (рис. 2). Следовательно, она должна проходить через одну из вершин многоугольника. Но тогда эта точка — вершина $C$. Итак, нужно купить 400 кг вшен и 200 кг абрикосов — лучший вариант!

Задание, подобные разобранной, называются задачи линейного программирования. В них требуется найти прямую (в трехмерном пространстве — плоскость, в многомерном — так называемую гиперплоскость), принадлежшую пучку параллельных прямых (плоскостей, гиперплоскостей), которая пересекается с некоторым многоугольником (многоугольником) и находится близке всего к началу координат. Можно дать и чисто алгебраическую форму-

14

Рис. 1.

нужно вырастить песцов и лисиц, чтобы средняя стоимость одной шкурики была минимальная, если стоимость вырашивания одной лисицы — 45 руб., а одного песца — 25 руб.?

Решение. Пусть $x$ — число вырашиваемых лисицы, а $y$ — песцов. Тогда

$$\begin{cases} 4x + 5y \leq 80000 \\ \frac{1}{2}x + y \leq 10000 \\ x \geq 3000 \\ y \geq 6000. \end{cases}$$

Средняя стоимость одной шкурики

$$z = \frac{45x + 25y}{x + y}.$$

Мулировку: имеется система линейных неравенств

$$\begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n \geq b_1, \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n \geq b_2, \\ \dots \\ a_{k1}x_1 + a_{k2}x_2 + \dots + a_{kn}x_n \geq b_k \end{cases}$$

и линейная функция $z = c_1x_1 + \dots + c_nx_n$. Нужно найти такое решение этой системы, для которого значение функции $z$ минимально. О линейном программировании в «Кванте» было уже много статей (1971 — № 3, с. 1 и № 4, с. 1, 1974 — № 7, с. 13, 1975 — № 10, с. 17, 1976 — № 7, с. 2, 1977 — № 8, с. 29).

Решим еще одну задачу: зверосовозы вырашивает песцов и лисиц; он имеет 10 000 клеток, причем в одной клетке могут жить две лисицы или один песец; по плану нужно вырасти не менее 3000 лисиц и не менее 6000 песцов; за сутки одной лисице скармливают 4 кормовых единиц, а песцу — 5 единиц; всего за сутки разрешается истранить не больше 80 000 кормовых единиц; сколько

15

Рис. 3.

стояние значения на прямых, проходящих через начало координат. Нам нужно найти ту из этих прямых, которая пересекает многоугольник F и на которой значение функции z минимально. Так же, как и выше, ясно, что эта пряма не должна содержать внутренних точек многоугольника F. Поэтому достаточно сравнить между собой прямы OA и OB. ОТВЕТ: $x=3000$, а $y=8500$.

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

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

В заключение — упражнение для читателей:

Два судна должны перевести грузы в соответствии с таблицей 2.

Известно, что первое судно может сделать не больше 5 рейсов, а второе — не больше 9. Составить план перевозок, который обеспечивает бы а) максимальную приближение;
б) наименьшие затраты на перевозку одной тонны груза.

Поправки

В № 3 «Кваита» за 1978 г. на с. 11 в восемой строке сверху влевой колонке следует читать «M. П. Бронштейном».
В № 11 «Кваита» за 1977 г. на с. 27 во второй строке снизу в правой колонке следует читать «В 1928 году».