XV Международная студенческая научная конференция Студенческий научный форум - 2023
Симплекс метод
КомментарииПолная версия работы доступна во вкладке "Файлы работы" в формате PDF
ВВЕДЕНИЕ
В математике взаимосвязь элементов множества, определяемая правилом, при котором каждое значение зависит от другого бесконечного числа величин, называется функцией. Для определения её крайних значений применяется линейное программирование. Решить поставленную задачу можно несколькими способами. Один из них — симплекс-метод.
1 Понятие о симплексном методе
Под симплексным методом понимается последовательный переход от одного базисного нахождения системы решений к другому. Эта перестановка повторяется до тех пор, пока переменная величина цели не достигнет своего наибольшего или наименьшего значения. Такой подход является универсальным, его можно использовать для решения любой задачи последовательного программирования.
Метод был разработан в 1947 году математиком из США Бернардом Данцигом. Предложенный способ оказался весьма эффективным для решения разнообразных землеустроительных и других экономических задач, связанных с оптимизацией использования ограниченных ресурсов. То есть он позволяет оценить и откорректировать параметры системы, а также получить качественные аналитические результаты. Универсальность данного метода проявляется в том, что он позволяет решать задачи различной размерности, в которых технико-экономические коэффициенты (αij) при переменных (Хij) выражены в разных единицах измерения.
В процессе решения задачи на каждой итерации осуществляется переход из одной вершины ОДР в смежную, связанную с не худшим значением целевой функции. Для этого используется процедура метода главных элементов. Количество итераций, необходимых для получения оптимального решения, находится в пределах от m до 2m, где m-количество ограничений в задаче.
2 Двухфазный симплекс-метод
Если в условии задачи линейного программирования не все ограничения представлены неравенствами типа «≤», то далеко не всегда нулевой вектор будет допустимым решением. Однако каждая итерация симплекс-метода является переходом от одной вершины к другой, и если неизвестно ни одной вершины, алгоритм вообще не может быть начат.Такой метод можно использовать, когда свободные члены уравнений являются любыми числами.
Процесс нахождения исходной вершины не сильно отличается от однофазного симплекс-метода, однако может в итоге оказаться сложнее, чем дальнейшая оптимизация.
3 Алгоритм решения задач
Алгоритм решения задачи линейного программирования симплекс методом следующий:
1. При постановке задачи формулируется: оптимальные значения, каких неизвестных необходимо найти, при каких условиях (ограничениях) по видам и размерам ресурсов, какая функция цели и на что она ориентирована (на максимум или минимум).
Например, необходимо определить оптимальное сочетание объемов производства трех видов продукции (Х1, Х2, Х3) при имеющихся в хозяйстве трех видах ресурсов в размере в1=100, в2=40, в3=50 -это трудовые ресурсы с целью получения максимальной денежной выручки.
Экономико-математическая модель в симплексном методе составляется в следующей последовательности:
2. записывается уравнение функции цели, правая часть которого представляет собой сумму произведений искомых неизвестных (Х1, Х2, Х3) на соответствующие им по условиям задачи коэффициенты целевой функции:
Zmax =20Х1+10Х2+30Х3
3. условия задачи записываются в виде неравенств с ограничениями типа ≤. Каждое из неравенств выражает собой ограничения по одному из видов ресурсов, поэтому в левой части неравенства проставляют искомые переменные с коэффициентами, выражающими расход данного вида ресурса на единицу искомой переменной или, наоборот, выход данного вида ресурса с единицы соответствующей переменной. В правой части неравенства проставляется тип ограничения ≤ и величина соответствующего вида ресурса;
4. количество неравенств в системе ограничений обусловлено условиями задачи. При записи неравенств необходимо контролировать правильность их оформления: технико-экономические коэффициенты при переменных, состав переменных (в левой части неравенства), вид и размер ресурса (в правой части неравенства) должны строго соответствовать условиям задачи и характеру её постановки.
Таким образом, система ограничений выглядит следующим образом:
3Х1+5Х2+8Х3≤100
2,5Х1+3Х2+6Х3≤40
2Х1+4Х2+3Х3≤50
5. после записи основных условий задачи в виде системы ограничений обязательно формулируется условие не отрицательности переменных, так как алгоритм симплексного метода позволяет решать задачи только с положительными значениями переменных (Хj):
Х1≤0; Х2≤0; Х3≤0.
6. Представленная выше форма записи условий задачи в виде неравенств называется стандартной. Для заполнения первой симплексной таблицы (исходного плана) необходимо перейти от стандартной формы записи условий задачи к канонической, а от неё – к симплексной.
Каноническая форма записи условий задачи предусматривает преобразование неравенств (стандартной формы записи) в уравнения, для этого в левую часть каждого из неравенств вводят дополнительные переменные со следующими знаками: с плюсом, если неравенство типа « ≤ » и с минусом, если неравенство типа « ≥ ». Дополнительным переменным (Х4, Х5, Х6) поочередно присваиваются номера, продолжающие нумерацию основных переменных (Х1, Х2, Х3). В уравнение дополнительные переменные вводятся с коэффициентом 1, а в целевую функцию с нулевыми коэффициентами для исключения их влияния на результаты решения задачи.
Преобразуем приведенную выше систему неравенств в систему уравнений:
3Х1+5Х2+8Х3+Х4≤100
2,5Х1+3Х2+6Х3+Х5≤40
2Х1+4Х2+3Х3+Х6≤50
7. Для дальнейшего преобразования канонической формы записи в симплексную система уравнений решается относительно дополнительных переменных:
Х4=100-(3Х1+5Х2+8Х3)
Х5=40-(2,5Х1+3Х2+6Х3)
Х6=50-(2Х1+4Х2+3Х3)
8. Исходя из симплексной формы записи условий задачи, становится ясен экономический смысл дополнительных переменных. На начальном этапе решения задачи принимается условие, что основные переменные равны нулю, а значения дополнительных переменных, исходя из симплексной формы записи, будут равны величинам ресурсов. В нашем примере: при Х1=0, Х2=0, Х3=0 будем иметь Х4=100, Х5=40, Х6=50.
В экономическом отношении это означает, что пока не реализовано ни одно из мероприятий, намечаемых по условиям задачи, ресурсы остаются неиспользованными. Исходя из данной установки, создается исходный базис, на основе которого начинается поиск оптимального решения задачи из числа допустимых её решений.
9. Если при решении отыскивается ответ с максимумом или минимумом линейной формы и все неосновные переменные получаются только положительными, то задача считается выполненной.
10. Если найденный максимум (минимум) линейной формы в функции имеет одну или несколько неосновных переменных с отрицательными коэффициентами, необходимо перейти к новому базисному решению.
11. Из переменных, входящих в форму с отрицательными или положительными коэффициентами, выбирается наибольшая (по модулю) и переводится в основные.
12. Другими словами, указывается оптимальное опорное решение, способ перехода от одного нахождения ответа к другому, варианты улучшения расчётов. После нахождения первоначального решения с «единичным базисом» вычисляется оценка разложения векторов по базису и заполняется симплексная таблица 1.
Таблица 1 –Первая симплексная таблица
|
Номера строк (ограниче-ний), i |
Номера переменных, вошедших в базис, Xn+i |
Коэффициенты целевой функции при базисной переменной, Сi |
Свободные члены (ресурсы),вi |
Коэффициенты целевой функции, Сj |
Сумма по строке |
Отношение
|
||||||||
|
20 |
10 |
30 |
0 |
0 |
0 |
|||||||||
|
Коэффи-циенты при небазисных переменных |
Коэффициенты при базисных переменных |
|||||||||||||
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|||
|
1 |
Х4 |
0 |
100 |
3 |
5 |
8 |
1 |
0 |
0 |
117 |
12,5 |
|||
|
2 |
Х5 |
0 |
40 |
25 |
3 |
6 |
0 |
1 |
0 |
52,5 |
6,67 |
|||
|
3 |
Х6 |
0 |
50 |
2 |
4 |
3 |
0 |
0 |
1 |
60 |
16,67 |
|||
|
m+1 |
Zj-Cj |
0 |
-20 |
-10 |
-30 |
0 |
0 |
0 |
-60 |
|
||||
Столбцы 5-7 – это столбцы основных переменных (соответственно, Х1, Х2, Х3). Из первого уравнения 3Х1+5Х2+8Х3+Х4=100 коэффициенты при основных переменных (Х1, Х2, Х3), соответственно 3,5 и 8 занесены в столбцы данных переменных по первой строке таблицы и так далее.
Столбцы 8-10 – это столбцы дополнительных переменных (Х4, Х5, Х6), в которых проставляются коэффициенты при данных переменных по каждому уравнению, в которое входит соответствующая переменная. Так, дополнительная переменная Х4 входит в первое уравнение с коэффициентом 1, поэтому данный коэффициент записываем. В остальных столбцах дополнительных переменных Х5 и Х6 по первой строке проставляем нули, т.к. данные дополнительные переменные не входят в первое уравнение.
Столбец 11 – в него записывается суммы, полученные путем сложения свободного члена (вj) и коэффициентов (аij) по соответствующей строке таблицы. Так, если сложить по первой строке таблицы свободный член и коэффициенты (100+3+5+8+1=117), то получим число 117. Аналогичным образом получаем значения для других.
Столбец 12 – в него записываются значения, полученные в результате построчного деления значений свободных членов (вj) на положительные коэффициенты ключевого (k-го) столбца.
Для выполнения таких расчетов необходимо предварительно выбрать ключевой столбец (k–й столбец). В качестве ключевого (k-го) выбирается столбец (из числа столбцов основных переменных Х1, Х2, Х3, по которому в индексной (m+n) строке таблицы стоит максимальное по абсолютной величине: отрицательное число при решении задачи на максимум и, наоборот, положительное число, при решении задачи на минимум. В данной задаче таким максимальным по абсолютной величине числом является -30 (т.к. Z→max).
Теперь можно выполнить расчеты для заполнения столбца 12. По первой строке указанное отношение получаем, разделив свободный член 100 (в1=100) на положительный коэффициент 8 (в1=8), стоящий по данной строке в ключевом столбце. Оно равно 12,5 ( ).
Столбец m+1 – это индексная строка симплексной таблицы. На ней записывается численное значение функции цели (Z). В первой симплексной таблице оно равно нулю (Z=0).
Все остальные элементы индексной (m+1) строки рассчитываются по формуле:
13. Анализ плана на оптимальность
Признаком оптимальности опорного плана является отсутствие в индексной (m+1) строке при решении задачи на минимум – положительных коэффициентов или нулей. Если это условие не выполняется, то план не оптимален и необходимо его улучшать.
Новую симплексную таблицу (улучшенный план) с новым базисным решением составляют в следующей последовательности:
Вместо базисной переменной, стоявшей в базисе (столбец 2) по ключевой l-строке предыдущей таблицы в новую таблицу записывают переменную Хj, столбец которой выбран в качестве ключевого. Этим самым в базис новой симплексной таблицы вводится новая базисная переменная, а прежняя – выводится из базиса;
- в столбец 3, рядом с новой переменной, введенной в базис, записывают её коэффициент целевой функции. Остальные базисные переменные и их коэффициенты целевой функции (столбцы 2 и 3) переписываются в новую таблицу из предыдущей без изменения;
- элементы ( ) для заполнения в новой таблице строки, стоящей на месте ключевой l-строки предыдущей таблицы, вычисляются как отношение соответствующего элемента (alj) ключевой l-строки на главный элемент (alk) предыдущей таблицы, т.е. по формуле:
- элементы остальных строк новой симплексной таблицы, за исключением строки, стоящей на месте бывшей ключевой l-строки, пересчитываются по одной из следующих формул:
, ( )
де , аij – однотипные коэффициенты, соответственно новой и предыдущей симплексной таблиц;
, аlj – коэффициенты строки, стоящей в новой таблице на месте бывшей ключевой l-строки и, соответственно, коэффициенты ключевой l-строки в предыдущей таблице;
aik – коэффициенты ключевого К-столбца предыдущей симплексной таблицы;
alk – главный (генеральный) элемент предыдущей симплексной таблицы, стоящий на пересечении ключевых l-строки и К-столбца.
Расчеты по указанным выше формулам выполняются для заполнения всех строк новой симплексной таблицы, включая индексную (m+1) строку, но исключая ключевую l-строку.
Таким образом получаем оптимальный план, представленный на таблице 3.
Таблица 2 - Вторая симплексная таблица
|
i |
Базис, Xn+i |
Сi |
вi |
20 |
10 |
30 |
0 |
0 |
0 |
Сумма по строке
|
Контроль |
|
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
1 |
Х4 |
0 |
46,66 |
-0,333 |
1 |
0 |
1 |
-1,333 |
0 |
47,00 |
- |
47,00 |
|
2 |
Х3 |
30 |
6,667 |
0,417 |
0,5 |
1 |
0 |
0,167 |
0 |
8,751 |
15,86 |
8,751 |
|
3 |
Х6 |
0 |
30 |
0,750 |
2,5 |
0 |
0 |
-0,5 |
1 |
33,750 |
40 |
33,750 |
|
m+1 |
|
|
200 |
-7,5 |
5 |
0 |
0 |
5 |
0 |
202,500 |
- |
202,500 |
Таблица 3 - Третья симплексная таблица
|
i |
Базис, Xn+i |
Сi |
вi |
20 |
10 |
30 |
0 |
0 |
0 |
Сумма по строке
|
Контроль |
|
|
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|
1 |
Х4 |
0 |
51,990 |
0 |
1,399 |
0,799 |
1 |
-1,199 |
0 |
53,989 |
|
53,989 |
|
2 |
Х1 |
20 |
15,988 |
1 |
1,199 |
2,398 |
0 |
0,400 |
0 |
20,985 |
|
20,985 |
|
3 |
Х6 |
0 |
18,010 |
0 |
1,600 |
-1,799 |
0 |
-0,799 |
1 |
18,012 |
|
18,012 |
|
m+1 |
|
|
319,909 |
0 |
13,993 |
17,985 |
0 |
8,003 |
0 |
359,890 |
|
359,890 |
14. Контроль правильности задачи должен осуществляться на всех этапах её решения: от составления экономико-математической модели задачи до анализа оптимального её решения.
В порядке осуществления текущего контроля правильности решения задачи и исключения «зацикливания», в поиске оптимального её решения необходимо иметь в виду следующее:
- если в ключевом К - столбце все коэффициенты (aik) отрицательные, то решения задачи не существует;
- если в столбце свободных членов (ресурсов) имеются нули, то при последующем решении задачи может произойти зацикливание (вырождение). Для преодоления вырожденности плана нули заменяют на малые положительные числа, не оказывающие влияния на результаты решения задачи;
Если перечисленные условия контроля соблюдены, то это гарантирует получение оптимального решения задачи. Контроль оптимального плана осуществляется в процессе его анализа.
4 Модификация ограничений
Все ограничения задачи модифицируются согласно следующим правилам:
ограничения типа «≤» переводятся на равенства созданием дополнительной переменной с коэффициентом «+1». Эта модификация проводится и в однофазном симплекс-методе, дополнительные переменные в дальнейшем используются как исходный базис.
ограничения типа «≥» дополняются одной переменной с коэффициентом «−1». Поскольку такая переменная из-за отрицательного коэффициента не может быть использована в исходном базисе, необходимо создать ещё одну, вспомогательную, переменную. Вспомогательные переменные всегда создаются с коэффициентом «+1».
ограничения типа «=» дополняются одной вспомогательной переменной.
Соответственно, будет создано некоторое количество дополнительных и вспомогательных переменных. В исходный базис выбираются дополнительные переменные с коэффициентом «+1» и все вспомогательные.
ЗАКЛЮЧЕНИЕ
Симплекс-метод позволяет эффективно найти оптимальное решение, избегая простой перебор всех возможных угловых точек. Основной принцип метода: вычисления начинаются с какого-то «стартового» базисного решения, а затем ведется поиск решений, «улучшающих» значение целевой функции. Это возможно только в том случае, если возрастание какой-то переменной приведет к увеличению значения функционала.
СПИСОК ЛИТЕРАТУРЫ
Симплексный метод решения задач линейного программирования [Электронный ресурс]// Информационный ресурс studopedia – Режим доступа: https://studopedia.ru/22_110893_simpleksniy-metod-resheniya-zadach-lineynogo-programmirovaniya.html/, свободный - Загл. с экрана.
Метод симплекса [Электронный ресурс]// Информационный ресурс nauka – Режим доступа: https://nauka.club/matematika/metod-simpleksa.html/, свободный - Загл. с экрана.
Симплекс-метод [Электронный ресурс]// Информационный ресурс wikipedia – Режим доступа: https://ru.wikipedia.org/wiki/Симплекс-метод/, свободный - Загл. с экрана.
Подробный разбор симплекс-метода [Электронный ресурс]// Информационный ресурс habr – Режим доступа: https://habr.com/ru/post/474286/, свободный - Загл. с экрана.