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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

Пример решения задачи симплексным методом

Задача 1 (п.4.2).

Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком “плюс”, так как все неравенства имеют вид «≤».

Получим систему ограничений в виде:

,

,

,

.

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

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

i шаг. Основные переменные: х3, х4, х5, х6. неосновные переменные: х1, х2. Выразим основные переменные через неосновные:

 ,                                                (7)

Положив неосновные переменные равными нулю, т.е. х1 =0, х2 = 0, получим базисное решение х1= (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине О (0;0) многогранника ОАВСDЕ на рис. 2.

 

Рис. 2

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

При решении х1 значение функции равно . Легко понять, что функцию f можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение для f с положительным коэффициентом. Это можно осуществить, перейдя к такому новому допустимому базисному решению, в котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функций “лучше” (по крайней мере “не хуже”). В данном примере для увеличения f можно переводить в основные либо х1, либо х2, так как обе эти переменные входят в выражение дня f со знаком “плюс”. Для определенности в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х2 (такое правило выбора не всегда дает наименее трудоемкое решение, иногда имеет смысл провести предварительные специальные оценки).

Система (1) накладывает ограничения на рост переменной х2. поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными, то должны выполняться следующие неравенства (при этом х1 = 0 как неосновная переменная):

откуда  

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

Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом ∞. Обратите внимание, что при нулевом свободном члене и отрицательном коэффициенте при переводимой переменной уравнение ограничивает рост этой переменной нулем! (любое положительное ее значение вносит отрицательную компоненту в следующее базисное решение). Очевидно, что сохранение неотрицательности всех переменных (допустимость решения) возможно, если не нарушается ни одна из полученных во всех уравнениях границ. В данном примере наибольшее возможное значение для переменной х2 определяется как х2 =min (18/3; 16/1; 5/1; ∞} =5. при х2 =5 переменная х5 обращается в нуль и переходит в неосновные.

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

ii шаг. Основные переменные: х2, х34, х6. неосновные переменные: х1, х5.

Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для х2):

 

или

                                                                                   (8)

Второе базисное решение  является допустимым и соответствует вершине а (0;5) на рис. 2. Геометрическая интерпретация перехода от х1 к х2 — переход от вершины о к соседней вершине а на многоугольнике решений ОАBCDЕ.

Выразив линейную функцию через неосновные переменные на этом шаге, получаем:

 

Значение линейной функции f2 = f (х2) =15. изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной функции; в данном случае    

Однако значение f2 не является максимальным, так как повторяя рассуждения 1 шага, обнаруживаем возможность дальнейшего увеличения линейной функции за счет переменной х1, входящей в выражение для f с положительным коэффициентом. Система уравнений (8) определяет наибольшее возможное значение для х1: х1 = min{∞;3/1;11/2; ∞} = 3. второе уравнение является разрешающим, переменная х3 переходит в неосновные, при этом  

iii шаг. Основные переменные: х1, х2, х4, х6. неосновные переменные х3, х5.

Как и на ii шаге, выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для хi). после преобразований получаем:

,

,

,                                                                                (9)

.

Базисное решение х3 = (3; 5; 0; 5; 0; 12) соответствует вершине в (3;5). выражаем линейную функцию через неосновные переменные . Проверяем:  Третье допустимое базисное решение тоже не является оптимальным, поскольку при неосновной переменной х5 в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х5 в основную переменную. при определении наибольшего возможного значения для х5 следует обратить внимание на первое уравнение в системе (9), которое не дает ограничений на рост х5, так как свободный член и коэффициент при х5 имеют одинаковые знаки. Поэтому . Третье уравнение является разрешающим, и переменная х4 переходит в неосновные; .

iv шаг. Основные переменные: х1, х2, х5, х6. неосновные переменные: х3, х4.

После преобразований получим:

,

,

,

.

Базисное решение  соответствует вершине с (6; 4) на рис. 2.

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

Прибыль предприятия принимает максимальное значение 24 руб. при реализации 6 единиц продукции  и 4 единиц продукции  Дополнительные переменные х3, х4, х5, х6 показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптимальном плане производства , т.е. остатки ресурсов s1 и s2 равны нулю, а остатки, ресурсов s3 и s4 равны соответственно 1 и 3 единицам.

Метод искусственного базиса

Суть метода: в каждое уравнение, дающее отрицательную компоненту в базисном решении, вводим свою новую неотрицательную искусственную переменную у12,…, уk, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаем в число основных все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты базисного решения. Составляем новую линейную функцию  где м - произвольно большое число, и ищем ее максимум (т-задача). Назовём м-функцией выражение . Справедлива теорема:

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

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

3. Если Тmax= ∞, то исходная задача также неразрешима, причем либо fmax=∞, либо условия задачи противоречивы.

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



Поделиться:


Последнее изменение этой страницы: 2021-04-05; просмотров: 84; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.204.214.205 (0.031 с.)