Принцип работы симплекс-метода

Цель работы

1. Рассмотреть пример задачи линейного программирования: задача планирования производства.

2. Изучить принцип работы симплекс-метода.

3. Научиться определять начальное допустимое решение и оптимальное решения на основе симплекс-таблиц.

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

Теоретическое введение

2.2.1 Симплекс – (от лат. simplex – простой, математический), простейший выпуклый многогранник данного числа измерений n. При n = 3 трёхмерный симплекс представляет собой произвольный, в том числе неправильный, тетраэдр. Под двумерным симплексом понимают произвольный треугольник, а под одномерным - отрезок. Нульмерный симплекс есть просто одна точка.

n-мерный симпекс имеет n + 1 вершин, не принадлежащих ни к какому (n - 1)-мерному подпространству того Евклидова пространства (с числом измерений n или больше), в котором лежит данный симплекс. Обратно, всякие n + 1 точек евклидова n-мерного пространства R^m, m ³ n, не лежащие ни в каком подпространстве менее n измерений, однозначно определяют n-мepный симплекс с вершинами в заданных точках e₀, e₁,..., e_n, он может быть определён как выпуклое замыкание совокупности заданных n + 1 точек, т. е. как пересечение всех выпуклых тел пространства R^m, содержащих эти точки. Если в пространстве R^m дана система декартовых координат x₁, х₂,..., х_т, в которой вершина e_i, i = 0, 1,..., n, имеет координаты x₁⁽ⁱ⁾, x₂⁽ⁱ⁾,..., x_m ⁽ⁱ⁾, то симплекс с вершинами e₀, e₁,..., e_m состоит из всех точек пространства, координаты которых имеют вид:

,

k = 1,2,..., m, где m⁽⁰⁾, m⁽¹⁾,..., m^(п) - произвольные неотрицательные числа, дающие в сумме 1.

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

Любые r + 1 вершин, 0 £ r £ n - 1, взятые из числа данных n + 1 вершин n-мерного симплекса, определяют некоторый r-мерный симплекс. - r-мерную грань данного симплекса. Нульмерные грани симплекса называются вершинами, одномерные грани – ребрами.

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

Можно доказать, что экстремум (минимум иди максимум) целевой функции всегда достигается при значениях переменных х₁,х₂,…,х_n, соответствующих одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР.

Методика выполнения работы

2.2.2.1 Пример задачи линейного программирования: задача планирования производства

Одной из наиболее распространенных практических задач, решаемых методами линейного программирования, является задача планирования производства при ограниченных ресурсах. Основной метод решения задач линейного программирования – симплекс-метод – будет рассмотрен на примере решения такой задачи.

Пример 2.1.Один из цехов машиностроительного предприятия выпускает изделия из двух видов: корпуса и задвижки. Для производства этих изделий требуются три вида сырья: алюминий, сталь и пластмасса. На выпуск одного корпуса расходуется 20 кг алюминия, 10 кг стали и 5 кг пластмассы. На выпуск одной задвижки расходуется 5 кг алюминия, 5 кг стали и 20 кгпластмассы. Запасы ресурсов ограничены: за рабочую смену цех может израсходовать не более 200 кг алюминия, 250 кг стали и 500 кг пластмассы.

Выпуск одного корпуса приносит предприятию прибыль в размере 100 денежных единиц (ден. ед.), одной задвижки – 300 ден. ед.

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

Для построения математической модели задачи введем переменные. Обозначим через х₁ количество выпускаемых корпусов, через х₂ - количество выпускаемых задвижек.

Составим ограничение на расход алюминия. На выпуск одного корпуса расходуется 20 кг алюминия: значит, расход алюминия на выпуск всех корпусов составит 20х₁ кг. На выпуск задвижек будет израсходовано 5х₂ кг алюминия. Таким образом, общий расход алюминия составит 20х₁ + 5х₂ кг Эта величина не должна превышать 200 кг, так как цех не может израсходовать за смену свыше 200 кг алюминия. Поэтому можно записать следующее ограничение:

20х₁+5х₂ ≤ 200

Аналогично можно составить ограничение на расход стали:

10х₁+5х₂≤ 250

и на расход пластмассы:

5х₁+20х₂≤ 500

Кроме того, переменные х₁ и х₂ по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество изделий. Поэтому необходимо указать ограничения неотрицательности:

х₁≥ 0, х₂≥ 0.

В данной задаче требуется определить количество выпускаемых изделий, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одного корпуса составляет 100 ден. ед.: значит, прибыль от выпуска корпусов составит 100х₁ ден. ед. Прибыль от выпуска задвижек составит 300х₂ ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 100х₁+300х₂ ден. ед. Требуется найти такие значения переменных х₁ и х₂ при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е=100х₁+300х₂→max

Приведем полную математическую модель рассматриваемой задачи:

20х₁+5х₂≤ 200

10х₁+5х₂≤ 250(2.1)

5х₁+20х₂≤ 500

х₁≥ 0, х₂≥ 0

Е=100х₁+300х₂→max

Примечание. В данной задаче на переменные х₁ и х₂ накладывается также ограничение целочисленности: они должны принимать только целые значения, так как обозначают количество изделий. Если в результате решения задачи эти переменные примут дробные значения, то для получения целочисленного решения потребуется использовать специальные методы, рассматриваемые в лабораторной работе № 4.

Эту задачу можно решить также графическим методом. Решение показано на рис. 2.1.

Рис. 2.1. Решение примера 2.1 графическим методом

Найдем значения целевой функции для угловых точек ОДР:

Е(О) = 100*0+300*0 = 0,

Е(А) = 100*0 +300*25 = 7500,

Е(В) = 100*4 +300*24 = 7600,

Е(С) = 100*10+300*0 = 1000.

Таким образом, оптимальное решение находится в точке В = (4;24). Это означает, что цех должен выпускать за смену 4 корпуса и 24 задвижки. Прибыль при этом составит 7600 ден. ед.

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

Для решения задачи симплекс-методом требуется привести ее к стандартной форме, как показано в подразделе 1.2.2.3. Все ограничения задачи имеют вид «меньше или равно». Их необходимо преобразовать в равенства. Для этого требуется добавить в каждое ограничение дополнительную (остаточную) переменную. Математическая модель задачи в стандартной форме будет иметь следующий вид:

20х₁+5х₂+х₃=200

10х₁+5х₂+х₄=250 (2.2)

5х₁+20х₂+х₅=500

х_j≥ 0, j=1,…,5.

E=100х₁+300х₂→max

Здесь х₃,х₄,х₅- остаточные переменные. Их физический смысл будет показан в п. 2.2.2.4.

Таблица 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

Симплекс-таблица строится по следующим правилам:

· в первой строке перечисляются все переменные задачи, как исходные (х₁, х₂,…,х_n), так и дополнительные, введенные при приведении к стандартной форме (х_n+1, x_n+2,…,x_k). Для задач, содержащих только ограничения «меньше или равно», дополнительные переменные х_n+1, x_n+2,…,x_k - это остаточные переменные;

· в первой колонке таблицы («Базис») перечисляются переменные, составляющие начальный базис задачи. Их количество всегда равно количеству ограничений. Для задач, содержащих только ограничения «меньше или равно», начальный базис состоит из остаточных переменных х_n+1,x_n+2,…,x_k . В этой же колонке указывается обозначение целевой функции Е;

· в строке целевой функции указываются коэффициенты целевой функции с обратным знаком. Для переменных, не входящих в целевую функцию (например, для остаточных переменных х_n+1,x_n+2,…,x_k, указываются нули;

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

· в последнем столбце («Решение») указываются значения базисных переменных (они равны правым частям ограничений), а также начальное значение целевой функции (0).

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

Исходная симплекс-таблица для примера 2.1 приведена в табл. 2.2.

Таблица 2.2

Базис	х1	х2	x3	x4	х5	Решение
Е	-100	-300
х3
х4
х5

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

3. Определяется переменная для включения в базис. В качестве такой переменной выбирается переменная, которой соответствует максимальный по модулю отрицательный коэффициент в Е-строке. Включение в базис (т.е. увеличение) такой переменной приводит к наиболее быстрому росту целевой функции. Столбец переменной, выбранной для включения в базис, называется ведущим (разрешающим).

Для рассматриваемого примера в базис необходимо включить переменную х₂, так как ей соответствует максимальный по модулю отрицательный коэффициент Е-строки (-300). Это означает увеличение выпуска задвижек. Из условия задачи и целевой функции видно, что увеличение выпуска задвижек приводит к более быстрому росту целевой функции, чем увеличение выпуска корпусов: выпуск каждой задвижки увеличивает целевую функцию (прибыль) на 300 ден. ед., а выпуск каждого корпуса - только на 100 ден. ед.

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

4. Определяется переменная для исключения из базиса. Для этого вычисляются отношения значений базисных переменных (указанных в столбце «Решение») к соответствующим элементам ведущего столбца. Такие отношения (называемые симплексными отношениями) вычисляются только для положительных коэффициентов ведущего столбца. Переменная, которой соответствует минимальное симплексное отношение, исключается из базиса.

Строка переменной, выбранной для исключения из базиса, называется ведущей (разрешающей). Элемент на пересечении ведущей строки и столбца называется ведущим (разрешающим) элементом.

Найдем симплексные отношения для рассматриваемого примера: 200/5=40, 250/5 = 50, 500/20 = 25. Минимальное симплексное отношение получено для последней строки, соответствующей базисной переменной х₅. Значит, эта переменная исключается из базиса (становится равной нулю).

Такой способ определения переменной, исключаемой из базиса, имеет следующее обоснование. При включении в базис новой переменной ее значение увеличивается. Чтобы по-прежнему соблюдались ограничения (2.1), необходимо в каждом из ограничений уменьшать базисные переменные. Увеличение переменной, включаемой в базис, возможно только до тех пор, пока одна из базисных переменных не станет равной нулю. Минимальное симплексное отношение показывает, какая из базисных переменных первой уменьшается до нуля (т.е. исключается из базиса). Так, для рассматриваемого примера, при увеличении переменной х₂ (т.е. при ее включении в базис) для соблюдения ограничений (2.1) необходимо уменьшать переменные х₃, х₄, х₅. Например, при каждом увеличении переменной х₂на единицу необходимо уменьшать переменную х₃ на 5, х₄ - также на 5, х₅ - на 20. Минимальное симплексное отношение показывает, что при увеличении х₂ переменная х₅ первой достигнет нулевого значения. Смысл симплексных отношений для данной задачи следующий: они показывают, что имеющегося запаса алюминия (200 кг) хватит на выпуск 40 задвижек, запаса стали (250 кг) - на 50 задвижек, запаса пластмассы (500 кг) - на 25 задвижек. Таким образом, запас пластмассы будет израсходован первым, поэтому из базиса исключается переменная х₅. Ниже будет показано, что переменная х₅ обозначает остаток запаса пластмассы.

Примечания:

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

· Если все элементы ведущего столбца оказываются отрицательными или равными нулю (т.е. невозможно вычислить ни одного симплексного отношения), это означает, что переменную, включаемую в базис, можно увеличивать на любую величину, не нарушая ни одного из ограничений задачи. Целевая функция при этом также может увеличиваться бесконечно. Обычно такой случай означает, что допущена ошибка в постановке задачи или в математической модели (не учтено некоторое ограничение).

5. Выполняется преобразование симплекс-таблицы по следующим правилам:

• в столбце «Базис» вместо переменной, исключенной из базиса на шаге 4, указывается переменная, включенная в базис на шаге 3;

• все элементы ведущей строки делятся на ведущий элемент;

• все элементы ведущего столбца (кроме ведущего элемента) заменяются нулями;

• все остальные элементы таблицы (включая Е-строку и столбец «Решение») пересчитываются по «правилу прямоугольника». Этот пересчет выполняется следующим образом: ведущий и пересчитываемый элемент образуют диагональ прямоугольника; находится произведение ведущего и пересчитываемого элемента; из этого произведения вычитается произведение элементов, образующих противоположную диагональ прямоугольника; результат делится на ведущий элемент.

Выполним пересчет симплекс-таблицы, приведенной в табл. 2.2. В столбце «Базис» х₅ заменяется на х₂. Все элементы ведущей строки делятся на ведущий элемент, равный 20. Ведущий столбец (х₂) заполняется нулями. Все остальные элементы пересчитываются по «правилу прямоугольника». Например, коэффициент на пересечении Е-строки и столбца х₁ пересчитывается следующим образом: (20*(-100) - (-300)*5)/20 =-25. Коэффициент на пересечении строки х₃ и столбца х₅ пересчитывается следующим образом: (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): х₂=25; х₃=75; х₄=125; х₁=х₃=0 (так как переменныех₁и х₃ - небазисные). Это решение соответствует угловой точке ОДР, обозначенной на рис.2.1 как А (х₁=0;х₂=25). Видно, что полученное решение (табл. 2.3) не является оптимальным, так как в Е-строке имеется отрицательный элемент (—25). Поэтому алгоритм продолжается. Определяется переменная для включения в базис (шаг 3). Это переменная х₁, так как только для этой переменной в Е-строке содержится отрицательный элемент. Определяется переменная, исключаемая из базиса (шаг 4). Для этого вычисляются симплексные отношения:

75/18,75 = 4;

125/8,75 = 14,29;

25/0,25 = 100.

Минимальное симплексное отношение соответствует переменной х₃; она исключается из базиса. Таким образом, ведущий столбец-х₁, ведущая строка- х₃, ведущий элемент равен 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 как В (х₁=4;х₂=24).

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

Таким образом, для задачи из примера 2.1 получено следующее оптимальное решение: х₁=4; х₂=24; х₃=0; х₄=90; х₅=0; Е=7600. Значения переменныхх₁=4, х₂=24 показывают, что цех должен выпускать за смену 4 корпуса и 24 задвижки. В этом случае будет получена максимальная прибыль в размере 7600 ден. ед. (значение целевой функции).

Остаточные переменные х₃, х₄, х₅ также имеют физический смысл. Например, из системы ограничении (2.1) видно, что величина 20х₁+5х₂ представляет собой расход алюминия на выпуск всех изделий, а величина 200 (правая часть ограничения) - имеющийся запас алюминия. Переменная х₃ представляет собой разность этих величин, т.е. неизрасходованный остаток запаса алюминия. Так как х₃ = 0. значит, весь запас алюминия (200 кг) расходуется на выпуск изделий. Аналогично можно показать, что переменная х₄ представляет собой неизрасходованный остаток стали, а х₅ - пластмассы. Таким образом, остается неизрасходованным 90 кг стали (расход стали на выпуск всех изделий составит 250 - 90 = 160 кг). Неизрасходованный остаток пластмассы равен нулю, значит, все 500 кг пластмассы расходуются на выпуск изделий.

Примечания:

1. Смысл остаточных переменных (как и остальных переменных, используемых в математической модели) полностью зависит от постановки задачи.

2. По результатам решения задачи переменные х₁ и х₂ приняли целочисленные значения. Если бы они оказались дробными, то потребовалось бы использовать специальные методы (см. лабораторную работу № 4) для получения целочисленного решения, так как эти переменные обозначают количество изделий.

Статус ресурсов

По статусу ресурсы делятся на дефицитные и недефицитные. Если для реализации оптимального решения ресурс расходуется полностью, то он называется дефицитным, если не полностью - недефицитным. Статус ресурсов определяется по значениям остаточных переменных. В примере 2.1 алюминий и пластмасса являются дефицитными ресурсами, так как они расходуются полностью (см. подраздел 2.2.3.4). Сталь - недефицитный ресурс, так как 90 кг стали остаются неизрасходованными (х₄= 90). Увеличение запасов дефицитных ресурсов позволяет увеличить целевую функцию (прибыль). Снижение запасов дефицитных ресурсов приводит к снижению прибыли. Увеличение запасов недефицитных ресурсов всегда нецелесообразно, так как оно приводит только к увеличению неизрасходованных остатков. Запас недефицитного ресурса можно снизить на величину его остатка; это никаким образом не влияет на оптимальное решение (в том числе на оптимальные объемы производства и на прибыль), уменьшается только неизрасходованный остаток ресурса. Если запас недефицитного ресурса снизится на величину, превышающую его остаток, то для определения нового оптимального плана производства необходимо решать задачу заново.

В примере 2.1 увеличение запасов алюминия и пластмассы позволит увеличить прибыль. Запас стали можно снизить на 90 кг (т.е. до 160 кг); эти 90 кг стали предприятие может, например, продать или использовать в другом цехе. Например, если запас стали составит не 250, а только 200 кг, то оптимальное решение задачи будет следующим: х₁=4; х₂=24; х₃=0; х₄=50; х₅=0; Е=7600 ден. ед. Таким образом, оптимальное решение не изменится (кроме снижения неизрасходованного остатка стали).

Если запас стали снизится более чем на 90 кг (т.е. составит менее 160 кг), то для определения нового оптимального плана производства необходимо решать задачу заново. Для нового оптимального решения изменятся не только значения переменных, но и состав переменных в оптимальном базисе (т.е. в оптимальный базис будут входить не переменные х₁,х₂ и х₅ , а другие переменные). Значение целевой функции при этом снизится, т.е. составит менее 7600 ден. ед.

Ценность ресурсов

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

Примечание. Вместо названия «ценность ресурса» используются также названия «теневая цена», «скрытая цена».

Ценности ресурсов определяются по симплекс-таблице, соответствующей оптимальному решению. Ценности ресурсов представляют собой коэффициенты Е-строки при остаточных переменных, соответствующих остаткам ресурсов.

Для примера 2.1 ценность алюминия равна 1,33 ден. ед./кг, ценность пластмассы- 14,67 ден. ед./кг. Это означает, например, что увеличение запаса алюминия на единицу (т.е. на 1 кг) приводит к увеличению прибыли предприятия в среднем на 1,33 ден. ед. Например, если запас алюминия увеличится на 100 кг (т.е. составит 300 кг), то прибыль составит примерно 7600+1,33*100= 7733 ден. ед. Снижение запаса алюминия приведет к соответствующему снижению прибыли.

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

Ценность недефицитного ресурса всегда равна нулю. В данном примере ценность стали равна нулю, так как увеличение ее запаса не приводит к увеличению прибыли, а снижение (не более чем на 90 кг) - не приводит к снижению прибыли.

Ценность ресурса показывает максимальную (предельную) цену, по которой выгодно закупать ресурсы. Например, в рассматриваемой задаче предприятию выгодно закупать алюминий по цене не более 1,33 ден. ед./ кг, пластмассу — по цене не более 14,67 ден. ед./кг. Закупка ресурса по цене, превышающей его ценность, означает, что затраты предприятия на закупку ресурса превышают прибыль от его использования.

Порядок выполнения работы

1. Изучить теоретическую часть.

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

3. Провести анализ полученного решения на чувствительность.

2.4 Контрольные вопросы

1. Расскажите принцип работы симплекс-метода.

2. Перечислите основные этапы реализации симплекс-метода.

3. Что называется базисом?

4. Расскажите правила определения переменных для включения в базис и исключения из базиса.

5. Перечислите правила преобразования симплекс-таблицы.

6. Какой элемент симплекс-таблицы называется ведущим?

7. Что называется анализом оптимального решения на чувствительность?

8. Перечислите виды анализа решения на чувствительность и их основные положения.

Цель работы

1. Рассмотреть пример задачи линейного программирования: задача планирования производства.

2. Изучить принцип работы симплекс-метода.

3. Научиться определять начальное допустимое решение и оптимальное решения на основе симплекс-таблиц.

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

Теоретическое введение

2.2.1 Симплекс – (от лат. simplex – простой, математический), простейший выпуклый многогранник данного числа измерений n. При n = 3 трёхмерный симплекс представляет собой произвольный, в том числе неправильный, тетраэдр. Под двумерным симплексом понимают произвольный треугольник, а под одномерным - отрезок. Нульмерный симплекс есть просто одна точка.

n-мерный симпекс имеет n + 1 вершин, не принадлежащих ни к какому (n - 1)-мерному подпространству того Евклидова пространства (с числом измерений n или больше), в котором лежит данный симплекс. Обратно, всякие n + 1 точек евклидова n-мерного пространства R^m, m ³ n, не лежащие ни в каком подпространстве менее n измерений, однозначно определяют n-мepный симплекс с вершинами в заданных точках e₀, e₁,..., e_n, он может быть определён как выпуклое замыкание совокупности заданных n + 1 точек, т. е. как пересечение всех выпуклых тел пространства R^m, содержащих эти точки. Если в пространстве R^m дана система декартовых координат x₁, х₂,..., х_т, в которой вершина e_i, i = 0, 1,..., n, имеет координаты x₁⁽ⁱ⁾, x₂⁽ⁱ⁾,..., x_m ⁽ⁱ⁾, то симплекс с вершинами e₀, e₁,..., e_m состоит из всех точек пространства, координаты которых имеют вид:

,

k = 1,2,..., m, где m⁽⁰⁾, m⁽¹⁾,..., m^(п) - произвольные неотрицательные числа, дающие в сумме 1.

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

Любые r + 1 вершин, 0 £ r £ n - 1, взятые из числа данных n + 1 вершин n-мерного симплекса, определяют некоторый r-мерный симплекс. - r-мерную грань данного симплекса. Нульмерные грани симплекса называются вершинами, одномерные грани – ребрами.

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

Можно доказать, что экстремум (минимум иди максимум) целевой функции всегда достигается при значениях переменных х₁,х₂,…,х_n, соответствующих одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР.

Методика выполнения работы

2.2.2.1 Пример задачи линейного программирования: задача планирования производства

Одной из наиболее распространенных практических задач, решаемых методами линейного программирования, является задача планирования производства при ограниченных ресурсах. Основной метод решения задач линейного программирования – симплекс-метод – будет рассмотрен на примере решения такой задачи.

Пример 2.1.Один из цехов машиностроительного предприятия выпускает изделия из двух видов: корпуса и задвижки. Для производства этих изделий требуются три вида сырья: алюминий, сталь и пластмасса. На выпуск одного корпуса расходуется 20 кг алюминия, 10 кг стали и 5 кг пластмассы. На выпуск одной задвижки расходуется 5 кг алюминия, 5 кг стали и 20 кгпластмассы. Запасы ресурсов ограничены: за рабочую смену цех может израсходовать не более 200 кг алюминия, 250 кг стали и 500 кг пластмассы.

Выпуск одного корпуса приносит предприятию прибыль в размере 100 денежных единиц (ден. ед.), одной задвижки – 300 ден. ед.

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

Для построения математической модели задачи введем переменные. Обозначим через х₁ количество выпускаемых корпусов, через х₂ - количество выпускаемых задвижек.

Составим ограничение на расход алюминия. На выпуск одного корпуса расходуется 20 кг алюминия: значит, расход алюминия на выпуск всех корпусов составит 20х₁ кг. На выпуск задвижек будет израсходовано 5х₂ кг алюминия. Таким образом, общий расход алюминия составит 20х₁ + 5х₂ кг Эта величина не должна превышать 200 кг, так как цех не может израсходовать за смену свыше 200 кг алюминия. Поэтому можно записать следующее ограничение:

20х₁+5х₂ ≤ 200

Аналогично можно составить ограничение на расход стали:

10х₁+5х₂≤ 250

и на расход пластмассы:

5х₁+20х₂≤ 500

Кроме того, переменные х₁ и х₂ по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество изделий. Поэтому необходимо указать ограничения неотрицательности:

х₁≥ 0, х₂≥ 0.

В данной задаче требуется определить количество выпускаемых изделий, при котором прибыль от их производства будет максимальной. Прибыль от выпуска одного корпуса составляет 100 ден. ед.: значит, прибыль от выпуска корпусов составит 100х₁ ден. ед. Прибыль от выпуска задвижек составит 300х₂ ден. ед. Таким образом, общая прибыль от выпуска всех изделий составит 100х₁+300х₂ ден. ед. Требуется найти такие значения переменных х₁ и х₂ при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:

Е=100х₁+300х₂→max

Приведем полную математическую модель рассматриваемой задачи:

20х₁+5х₂≤ 200

10х₁+5х₂≤ 250(2.1)

5х₁+20х₂≤ 500

х₁≥ 0, х₂≥ 0

Е=100х₁+300х₂→max

Примечание. В данной задаче на переменные х₁ и х₂ накладывается также ограничение целочисленности: они должны принимать только целые значения, так как обозначают количество изделий. Если в результате решения задачи эти переменные примут дробные значения, то для получения целочисленного решения потребуется использовать специальные методы, рассматриваемые в лабораторной работе № 4.

Эту задачу можно решить также графическим методом. Решение показано на рис. 2.1.

Рис. 2.1. Решение примера 2.1 графическим методом

Найдем значения целевой функции для угловых точек ОДР:

Е(О) = 100*0+300*0 = 0,

Е(А) = 100*0 +300*25 = 7500,

Е(В) = 100*4 +300*24 = 7600,

Е(С) = 100*10+300*0 = 1000.

Таким образом, оптимальное решение находится в точке В = (4;24). Это означает, что цех должен выпускать за смену 4 корпуса и 24 задвижки. Прибыль при этом составит 7600 ден. ед.

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

Для решения задачи симплекс-методом требуется привести ее к стандартной форме, как показано в подразделе 1.2.2.3. Все ограничения задачи имеют вид «меньше или равно». Их необходимо преобразовать в равенства. Для этого требуется добавить в каждое ограничение дополнительную (остаточную) переменную. Математическая модель задачи в стандартной форме будет иметь следующий вид:

20х₁+5х₂+х₃=200

10х₁+5х₂+х₄=250 (2.2)

5х₁+20х₂+х₅=500

х_j≥ 0, j=1,…,5.

E=100х₁+300х₂→max

Здесь х₃,х₄,х₅- остаточные переменные. Их физический смысл будет показан в п. 2.2.2.4.

Принцип работы симплекс-метода

Принцип работы симплекс-метода состоит в следующем. Находится какое-либо допустимое решение, соответствующее одной из угловых точек ОДР. Проверяются смежные с ней угловые точки ОДР. Под смежной здесь понимается угловая точка, расположенная на той же границе ОДР, что и текущая угловая точка (для двухмерной ОДР - на той же стороне многоугольника, для трехмерной - на том же ребре многогранника, и т.д.). Если ни в одной из смежных угловых точек значение целевой функции не улучшается, то решение задачи завершается; текущая угловая точка ОДР соответствует оптимальному решению задачи. Если имеются смежные угловые точки ОДР, для которых значение целевой функции улучшается, то выполняется переход в ту из них, для которой достигается наиболее быстрое улучшение значения целевой функции. Для новой угловой точки ОДР процесс повторяется, т.е. проверяются смежные угловые точки. Перебор угловых точек происходит до тех пор, пока не будет найдено оптимальное решение, т.е. пока не будет достигнута угловая точка ОДР, для которой ни в одной из смежных точек значение целевой функции не улучшается.

Поиск решения на основе симплекс-метода реализуется с помощью симплекс-таблиц. Основные этапы реализации симплекс-метода следующие.

1. Задача линейного программирования приводится к стандартной форме.

2. Определя