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

Авиакомпания, которая определяет маршруты самолетов; организация, занимающаяся материально-техническим снабжением армии; международная корпорация, производящая прохладительные напитки; NASA, разрабатывающая космические программы; крупная телефонная компания, осуществляющая прокладку линий; телекоммуникационная компания, которой необходимо оптимальным образом расположить сетевое оборудование, — всем им требуется обработка огромных объемов данных, и все они имеют очень четкие цели.

Линейное программирование также связано со статистикой, теорией принятия решений и теорией игр.

Изначально линейное программирование не располагало мощными средствами вычислений, но со временем рост возможностей компьютеров способствовал бурному развитию этой дисциплины. Подсчитано, что современные организации тратят от 50 до 90 % вычислительных мощностей на решение задач линейного программирования. Среди тех, кто внес важный вклад в развитие линейного программирования, стоит выделить Джона фон Неймана, Леонида Канторовича, Тьяллинга Купманса, Джорджа Данцига, а также Нарендру Кармаркара — блестящего исследователя, работавшего в американской телефонной компании AT&T Bell, который изобрел радикально новый алгоритм решения задач линейного программирования.

Пионер линейного программирования математик Джон фон Нейман общается со студентами Принстонского университета. 1947 год.

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

Рассмотрим компанию, которая производит два типа напитков А и В, в которых сочетаются два ингредиента а и Ь. Прибыль от продажи единицы напитка А составляет 6 евро, от единицы напитка В — 5 евро. В рассматриваемый период на складе компании находится 1000 литров а и 3000 литров Ь. При производстве напитка А нужно смешать 0,3 литра а и 0,5 литра Ь, при производстве В — 0,3 литра a и 0,7 литра Ь. Как получить максимальную прибыль?

* * *

* * *

Условия задачи сведены в следующую таблицу.

Алгоритм решения подобных задач в общем виде выглядит так:

1. Какими ресурсами мы располагаем?

2. Каков объем каждого ресурса?

3. Какие продукты нужно изготовить?

4. Сколько ресурсов требуется для изготовления каждого продукта?

5. Каковы неизвестные величины?

6. По какой формуле рассчитывается прибыль?

Обозначим за х объем выпуска напитка А, за у — объем выпуска напитка В, для изготовления которых нам потребуются ресурсы а и Ь. Формула расчета прибыли, которую нужно максимизировать, такова:

6х + 5у.

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

x >= 0,

у >= 0,

0,5x + 0,3у =< 1000,

0,5x + 0,7у =< 3000.

Мы составили математическую модель задачи, и теперь необходимо найти максимальное значение выражения 6х + 5у для пары значений (х, у), которые будут удовлетворять четырем вышеперечисленным ограничениям. Построим область допустимых решений, которую образуют все точки (х, у) в декартовой системе координат, удовлетворяющие условиям задачи.

Графическое представление области допустимых решений, имеющей форму многоугольника.

Область допустимых решений имеет форму многоугольника. Именно в вершинах этого многоугольника расположены значения (х, у), обеспечивающие максимальную прибыль, которая рассчитывается по формуле 6х + 5у. Чтобы найти максимально возможный объем прибыли, нужно выполнить следующие действия.

1. Определить координаты вершин области допустимых решений.

2. Рассчитать прибыль в каждой из вершин области допустимых решений.

3. Выбрать вершину, для которой прибыль будет максимальной.

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

* * *

РЕШЕНИЯ ЗАДАЧ

Цепь в прямоугольнике :

Цепь на квадратной сетке:

Задача о четырех окружностях :

Магическая гексаграмма: чтобы получить одно из возможных решений, нужно расположить числа в рядах, сверху вниз, следующим образом: 10; 4, 7, 9, 6; 8, 5; 1, 11, 12, 2; 3.

* * *

Здесь снова появляется теория графов: эта задача может быть решена с помощью симплекс-метода, разработанного Джорджем Данцигом.

Представьте область допустимых решений в виде графа (это может быть многоугольник на плоскости, многогранник в пространстве либо же некий плоский граф в общем виде).

Плоский граф, соответствующий области допустимых решений, которая представляет собой многогранник.

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

Поиск быстрых алгоритмов для решения подобных задач всегда имел особую важность. Работы Кармаркара позволяют, например, найти оптимальные решения на 50—100 % быстрее, чем традиционный симплекс-метод.