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

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

где индекс] приписывается небазисным (нулевым) переменным, а индекс i - базисным. Для получения значений коэффициента с. це­ левая функция уА преобразуется таким образом, чтобы исключить из нее небазисные переменные х5 их6:

уА = -2,4х, + 0,8х2 + 22,8 = -0,8л:, - \,6х2 + 0,2х3 + 0,8х4 + 72. Значения аг выбираются из соответствующих столбцов

матрицы (3.15).

Имеется доказательство того, что в случае оптимальности полу­ ченного плана все 5, становятся равными нулю или меньше нуля. Включению в базис подлежитта переменная, для которой 5 принимает наибольшее положительное значение. В нашем примере это:

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

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

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

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

положительное значение отношения свободного члена уравнения к коэффициенту при х5 в соответствующем столбце матрицы (3.15).

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

Теперь необходимо получить в четвертой строке значение коэффициента при новой базисной величине *5, равного единице, а все остальные коэффициенты этого столбца обратить в нуль. Для этого проверяем вычислительную процедуру полного исключения.

Получаем

Данной матрице отвечает допустимый план в вершине В. Приравнивая небазисные переменные нулю (х4 = х6 = 0), получа­ ем значения остальных переменных, соответствующих второму плану:

х,=4; х3=48;

-*.. -11

Как уже было показано, ув = 157г Итак, получено суще­ ственное сокращение целевой функции, однако критерий 56 про­ должает оставаться положительным, что говорит о необходимости дальнейшего улучшения плана:

23

36 10

На этот раз в базис вводится переменная х4, а выводится пере­ менная х2, которой соответствует наименьшее значение коэффи­ циента в столбце *6.

После преобразования матрицы (3.17) получаем матрицу (3.18), отвечающую третьему плану:

Данный план соответствует вершине С:

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

Целевая функция при данном плане равна: Ус =13,2.

Итак, мы пришли аналитическим путем к тому же оптималь­ ному плану, который был ранее получен геометрическим способом.

Решение примера 3.1 можно сформулировать следующим образом.

Чтобы издержки при распределении ресурсов между пред­ приятиями были минимальными, количество предприятий пер­ вого типа должно быть равно 4, второго - 0, третьего - 16, чет­ вертого - 0, пятого - 10, шестого - 8.

При этом издержки будут составлять 13,2 единицы.

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

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

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

Техника решения системы уравнений (3.3) с помощью мат­ риц заключается в следующем.

Исходную систему уравнений (3.3) можно компактно

Матрица А содержит коэффициенты при переменных в

Матрица X содержит переменные величины этого уравнения:

i

х2

(3.21)

\X6j

Матрица S содержит свободные члены того же уравнения:

где С - матрица, содержащая коэффициенты при переменных в уравнении (3.4).

Разобьем матрицы А, X и С на подматрицы (клетки) в соот­ ветствии с принятым базисным решением - исходным (или опор­ ным) планом.

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

Матрица X разбивается на подматрицы Х0 и Xs, причем Х0 содержит значения переменных, равных нулю, aXs-значения ос­ тальных (базисных) переменных:

Матрица С разбивается на подматрицы С0 и Cs, причем С0 со­ держит коэффициенты в выражении для линейной формы при нуле­ вых переменных, а С — для остальных (базисных) переменных:

76 Часть I. Глава 3

Затем описанным выше путем устанавливается переменная хА, подлежащая исключению из базиса.

Значения других переменных рассчитываются по формуле

v 7 y

Таким образом, мы получили следующие значения перемен­ ных для второго, улучшенного плана:

xi "" 4 '

х2 = 5; х3 = 62; х4 = 7; *5 = 0; *6 = 0.

Это уже знакомый нам первый допустимый план, которому соответствует точка А на графике рис. 3.1, и т.д.

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

П р и м е р 3.2

Рассмотрим некую производственную ситуацию. Напри­ мер, организация, занимающаяся механизацией трудоемких ра­ бот, располагает набором однородных технических средств в количестве 30 единиц, которые размещаются в трех базах: Ар А,, А3. При этом базы Aj и А2 имеют по 11 единиц техники, а база А3 - 8 единиц. Использование этой техники планируется на четырех объектах Бр Б2, Б3, Б4. Причем объект Б] нуждается в 5 единицах, объекты Б2 и Б3 - в 9 единицах каждый, а объект Б4 - в 7 единицах техники.

Эффективность эксплуатации технических средств во мно­ гом зависит от того, насколько интенсивно они используются, т.е. чем меньше простои, тем выше эффективность. В данном случае простой машин определяется главным образом тем, на каком объек­ те они работают. Например, машины базы А3, занятые на объекте Бр простаивают в среднем 6 ч в неделю, а те же машины на объек­ те Б3 бездействуют лишь 1 ч в неделю.

Общая картина использования техники с указанием ее нали­ чия в базах и потребностей на объектах показана в табл. 3.2.

ресурсы базы Aj оказываются исчерпанными (А{ можно под­ черкнуть), а на объекте Б3 остается потребность в 5 единицах (эта цифра записывается рядом с 9 в скобках).

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

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

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

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

а для тех клеток, где распределения нет, эта сумма будет не более стоимости результата, т.е.

План, все клетки которого отвечают условиям (3.34), (3.35), является оптимальным.

Чтобы определить оптимальность указанного исходного плана, вначале рассчитаем и внесем в табл. 3.3 значения потенци­ алов баз и объектов.