korobov

111

программе на ключевой элемент a13=5, устанавливаем, сколько продукции х3 (вида Р3) теперь должно вырабатываться в новом варианте программы. Все остальные элементы ключевой строки надо разделить на ключевой элемент, чтобы они в новой таблице также соответствовали не x4 а вновь введенной базисной неизвестной х3.

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

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

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

Результаты пересчета табл. 3.2 приведены в табл. 3.3, которая соответствует

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

Табл. 3.З

112

По правилу замещения она получается следующим образом. В табл. 3.2 второй строке соответствует коэффициент α = 2/5, на этот коэффициент умножаются все элементы первой (ключевой) строки, в результате получаем строку из чисел: 1500 2/5 = 600; 2 2/5 =4/5; 3 2/5 =6/5; 5 2/5 = 2; 1 2/5=2/5; 0 2/5 = 0; 0 2/5 = 0; 0 2/5 = 0; 1511 2/5=3022/5, затем полученный ряд чисел вычитаем соответственно из чисел преобразуемой второй строки. В результате имеем: 1000-600 = 400; 1- 4/5=1/5; 4-6/5 = 14/5; 2-2 = 0; 0-2/5 = - 2/5; 1-0=1; 0-0 = 0; 0-0 = 0; 1008-3022/5=2018/5, т. е. вторую строку в табл. 3.3, не считая чисел в столбце β иα.

Сумма чисел

совпадает с числом 1008—1511 2/5 = 2018/5, полученным по правилу замещения, что является признаком того, что вторая строка в табл. 3.3 получена правильно.

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

строку.

Далее кратко рассмотрим экономическую сущность преобразования элементов симплексной таблицы. Зачем, например, надо было пересчитывать элементы итогового столбца В (1000, 1800, 2200)? Чтобы ответить на этот вопрос, надо вспомнить экономическое содержание этих цифр.

В нашем примере они представляют (в первой симплексной таблице) общие ресурсы машинного времени по группе машин типа A, В и ресурсы материалов вида М1 и М2. Поскольку в новую программу вводится новая неизвестная х3, представляющая выпуск продукции Р3, то на ее производство будет израсходована какая-то часть ресурсов. Эту израсходованную часть ресурсов надо учесть (исключить из первоначального значения) при расчете элементов итогового столбца, соответствующих новой программе.

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

Вторая программа Р1 «лучше» исходной Р0 с нулевой прибылью, в ней уже прибыль составляет 1800 руб., но она оказывается также не оптимальной, так как две двойственные оценки в табл. 3.3 1 и 2 отрицательны.

В таком случае надо перейти к новой программе Р2, для чего следует проделать все последовательные операции подобно тем, которые были выполнены при переходе от исходной программы P0 к программе Р1.

113

Вкачестве ключевого столбца здесь надо принять столбец х1, так как включение

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

Вкачестве ключевой строки следует принять строку x7 — с минимальным

Таким образом, неизвестную х1 надо ввести в базисные вместо базисной неизвестной х7, содержащейся в программе Р1.

Далее производится преобразование элементов матрицы — табл. 3.3 по правилам замещения с ключевым элементом α41 = 2. В результате операции одноразового замещения получаем третью симплексную табл. 3.4.

Т а б л. 3.4

Программа Р2 лучше программы Р1 (3.8), так как в ней значение целевой функции (суммарная прибыль) выше по сравнению с программой P1 на 210 руб., однако и она не является оптимальной. Поэтому надо перейти к следующей новой программе Рз, путем введения в нее неизвестной х2 в качестве базисной вместо х5.

Составим следующую табл. 3.5, в которой заполним столбец PЗ и столбец с0. Далее необходимо вычислить новые значения элементовматрицы.

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

Т а б л . 3.5

114

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

значению выравнивающей переменной х6.

Экономический результат решения (3.10) заключается в том, что с целью получения максимальной прибыли необходимо выпустить 407 ед. продукции Р1, 114 ед. продукции Р2 и 69 ед. продукции Р3. При таком округлении плана выпуска продукции до целых чисел максимальный доход от ее производства составит 2091 руб.

Имеющиеся ресурсы используются при этом следующим образом: машинное время и материалы вида М2 используются полностью, а материалы вида М1 используются не полностью (приблизительно на 92%).

115

3.2. Симплексный метод в решении задач с условием в виде уравнений и неравенств со знаком ≥ (метод искусственного базиса)

В предыдущем параграфе нами рассмотрен основной алгоритм симплексного метода для решения так называемой стандартной задачи линейного программирования на

n

максимум целевой функции F = ∑cj xj , условие которой было представлено в виде

j=1

n

неравенств ∑αij xj ≤ bi (i = 1,2,...,m) с положительными свободными членами. Исходные

j=1

неравенства нами были преобразованы в уравнения путем ввода дополнительных неотрицательных неизвестных (xn+1,…,хп+т). Дополнительные неизвестные входили в симплексные уравнения со знаком плюс, и в единичной подматрице на главной диагонали мы имели элементы, равные единице. Это позволило нам получить исходную программу.

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

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

Предположим, дано условие задачи в виде системы линейных уравнений:

переменных xj, которые бы входили с коэффициентом + 1 один раз в какое-либо одно уравнение системы.

Следовательно, нет и явной исходной программы.

116

Рассмотрим еще один пример — раскройную задачу, которая нами была изложена и математически сформулирована в 1.2 В результате проведенной постановки была получена математическая модель задачи, заключающаяся в минимизации целевой функции

Эти исходные неравенства надо преобразовать в равенства с неотрицательными неизвестными. Для этого надо ввести дополнительные неотрицательные неизвестные х6,

x7, х8 и x9 (а в общем случае xn+1, хп+2,…,хп+т) в неравенства-ограничения так, чтобы они превратились в уравнения.

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

Итак, вышеуказанные системы неравенств преобразуются в следующие

117

Вматрицах систем уравнений такого вида не содержится единичной подматрицы,

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

неизвестные в качестве базисных, то они окажутся отрицательными (х1 = х2 = х3 = х4 = x5 = 0, х6= — 500, х7 = — 1000, х8 = — 200, x9 = — 400), т. е. не будут удовлетворять условиям неотрицательности всех переменных. Следовательно, здесь мы не имеем явной неотрицательной исходной программы.

Для решения задачи необходима единичная подматрица (с положительными элементами). Чтобы получить ее, надо ввести еще одну группу неизвестных, число которых равно числу исходных неравенств (или уравнений — в первом примере), по одному такому неизвестному на каждое неравенство (или уравнение). Эти новые неизвестные в отличие от дополнительных — уравновешивающих — называют искусственными. В данной задаче обозначим их через y1, у2, у3, y4 и введем их в левые части уравнений со знаком плюс.

Симплексные уравнения исходных условий в окончательном виде, допускающем перенесение коэффициентов при неизвестных непосредственно в первоначальную симплекcную таблицу, будут1:

В этих уравнениях имеется единичная подматрица и все неизвестные считаются неотрицательными. Дальнейшее решение задачи может быть выполнено двумя способами. Рассмотрим их последовательно.

Первый способ заключается в отыскании какой-то программы (опорного плана) основной задачи (3.16), (3.17) посредством решения вспомогательной задачи, которая

F’=0x1+0x2+0x3+0x4+0x5+0x6+0x7+0x8+0x9+1y1+1y2+1y3+1y4=min

Если получится минимум этой целевой функции, равный нулю (F' = 0), то в решении этой вспомогательной задачи (3.24; 3.25) получится искомая программа исходной задачи (3.16; 3.17).

Последняя таблица вспомогательной задачи при F'=0 = min служит основой для составления первоначальной симплексной таблицы для решения исходной задачи. С этой целью надо из последней таблицы вспомогательной задачи отбросить столбцы, соответствующие неизвестным у1, у2, y3 и y4, затем изменить коэффициенты сj в первой строке и столбце с0, заменив их соответствующими коэффициентами сj, из целевой функции

118

(3.17) исходной задачи и продолжить таким образом решение на минимум целевой функции исходной задачи.

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

Рассмотрим сущность этого способа на решении приведенной здесь раскройной

n

задачи (первая, с условием ∑αij x j = bi , решается подобным же образом).

j=1

Итак, с целью отыскания одного из решений этой задачи, приступим к решению вспомогательной задачи, ограничительные условия которой выражены симплексными уравнениями (3.24), а целевая функция — выражением (3.25).

1Симплексные уравнения исходных условий, применительно к первому примеру, примут окончательную форму:

2=1х1-1х2+2х3-1х4+1y1+0y2+0y3; 6=2х1+1х2-3х3+1х4+0y1+1y2+0y3; 7=1х1+1х2+1х3+1х4+0y1+0y2+1y3.

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

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

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

Отличительная особенность решения этой задачи от рассмотренной в предыдущем параграфе заключается в том, что здесь определяется не максимум, а минимум целевой функции. При решении этой задачи на минимум можно было поменять все знаки двойственных оценок на обратные и дальше все операции производить тем же способом как и ранее. Но можно сделать иначе. Оставим те знаки двойственных оценок, какие они есть, а в качестве ключевого выберем такой столбец, у которого имеется наибольшая положительная оценка, а не наименьшая, отрицательная как раньше. Решение будет оптимально тогда, когда не останется ни одной положительной оценки, превышающей ноль, т.е. когда все j≤0. Так мы и будем решать эту задачу.

Первая программа оказалась не оптимальной. Переходим ко второй программе. Для этого введем в базисные переменную x1, поскольку двойственная оценка в этом столбце оказалась наибольшей из положительных. При переходе к «лучшему» решению это обеспечивает наибольшее снижение целевой функции F' при ее минимизации. Принимая в качестве базисной переменную x1, вместо уз, получим новую программуP2.

Однако эта 2-я программа, соответствующая 2-й итерации, так же как и первая, оказалась не оптимальной. Поэтому переходим к следующей программе. Для этого в качестве базисной примем переменную х4 вместо y4, так как в столбце, соответствующем х4, оказалась самая большая положительная двойственная оценка на этой 2-й итерации.

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

Программа P5, соответствующая 5-й итерации, оказалась оптимальной, так как нет

119

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

одновременно является опорным планом исходной задачи (3.16), (3.17), ограничительные условия которой для удобства чтения запишем еще раз:

x2 + 2x4 + x5 ≥ 400.

Вэтом нетрудно убедиться, подставив значения неизвестных х1, x2, xз, x4 и x5 в

неравенства: