91. Л. В. Канторович: разработка теории линейного программирования.

За разработку метода линейного программирования Леонид Вита­льевич Канторович (1912–1986) был (совместно с американским эко­номистом Т. Купмансом) удостоен Нобелевской премии в области экономики (1975 г.).

Заслуга Канторовича состоит в том, что он предложил математичес­кий метод поиска оптимального варианта распределения ресурсов. Решая конкретную задачу достижения наибольшей производительности при загрузке оборудования предприятия, производящего фанеру, уче­ный разработал метод, получивший название метода линейного про­граммирования. Тем самым был открыт новый раздел в математике, по­лучивший распространение в экономической практике, способствовав­ший развитию и использованию электронно-вычислительной техники.

Для решения задачи на оптимум Канторович использовал метод пос­ледовательных приближений, последовательного составления вариантов с выбором наилучшего в соответствии с условиями задачи. Линейное программирование – это программное распределение ограниченных ре­сурсов наилучшим способом в соответствии с поставленными целями.

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

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

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

Метод линейного программирования позволяет найти оптималь­ное решение. Линейным оно называется потому, что основывается на решении линейных уравнений. Неизвестные в них только первой сте­пени; ни одно неизвестное не перемножается на другое неизвестное. Такие уравнения отражают зависимости, которые могут быть изобра­жены на графике прямыми линиями.

На рис. 20 приведена транспортная задача: требуется определить план перевозок при минимальных затратах.

Рис.20. Транспортная задача 151

В данном случае имеются четыре потребителя (квадратики) и три поставщика (кружочки). Линии, соединяющие пункты, изображают маршруты поставок (транспортную сеть). Цифры внутри квадратиков показывают объемы спроса (со знаком минус), внутри кружочков – размеры предложения (со знаком плюс).

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

Для любой задачи линейного программирования существует со­пряженная ей, двойственная задача. Если прямая задача заключается в минимизации целевой функции, то двойственная – в максими­зации.

При непосредственном участии Канторовича и его ближайших коллег – В. В. Новожилова (автора идеи продуктово-трудового ба­ланса) и В. С. Немчинова (обосновавшего глобальный критерий функционирования экономики) – формировалась отечественная эко­номико-математическая школа.

Усилиями экономистов-математиков была разработана система оптимального функционирования экономики (СОФЭ); строились модели эффективного распределения и оценки ресурсов.