Определение начального допустимого решения
В задаче, представленной в стандартной форме, количество переменных обычно больше, чем количество ограничений. Так, в стандартной форме для примера 2.1 имеются три ограничения (m= 3) и пять переменных (k= 5). Для определения начального решения k-m переменных принимаются равными нулю. Тогда в системе из mравенств остается m переменных (неизвестных); в этом случае их значения можно определить однозначно. Эти значения используются в качестве начального решения задачи. Переменные, значения которых принимаются равными нулю, называются небазисными, остальные – базисными. Количество базисных переменных (переменных, составляющих базис), всегда равно количеству ограничений (т).
Начальный базис легко определить, если в каждом ограничении имеется переменная, входящая в это ограничение с коэффициентом, равным единице, и при этом не входящая ни в одно из других ограничений. Эти переменные принимаются в качестве базисных. Все остальные (небазисные) переменные принимаются равными нулю. Таким образом, базисные переменные принимают значения, равные правым частям ограничений.
Такой способ определения начального базиса наиболее удобен при решении задач, для которых математическая модель состоит только из ограничений «меньше или равно». В таких задачах после приведения к стандартной форме в каждом ограничении имеется переменная, входящая в данное ограничение с коэффициентом, равным единице, и не входящая ни в одно из других ограничений. Эти переменные - остаточные переменные, введенные при приведении задачи к стандартной форме. Эти переменные принимаются в качестве базисных. Все остальные переменные (т.е. переменные, входившие в исходную математическую модель задачи), принимаются в качестве небазисных, т.е. равных нулю. Таким образом, в качестве начального допустимого решения (начальной угловой точки ОДР) принимается начало координат, т.е. решение, в котором все исходные переменные математической модели равны нулю: х1=х2=…=хn=0.
Если базисные переменные присутствуют не во всех ограничениях задачи, то решение х1=х2=…=хn=0 обычно оказывается недопустимым (не соответствует системе ограничений). В этом случае начало координат не может использоваться в качестве начального допустимого решения (начальной угловой точки ОДР). Для поиска начального допустимого решения в таких случаях используются специальные методы (см. лабораторную работу № 3). Обычно это требуется для задач, в которых имеются ограничения «не меньше» или «равно». Найдем начальное допустимое решение для примера 2.1. Для задачи, приведенной к стандартной форме, в качестве базисных переменных следует выбрать переменные х3, х4, х5, так как каждая из них входит только в одно ограничение с коэффициентом, равным единице, и не входит в другие ограничения.
Базисные переменные имеются во всех ограничениях задачи. Переменные х1, х2 принимаются равными нулю, т.е. небазисными. Таким образом, начальное решение задачи следующее: х1=0,х2=0, х3=200, х4=250, х5=500.
Это решение является допустимым, так как значения х1=х2=0 соответствуют системе ограничений (2.1). Таким образом, в качестве начальной угловой точки ОДР выбрано начало координат.
Выбранное решение явно не является оптимальным, так как целевая функция Е=100х1+300х2 при этом равна нулю. По своему смыслу это решение означает, что никакие изделия не выпускаются.
Определение оптимального решения на основе симплекс-таблиц
Как отмечено выше, поиск оптимального решения на основе симплекс-метода состоит в целенаправленном переборе смежных угловых точек ОДР в направлении улучшения значения целевой функции. Можно доказать, что переход из одной угловой точки ОДР в другую (смежную) соответствует замене одной переменной в базисе. Такая замена означает, что одна из небазисных переменных (имевшая нулевое значение) включается в базис, т.е. увеличивается, а одна из базисных переменных уменьшается до нуля, т.е. исключается из базиса. Выбор таких переменных выполняется по определенным правилам, обеспечивающим максимально быстрое увеличение целевой функции.
Рассмотрим алгоритм поиска оптимального решения на основе симплекс-таблиц для примера 2.1.
1. Строится исходная симплекс-таблица. Общий вид симплекс-таблицы показан в табл. 2.1.
Таблица 2.1
| Базис | x1 | x2 | … | xn | xn+1 | xn+2 | … | xk | Решение |
| Е | -С1 | -С2 | … | -Cn | |||||
| Хn+1 | А11 | А12 | … | A1n | В1 | ||||
| Хn+2 | А21 | А22 | … | A2n | В2 | ||||
| … | … | … | … | … | … | … | … | … | … |
| Хк | Аm1 | Аm2 | … | Amn | Вm |
Симплекс-таблица строится по следующим правилам:
· в первой строке перечисляются все переменные задачи, как исходные (х1, х2,…,хn), так и дополнительные, введенные при приведении к стандартной форме (хn+1, xn+2,…,xk). Для задач, содержащих только ограничения «меньше или равно», дополнительные переменные хn+1, xn+2,…,xk - это остаточные переменные;
· в первой колонке таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений. Для задач, содержащих только ограничения «меньше или равно», начальный базис состоит из остаточных переменных хn+1,xn+2,…,xk . В этой же колонке указывается обозначение целевой функции Е;
· в строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для остаточных переменных хn+1,xn+2,…,xk, указываются нули;
· в строках базисных переменных указываются коэффициенты ограничений, в которые входят эти переменные. Для переменных, не входящих в ограничения, указываются нулевые коэффициенты;
· в последнем столбце («Решение») указываются значения базисных переменных (они равны правым частям ограничений), а также начальное значение целевой функции (0).
Если таблица построена правильно, то в столбце каждой базисной переменной должна присутствовать только одна единица (в строке ограничения, в которое входит эта переменная); остальные коэффициенты - нулевые.
Исходная симплекс-таблица для примера 2.1 приведена в табл. 2.2.
Таблица 2.2
| Базис | х1 | х2 | x3 | x4 | х5 | Решение |
| Е | -100 | -300 | ||||
| х3 | ||||||
| х4 | ||||||
| х5 |
2. Проверяется условие окончания решения задачи. Если в строке целевой функции (Е-строке) все коэффициенты неотрицательны, это означает, что оптимальное решение найдено. В противном случае выполняется следующий шаг.
3. Определяется переменная для включения в базис. В качестве такой переменной выбирается переменная, которой соответствует максимальный по модулю отрицательный коэффициент в Е-строке. Включение в базис (т.е. увеличение) такой переменной приводит к наиболее быстрому росту целевой функции. Столбец переменной, выбранной для включения в базис, называется ведущим (разрешающим).
Для рассматриваемого примера в базис необходимо включить переменную х2, так как ей соответствует максимальный по модулю отрицательный коэффициент Е-строки (-300). Это означает увеличение выпуска задвижек. Из условия задачи и целевой функции видно, что увеличение выпуска задвижек приводит к более быстрому росту целевой функции, чем увеличение выпуска корпусов: выпуск каждой задвижки увеличивает целевую функцию (прибыль) на 300 ден. ед., а выпуск каждого корпуса - только на 100 ден. ед.
Примечание. Если в Е-строке имеется несколько максимальных по модулю отрицательных элементов (равных между собой), то для включения в базис можно выбирать любую из соответствующих переменных.
4. Определяется переменная для исключения из базиса. Для этого вычисляются отношения значений базисных переменных (указанных в столбце «Решение») к соответствующим элементам ведущего столбца. Такие отношения (называемые симплексными отношениями) вычисляются только для положительных коэффициентов ведущего столбца. Переменная, которой соответствует минимальное симплексное отношение, исключается из базиса.
Строка переменной, выбранной для исключения из базиса, называется ведущей (разрешающей). Элемент на пересечении ведущей строки и столбца называется ведущим (разрешающим) элементом.
Найдем симплексные отношения для рассматриваемого примера: 200/5=40, 250/5 = 50, 500/20 = 25. Минимальное симплексное отношение получено для последней строки, соответствующей базисной переменной х5. Значит, эта переменная исключается из базиса (становится равной нулю).
Такой способ определения переменной, исключаемой из базиса, имеет следующее обоснование. При включении в базис новой переменной ее значение увеличивается. Чтобы по-прежнему соблюдались ограничения (2.1), необходимо в каждом из ограничений уменьшать базисные переменные. Увеличение переменной, включаемой в базис, возможно только до тех пор, пока одна из базисных переменных не станет равной нулю. Минимальное симплексное отношение показывает, какая из базисных переменных первой уменьшается до нуля (т.е. исключается из базиса). Так, для рассматриваемого примера, при увеличении переменной х2 (т.е. при ее включении в базис) для соблюдения ограничений (2.1) необходимо уменьшать переменные х3, х4, х5. Например, при каждом увеличении переменной х2на единицу необходимо уменьшать переменную х3 на 5, х4 - также на 5, х5 - на 20. Минимальное симплексное отношение показывает, что при увеличении х2 переменная х5 первой достигнет нулевого значения. Смысл симплексных отношений для данной задачи следующий: они показывают, что имеющегося запаса алюминия (200 кг) хватит на выпуск 40 задвижек, запаса стали (250 кг) - на 50 задвижек, запаса пластмассы (500 кг) - на 25 задвижек. Таким образом, запас пластмассы будет израсходован первым, поэтому из базиса исключается переменная х5. Ниже будет показано, что переменная х5 обозначает остаток запаса пластмассы.
Примечания:
· Если имеется несколько минимальных симплексных отношений (равных между собой), то для исключения из базиса можно выбирать любую из соответствующих переменных.
· Если все элементы ведущего столбца оказываются отрицательными или равными нулю (т.е. невозможно вычислить ни одного симплексного отношения), это означает, что переменную, включаемую в базис, можно увеличивать на любую величину, не нарушая ни одного из ограничений задачи. Целевая функция при этом также может увеличиваться бесконечно. Обычно такой случай означает, что допущена ошибка в постановке задачи или в математической модели (не учтено некоторое ограничение).
5. Выполняется преобразование симплекс-таблицы по следующим правилам:
• в столбце «Базис» вместо переменной, исключенной из базиса на шаге 4, указывается переменная, включенная в базис на шаге 3;
• все элементы ведущей строки делятся на ведущий элемент;
• все элементы ведущего столбца (кроме ведущего элемента) заменяются нулями;
• все остальные элементы таблицы (включая Е-строку и столбец «Решение») пересчитываются по «правилу прямоугольника». Этот пересчет выполняется следующим образом: ведущий и пересчитываемый элемент образуют диагональ прямоугольника; находится произведение ведущего и пересчитываемого элемента; из этого произведения вычитается произведение элементов, образующих противоположную диагональ прямоугольника; результат делится на ведущий элемент.
Выполним пересчет симплекс-таблицы, приведенной в табл. 2.2. В столбце «Базис» х5 заменяется на х2. Все элементы ведущей строки делятся на ведущий элемент, равный 20. Ведущий столбец (х2) заполняется нулями. Все остальные элементы пересчитываются по «правилу прямоугольника». Например, коэффициент на пересечении Е-строки и столбца х1 пересчитывается следующим образом: (20*(-100) - (-300)*5)/20 =-25. Коэффициент на пересечении строки х3 и столбца х5 пересчитывается следующим образом: (20*0 – 5*1)/20 = -0,25. Расчет этих элементов иллюстрируется рис. 2.2. Полученная симплекс-таблица приведена в табл. 2.3.
Рис. 2.2. Примеры расчетов по «правилу прямоугольника»
Таблица 2.3
| Базис | x1 | х2 | x3 | x4 | x5 | Решение |
| Е | -25,00 | 0,00 | 0,00 | 0,00 | 15,00 | 7500,00 |
| x3 | 18,75 | 0,00 | 1,00 | 0,00 | -0,25 | 75,00 |
| x4 | 8,75 | 0,00 | 0,00 | 1,00 | -0,25 | 125,00 |
| x2 | 0,25 | 1,00 | 0,00 | 0,00 | 0,05 | 25,00 |
6. Выполняется возврат к шагу 2.
Для рассматриваемого примера на шаге 5 получено следующее решение (табл. 2.3): х2=25; х3=75; х4=125; х1=х3=0 (так как переменныех1и х3 - небазисные). Это решение соответствует угловой точке ОДР, обозначенной на рис.2.1 как А (х1=0;х2=25). Видно, что полученное решение (табл. 2.3) не является оптимальным, так как в Е-строке имеется отрицательный элемент (—25). Поэтому алгоритм продолжается. Определяется переменная для включения в базис (шаг 3). Это переменная х1, так как только для этой переменной в Е-строке содержится отрицательный элемент. Определяется переменная, исключаемая из базиса (шаг 4). Для этого вычисляются симплексные отношения:
75/18,75 = 4;
125/8,75 = 14,29;
25/0,25 = 100.
Минимальное симплексное отношение соответствует переменной х3; она исключается из базиса. Таким образом, ведущий столбец-х1, ведущая строка- х3, ведущий элемент равен 18,75. Симплекс-таблица преобразуется по правилам, приведенным на шаге 5. Полученная симплекс-таблица показана в табл. 2.4.
Таблица 2.4
| Базис | x1 | х2 | x3 | x4 | x5 | Решение |
| Е | 0,00 | 0,00 | 1,33 | 0,00 | 14,67 | 7600,00 |
| х1 | 1,00 | 0,00 | 0,05 | 0,00 | -0,01 | 4,00 |
| х4 | 0,00 | 0,00 | -0,47 | 1,00 | -0,13 | 90,00 |
| х2 | 0,00 | 1,00 | -0,01 | 0,00 | 0,05 | 24,00 |
Выполняется возврат к шагу 2 (проверка оптимальности полученного решения). Решение, полученное в табл. 2.4, оптимально, так как в Е - строке нет отрицательных элементов.
Полученное решение соответствует угловой точке ОДР, обозначенной на рис. 2.1 как В (х1=4;х2=24).
По окончании алгоритма в столбце «Решение» находятся оптимальные значения базисных переменных, а также значение целевой функции, соответствующее полученному решению. Оптимальные значения небазисных переменных равны нулю.
Таким образом, для задачи из примера 2.1 получено следующее оптимальное решение: х1=4; х2=24; х3=0; х4=90; х5=0; Е=7600. Значения переменныхх1=4, х2=24 показывают, что цех должен выпускать за смену 4 корпуса и 24 задвижки. В этом случае будет получена максимальная прибыль в размере 7600 ден. ед. (значение целевой функции).
Остаточные переменные х3, х4, х5 также имеют физический смысл. Например, из системы ограничении (2.1) видно, что величина 20х1+5х2 представляет собой расход алюминия на выпуск всех изделий, а величина 200 (правая часть ограничения) - имеющийся запас алюминия. Переменная х3 представляет собой разность этих величин, т.е. неизрасходованный остаток запаса алюминия. Так как х3 = 0. значит, весь запас алюминия (200 кг) расходуется на выпуск изделий. Аналогично можно показать, что переменная х4 представляет собой неизрасходованный остаток стали, а х5 - пластмассы. Таким образом, остается неизрасходованным 90 кг стали (расход стали на выпуск всех изделий составит 250 - 90 = 160 кг). Неизрасходованный остаток пластмассы равен нулю, значит, все 500 кг пластмассы расходуются на выпуск изделий.
Примечания:
1. Смысл остаточных переменных (как и остальных переменных, используемых в математической модели) полностью зависит от постановки задачи.
2. По результатам решения задачи переменные х1 и х2 приняли целочисленные значения. Если бы они оказались дробными, то потребовалось бы использовать специальные методы (см. лабораторную работу № 4) для получения целочисленного решения, так как эти переменные обозначают количество изделий.