Экономико-математические методы (Абчук)

Условия задачи (ограничения) могут быть заданы также в виде неравенств. В этих случаях можно привести систему линей­ ных ограничений к виду (3.1), вводя в каждое линейное ограниче­ ние дополнительные неотрицательные неизвестные:

Целевая установка оптимизации заключается в том, чтобы свести ожидаемые при решении данной задачи издержки предпри­ ятий к минимуму.

Общая математическая формулировка задачи соответствует условиям (3.1) и (3.2).

Первая строка системы уравнений (3.1)

а,.х1 + a,jc, + ... + а,х + ... + а, х =ЪЛ

И 1 12 2 lj ) In n 1

в данном примере означает следующее:

аи - количество единиц ресурсов вида 1 на первом пред­ приятии;

а,2 - количество единиц ресурсов вида 1 на втором предпри­ ятии и т.п.;

Ь, - общий ресурс ресурсов вида 1 (для всех предприятий); хх, х2 и т.д. - искомое количество предприятий типов 1,2 и т.д. Вторая строка упомянутой системы уравнений содержит ана­ логичные величины для ресурсов вида 2 и т.д. Функция цели соот­ ветствует формуле (3.2). Требуется обратить в минимум величину

где с. - показатель, характеризующий издержки предприятий. Пусть m - общее число различных видов ресурсов, которы­

ми располагает собственник, a n - число типов предприятий, меж­ ду которыми эти ресурсы должны быть распределены. При этом известно, какое количество однородных ресурсов различного вида (i = 1,2... m) может быть реализовано на каждом из предприятий данного типа (j = 1, 2... п), а также общее количество ресурсов данного вида (Ь). Известно также относительное значение издер­ жек на каждом из предприятий (с).

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

Собственник располагает четырьмя видами ресурсов (т = 4). Это, например, денежные средства, производственные помещения, оборудование, сырье. Ресурсы необходимо распределить между шестью предприятиями (п = 6). Предприятия различаются по эко­ номическим условиям деятельности: месту расположения, систе­ ме налогообложения, стоимости энергии, оплате труда и т.д., в свя­ зи с чем имеют разные издержки производства. Относительные уровни издержек заданы табл. 3.1.

Таблица 3. J

Относительные уровни издержек на предприятиях

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

^>0Ц=1,2,...,4). J

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

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

Целевая функция примет вид у = -2,4^ + 0,8х2 + 22,8. (3.6)

Из сопоставления уравнения (3.5) и последнего из ограни­ чений (3.1) х > О следует:

*,>0; 1

х2>0;

х3=8х, + 12х2-16>0;[

Каждому из неравенств (3.7) на графике рис. 3.1 соответствует полуплоскость, в пределах которой находятся все допускаемые дан­ ным неравенством значения переменной величины х (j = 1,2,..., 6).

Так, неравенству х,- > 0 соответствует полуплоскость вправо от оси х2 (граница ее заштрихована).

Неравенству х3 = 8х, + 12х2 - 16 > 0 соответствует полуплос­ кость вправо и вверх от линии граничного значения данного нера­ венства (при х3 = 0). Уравнение этой линии

3

JC, +—х, - 2 = 0.

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

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

Из всех допустимых планов нас интересует оптимальный план, при котором функция цели у достигает минимума.

Целевой функции соответствует семейство параллельных прямых. Рассмотрим одну из них, проходящую через начало коорди­ нат, что будет иметь место при у = 22,8. При этом х2 = Зх,.

Интересующая нас прямая у = 22,8, как видно из рис. 3.1, имеет наклон вправо от оси х2. Задаваясь различными значения­ ми у, получим семейство прямых линий, параллельных прямой

у = 22,8, проходящей через точку 0. При этом чем меньше будет значение у, тем, очевидно, правее будет располагаться соответ­ ствующая прямая.

Поскольку мы добиваемся минимального значения у, то нас будет интересовать прямая, расположенная в наибольшем удале­ нии вправо от прямой у = 22,8 и проходящая через многоугольник ABCDEF, - прямая ymin.

Единственной точкой, соответствующей оптимальному пла­ ну, будет та вершина многоугольника ABCDEF (рис. 3.1), которая одновременно принадлежит области допустимых планов и отве­ чает требованию минимизации целевой функции у, - вершина С. Из уравнения прямой ВС, проходящей через точку С, следует, что х] = 4. Из уравнения прямой DC, проходящей через ту же точку, следует, что х2 = 0.

Подставляя полученные значения л; = 4 и х2 = 0 в уравнения (3.5), определим величины остальных переменных, составляющих оптимальный план:

*3 = 16; *4 = 0; *5 = Ю; *6 = 8.

Таким образом, оптимальный план будет следующим:

х5 =10;

х6=8. ]

Линейная форма (величина издержек) при этом будет мини­ мальной:

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

При решении этих задач целевая функция рассчитывается по формуле, аналогичной (3.2):

где у* - целевая функция, подлежащая максимизации. Отличие зак­ лючается в том, что знаки перед всеми постоянными коэффи­ циентами меняются на обратные (с* = -с*).

Вычислительные методы линейного программирования

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

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

На основе этой идеи создан и разработан один из основных методов решения задач линейного программирования-так на­ зываемый симплекс-метод.

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

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

Второй шаг. Проверить, оптимален ли найденный план. Если оптимален, вычисления окончены. Если нет - следующий план.

Третий шаг. Переход к другой вершине (другому допусти­ мому плану), в которой значение целевой функции меньше, про­ верка его на оптимальность и т.д.

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

Анализируя рис. 3.1, можно заметить, что в каждой из вер­ шин две из переменных обращаются в нуль. Поэтому мы должны принять две переменные равными нулю, а затем найти остальные четыре из системы уравнений (3.3). В совокупности все переменные дадут один из допустимых планов, соответствующих некоторой вершине.

Чтобы преобразовать систему уравнений описанным обра­ зом, необходимо выразить каждую из неизвестных xv х2,..., хт че­ рез остальные.

Такая возможность существует лишь в случае, если определитель

Га,j а12 ...а1п1

а21а22...а2т

* 0 .

(3.11)

Если это условие выполняется, то величины х]9 x2, ..., хт называют базисными. Каждый базис соответствует определен­ ной вершине.

Преобразуем систему уравнений (3.3) так, чтобы, прирав­ нивая две переменные нулю (например, х5 = 0, х6 = 0), можно было получить значение базисных величин *,, х2, хъ и х4 - координаты одной из вершин многоугольника.

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

Действительно,

'4 П

ОО

О2

4 0J

Это дает нам право считать, что величины х19 х2, хг их4 яв­ ляются базисными и система (3.3) может быть разрешена относи­ тельно их.

Все необходимые преобразования будем производить с мат­ рицей коэффициентов уравнений (3.3):

Преобразуем матрицу (3,1.2) в соответствии с указанным выше требованием получения базисных значений переменных ве­ личин. Для этого необходимо выполнить над ней такие преобразо­ вания, чтобы базисные переменные остались по одной в каждом из уравнений (строке матрицы), а коэффициенты при них были равны единице. Начинаем с коэффициента при х, в первом уравне­ нии. Чтобы сделать его равным единице, делим все коэффициенты первого уравнения на четыре. Для исключения переменной х} из остальных уравнений отнимаем от каждого из них первое уравне­ ние, умноженное на такое число, при котором разность коэффици­ ентов при х] была бы равна нулю. Например, второе и третье урав­ нения (строки) нужно умножить на нуль, четвертое - на единицу.

В результате преобразований получим:

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

ОО О 1 - -1

Выполненная процедура носит название метода полного исключения (так называемое Жорданово исключение).

Теперь, приравнивая переменные х5 и х6 (соответственно пятый и шестой столбцы матрицы) нулю, можем написать значе­ ния базисных переменных, которые будут в этом случае равны сво­ бодным членам соответствующих уравнений:

9

х2 = 5;

Обращаясь к геометрической интерпретации (см. рис. 3.1), можно убедиться, что полученные координаты хх = 2V4, x2 = 5, х5 = х6 = 0 соответствуют вершине А многоугольника ABCDEF - области допустимых планов. Это и есть первый допустимый план.

Теперь можно перейти ко второму шагу симплекс-метода - установлению того, является ли допустимый план, соответствую­ щий найденной вершине А, оптимальным.

Наиболее естественным путем решения этой задачи был бы сплошной перебор всех вершин области допустимых планов, опреде­ ление для каждой из них значений переменных х (j = 1, 2, ..., 6) и вычисление по ним в каждой вершине величины целевой функции.

Та вершина, в которой величина у оказалась бы минималь­ ной, и даст искомый оптимальный план.

Но этот путь весьма неэкономичный, ибо требует просчитать большое количество планов, в том числе и явно неоптимальных.

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

Вчем сущность направленного перебора?

Впервом допустимом плане, соответствующем вершине А, целевая функция в соответствии с формулой (3.6) равна:

vA = -2,4JC, + 0,8JC2 + 22,8 = -2,4 — + 0,8 • 5 + 22,8 = 21,4.

4

Мы уже знаем из выражения (3.9), что ymin = 13,2. Следова­ тельно, целевая функция в точке А значительно больше минимума и необходимо продолжать перебор вершин-планов до тех пор, пока не придем к оптимальному.

Из вершины А можно перейти к соседним вершинам F и В (см. рис. 3.1), двигаясь по сторонам многоугольника AF и АВ со­ ответственно. Видимо, нужно избрать такое направление перехода к соседней вершине, которое приведет к наибольшему уменьше­ нию целевой функции.

Рассчитаем значения целевой функции для соседних вершин F и В. Пользуясь формулой (3.6) и подставляя соответствующие значения х} и xv получим:

yF = -2,4 0 + 0,8 • 5 + 22,8 = 26,8; ув = -2,4 • 4 + 0,8 • 73 + 22,8 = 15,33.

Сопоставляя два последних выражения, нетрудно убедить­ ся, что минимизация функции цели достигается при движении к точке В по стороне АВ. Это означает, что в базис вводится перемен­ ная х5, которая в вершине А была равна нулю.

Поскольку при отсутствии наглядного геометрического пред­ ставления заранее нельзя располагать значениями переменных в вер-