13.1. Линейное программирование

Исторически понятие «программа» определяло времен­ную последовательность взаимосвязанных действий, выраженных количественно. Теперь под программой часто понимают серию команд, предписанных человеку или машине и определяющих последовательность действий, направленных на достижение конечной цели.

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

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

Производство Стоимость Потребление

Производитель1, завод А 3 изделия	Транспортировки 3 долл. на изделие
	1 долл. на изделие			Потребитель М 1 изделие
	2 долл. на изделие			Потребитель N 2 изделия
	2 долл. на изделие
	1 долл. на изделие			Потребитель Р 4 изделия
Производитель1, завод В 4 изделия	3долл. на изделие

Рис. 13.1. Простейшая задача линейного программирования.

Предположим, что некая фирма имеет два завода. Один из них (А) производит за единицу времени три изделия, а другой (В) - четыре. Есть три потребителя этих изделий. Один из них, расположенный в пункте М, получает за единицу времени одно изделие, другой, находящийся в пункте N, - два изделия, а третий, находящийся в пункте Р, - четыре изделия.

Если расходы на перевозку одного изделия составляют: из пункта А в М - 3долл., из А в N - 2 долл., из А в Р - 1 долл., из В в М - 1 долл., из В в N - 2 долл., из В в Р - 3 долл. (рис. 13.1), то при некоей схеме распределения изделий по маршрутам транспортные расходы будут минимальны .

Можно, например, доставлять по одному изделию из А в N, М и Р, еще одно изделие - из В в N и, наконец, три изделия - из В в Р. Тогда транспортные расходы составят: (3 х 1) + (2 х 1) + (1 х 1) + (2 х 1) + + (3 х 3) = 3 + 2 + 1 + 2 + 9 = 17 долл.

Однако большие преимущества представит схема транспортировки, когда три изделия доставляют из А в Р, а остальные из В. Тогда расходы составят: (1x3 + +(1 х 1) + (2 х 2) + (3 х 1) = 3+1 +4 + 3 = 11 долл. Но будет ли этот вариант лучшим?

В нашем примере количество вариантов невелико и ответ легко получить их перебором. Однако при нескольких сотнях адресатов и изделий на определение лучшей из альтернатив потребуется недопустимо много времени. Действительно, в некоторых случаях их число будет столь велико, что пересчет всех возможных сочетаний немыслим. Электронно-вычислительные машины методами линейного программирования могут решать подобные, так называемые транспортные задачи, включающие до 3200 уравнений и 600 тыс. переменных. Линейное программирование позволяет найти лучший или один из лучших вариантов решения без обсчета по отдельности каждого из возможных вариантов.

Прилагательное «линейное» в названии «линейное про­граммирование» определяет характер соотношения между видами деятельности и ресурсами. Так, в нашем примере число изделий, направленных из А, должно быть больше нуля или равно нулю или меньше трех или равно трем. То же соотношение справедливо и для В. Математически эти уравнения выражаются линейными неравенствами. Поскольку стоимость транспортировки п аналогичных изделий в п раз больше стоимости транспортировки одного изделия, то эти равенства и неравенства будут линейными.

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

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

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

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

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

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