Рассмотрим симплекс -метод
для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
- Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 0 , т.к. целевая функция не должна при этом менять свой экономический смысл.
- Выписываются вектора P i из коэффициентов при переменных и столбца свободных членов. Этим действием определяется количество единичных векторов. Правило – единичных векторов должно быть столько, сколько неравенств в системе ограничений.
- После этого исходные данные вводятся в симплекс-таблицу. В базис вносятся единичные вектора, и исключая их из базиса, находят оптимальное решение . Коэффициенты целевой функции записывают с противоположным знаком.
- Признак оптимальности для задачи ЛП – решение оптимально, если в f – строке все коэффициенты положительны. Правило нахождения разрешающего столбца – просматривается f – строка и среди ее отрицательных элементов выбирается наименьшее. Вектор P i его содержащий становится разрешающим. Правило выбора разрешающего элемента – составляются отношения положительных элементов разрешающего столбца к элементам вектора Р 0 и то число, которое дает наименьшее отношение становится разрешающим элементом, относительно которого будет произведен пересчет симплекс-таблицы. Строка, содержащая этот элемент называется разрешающей строкой. Если в разрешающем столбце нет положительных элементов, то задача не имеет решения. После определения разрешающего элемента переходят к пересчету новой симплекс – таблицы.
- Правила заполнения новой симплекс – таблицы. На месте разрешающего элемента проставляют единицу, а другие элементы полагают равными 0 . Разрешающий вектор вносят в базис, из которого исключают соответствующий нулевой вектор, а остальные базисные вектора записывают без изменений. Элементы разрешающей строки делят на разрешающий элемент, а остальные элементы пересчитывают по правилу прямоугольников.
- Так поступают до тех пор, пока в f – строке все элементы не станут положительными.
Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:
Приводим задачу к каноническому виду:
Составляем вектора:
Заполняем симплекс – таблицу:
:
Пересчитаем первый элемент вектора Р 0
, для чего составляем прямоугольник из чисел: и получаем: 
.
Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:
В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:
Отсутствие отрицательных элементов в f
– строке означает, что найден оптимальный план
:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
- Ашманов С. А. Линейное программирование, М: Наука, 1998г.,
- Вентцель Е.С. Исследование операций, М: Советское радио, 2001г.,
- Кузнецов Ю.Н., Кузубов В.И., Волошенко А.Б. Математическое программирование, М: Высшая школа, 1986г.
Решение линейного программирования на заказ
Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на
Основные теоремы линейного программирования
Для обоснования методов решения задач линейного программирования сформулируем ряд важнейших теорем, опуская их аналитические доказательства. Уяснить смысл каждой из теорем поможет понятие о геометрической интерпретации решения ЗЛП, данное в предыдущем подразделе.
Однако сначала напомним о некоторых понятиях, важных с точки зрения дальнейшего разговора.
Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными , если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные m-n переменных называются неосновными (или свободными) .
Базисным решением системы m линейных уравнений c n переменными (m < n) называется всякое ее решение, в котором все неосновные переменные имеют нулевые значения.
Теорема 1 . Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
В частном случае, когда в систему ограничений входят только две переменные x 1 и x 2 , это множество можно изобразить на плоскости. Так как речь идет о допустимых решениях (x 1 , x 2 ≥ 0), то соответствующее множество будет располагаться в первой четверти декартовой системы координат. Это множество может быть замкнутым (многоугольник), незамкнутым (неограниченная многогранная область), состоять из единственной точки и, наконец, система ограничений-неравенств может быть противоречивой.
Теорема 2 . Если задача линейного программирования имеет оптимальное решение, то оно совпадает с одной (двумя) из угловых точек множества допустимых решений.
Из теоремы 2 можно сделать вывод о том, что единственность оптимального решения может нарушаться, причем, если решение не единственное, то таких оптимальных решений будет бесчисленное множество (все точки отрезка, соединяющего соответствующие угловые точки).
Теорема 3 . Каждому допустимому базисному решению задачи линейного программирования соответствует угловая точка области допустимых решений, и наоборот.
Следствием из теорем 2 и 3 является утверждение о том, что оптимальное решение (оптимальные решения) задачи линейного программирования, заданной (или приведенной) ограничениями-уравнениями, совпадает с допустимым базисным решением (допустимыми базисными решениями) системы ограничений.
Таким образом, оптимальное решение ЗЛП следует искать среди конечного числа допустимых базисных решений.
Симплекс-метод был разработан и впервые применен для решения задач в 1947 г. американским математиком Дж. Данцигом.
Симплексный метод в отличие от геометрического универсален. С его помощью можно решить любую задачу линейного программирования.
В основу симплексного метода положена идея последовательного улучшения получаемого решения.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений к соседней, в которой целевая функция принимает лучшее (или, по крайней мере, не худшее) значение до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Таким образом, имея систему ограничений, приведенную к канонической форме (все функциональные ограничения имеют вид равенств), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще. Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то осуществляется переход к другому, обязательно допустимому базисному решению. Симплексный метод гарантирует, что при этом новом решении целевая функция, если и не достигнет оптимума, то приблизится к нему (или, по крайней мере, не удалится от него). С новым допустимым базисным решением поступают так же, пока не отыщется решение, которое является оптимальным.
Процесс применения симплексного метода предполагает реализацию трех его основных элементов:
1) способ определения какого-либо первоначального допустимого базисного решения задачи;
2) правило перехода к лучшему (точнее, не худшему) решению;
3) критерий проверки оптимальности найденного решения.
Симплексный метод включает в себя ряд этапов и может быть сформулирован в виде четкого алгоритма (четкого предписания о выполнении последовательных операций). Это позволяет успешно программировать и реализовывать его на ЭВМ. Задачи с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Реализация симплекс-алгоритма включает восемь шагов. Опишем их, параллельно рассматривая пример выполнения каждого шага в применении к задаче о хоккейных клюках и шахматных наборах.
Шаг 1 . Формулировка ЗЛП (формирование целевой функции и системы ограничений).
Читайте также:
|
Теорема (о выборе разрешающего элемента)
Если в нескольких столбцах z-ой строке есть отрицательные элементы, то разрешающим столбцом нужно выбрать тот столбец у которого максимально произведение абсолютного значения коэффициента в z-ой строке и минимально симплексное отношение данном столбце.
Доказательство:
Пусть разрешающим будет элемент . В результате шага модифицированных жордановых исключений свободным членом в z-строке будет число , равное .Поскольку и ,скобка в этом выражении всегда будет положительной. А так как значение функционала всегда равно свободному члену, эта скобка представляет собой тот добавок к функционалу, который получается в результате сделанного шага.
Чем большее приращение будет получать функционал на каждом шаге, тем меньше потребуется шагов (т.е. вычислений) для достижения оптиума. Величина этого приращения зависит от абсолютной величины коэффициента и от величины наименьшего симплексного отношения . То есть разрешающим столбцом будет столбец, у которого максимально это произведение.
Пример: линейное программирование:
Найдем максимум функции
при ограничениях
Решение: составим жорданову таблицу.
Поскольку в ней свободные члены положительны, план является опорным. Однако он не оптимален, так как коэффициенты z-строки отрицательны. Выбираем из них тот, у которого наибольшее произведение абсолютной величины и наименьшее симплексное отношение. Третий столбец считаем разрешающим, так как он имеет наибольшую абсолютную величину 8 и симплексные отношения: соответственно ( , поэтому элемент 1 в третьим столбце будет разрешающим). Делаем шаг модифицированных жордановых исключений и приходим к следующей таблице.
Судя по коэффициентам z-строки, в полученной таблице оптимальное решение не достигнуто. Берём второй столбец с отрицательным коэффициентом в z-строке за разрешающий (разрешающей строкой может быть только первая). С найденным элементом 5 делаем следующий шаг.
В z-строке все коэффициенты положительны, план, получаемый приравниванием верхних переменных нулю, а боковых – свободным членам, оптимален. Выписываем из таблицы значения основных неизвестных: Максимальное значение функционала считаем в последней клетке таблицы:
В окончательной таблице все определители неотрицательны. Это говорит о том, что при значениях неизвестных функционал достигает максимума
Обычно предполагается, что на множестве планов задачи нет точек, в которых знаменатель целевой функции равен нулю. Без ограничения общности, можно считать, что .
В задаче дробно-линейного программирования экстремум целевой функции достигается в вершине многогранника решений. Это сходство с линейным программированием позволяет решать дробно-линейные задачи методом Штифеля.
Вычисления оформляются в виде жордановых таблиц. При этом для функционала отводятся две нижние строки: в первую из них записываем коэффициенты числителя, а во вторую – знаменателя. Исходной задаче соответствует таблица 1:
| –x 1 | –x 2 | … | –x j | … | –x n | ||
| y 1 | a 11 | a 12 | … | a 1 j | … | a 1 n | a 1 |
| … | ……………………………………… | … | |||||
| y i | a i 1 | a i 2 | … | a ij | … | a in | a i |
| … | ……………………………………… | … | |||||
| y m | a m 1 | a m 2 | … | a mj | … | a mn | a m |
| z 1 | –p 1 | –p 2 | … | –p j | … | –p n | |
| z 2 | –q 1 | –q 2 | … | –q j | … | –q n |
Через y i обозначаются разности между правыми и левыми частями системы ограничений:
y i = a i – a i 1 x 1 – a i 2 x 2 – a i 3 x 3 – … – a in x n ³ 0.
Свободными переменными мы будем называть переменные, расположенные в верхней заглавной строке жордановой таблицы. Придавая свободным переменным нулевые значения, мы получим исходное базисное решение: . Данный вектор не может являться опорным планом, т.к. знаменатель целевого функционала на нем равен нулю (z 2 = 0). Поэтому среди свободных членов системы ограничений a 1 ,…, a m обязательно есть отрицательные числа (иначе базисное решение было бы опорным планом).
Шагами модифицированных жордановых исключений, точно так же, как при решении задачи линейного программирования (см. ), отыскиваем первоначальный план задачи. В результате k шагов мы приходим к таблице 2:
| –y 1 | … | –x j | … | –x n | ||
| x 1 | b 11 | … | b 1 j | … | b 1 n | b 1 |
| .… | ……………………………………… | |||||
| y i | b i 1 | … | b ij | … | b in | b i |
| …. | ……………………………………. | |||||
| y m | b m 1 | … | b mj | … | b mn | b m |
| z 1 | f 1 | … | f j | … | f n | F |
| z 2 | g 1 | … | g j | … | g n | G |
В таблице 2 все свободные члены b i неотрицательны, что обеспечивает неотрицательность базисных переменных x 1 ,…, y m . Кроме того (в силу положительности знаменателя целевой функции z 2 на множестве опорных планов). Первоначальным опорным планом является вектор с координатами . Значение целевой функции на первоначальном опорном плане равно .
Заметим, что если на одном из шагов жордановых исключений какой-либо из свободных членов b i окажется отрицательным, а все остальные элементы i -й строки будут неотрицательными, то задача не будет иметь решения из-за отсутствия планов.
Проследим за тем, как меняется целевая функция при переходе от одного опорного плана задачи к другому. Оказывается, знак разности между новым и старым значениями функции совпадает со знаком определителя . Если. Т.к. многогранник решений содержит лишь конечное число опорных планов, то за конечное число шагов мы придем к оптимальному опорному плану.
Этому процессу может помешать только неограниченность многогранника решений. В этом случае целевая функция может иметь так называемый асимптотический экстремум (в данном случае – максимум). Асимптотическим максимумом задачи дробно-линейного программирования называется точная верхняя грань целевой функции на множестве планов, которая не достигается ни на одном из планов. В том случае, когда задача имеет асимптотический максимум, в области планов всегда можно найти такой план (не опорный), на котором целевая функция принимает значение сколь угодно близкое к асимптотическому максимуму.
Метод Штифеля позволяет находить не только максимум, но и асимптотический максимум задачи дробно-линейного программирования. Рассмотрим более подробно переход от плана к плану и выясним. Выбирая разрешающий элемент в j -м столбце, мы должны руководствоваться принципом минимального симплексного отношения. Т.е. разрешающий элемент в j -м столбце должен попасть в ту строку, для которой симплексное отношение положительно и минимально.
Т.к. после нахождения первоначального опорного плана все правые части b i стали неотрицательными, то разрешающим элементом j -го столбца может быть один из его положительных элементов (). Если на каждом шаге этапа поиска оптимального опорного плана в выбранном разрешающем столбце присутствует (хотя бы один) положительный элемент , то такая задача имеет максимум (возможно, что не один).
Однако, если на одном из шагов некоторая оценка меньше нуля, и при этом все элементы j -го столбца . Тогда в данном столбце, руководствуясь принципом минимального симплексного отношения, разрешающий элемент выбирать нельзя. Увеличивая значения свободной переменной x j от 0 и до (см. Табл. 2), мы все время остаемся в области планов. Это связано с тем, что увеличение переменной x j не вызывает изменения знака на минус ни у одной из базисных переменных.
Обозначим через М предел, к которому, монотонно возрастая, стремится целевая функция при : . Это число является асимптотическим максимумом.
| 2 |
. Алгоритм симплекс-метода
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
Решение:
I итерация:
х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:
Приведем целевую функциюк следующему виду:
На основе полученной задачи сформируем исходную симплекс-таблицу:
Таблица 5.3
Исходная симплекс-таблица
Оценочные отношения |
||||
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
6 этап: проверка оптимальности.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
Таблица 5.4
Исходная симплекс-таблица
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.
9.1. Преобразование разрешающего элемента.
Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:
Полученный результат вписываем в аналогичную клетку таблицы 5.5.
9.2. Преобразование разрешающей строки.
Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.
9.3. Преобразование разрешающей колонки.
Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.
9.4. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:
«х3 »: .
Аналогично преобразуются значения других клеток:
«х3 х1 »: ;
«х4
»: 
;
«х4 х1 »: ;
«х6
»: 
;
«х6 х1 »: ;
«»: 
;
«х1
»: 
.
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
II итерация:
1 этап: составление симплекс-таблицы.
Таблица 5.5
Симплекс-таблица II итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):
Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.6
Симплекс-таблица II итерации
Оценочные отношения |
||||
3/1=3 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.
III итерация
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.7
Симплекс-таблица III итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.8, минимальным является отношение, соответствующее строке «х4 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.8
Симплекс-таблица III итерации
Оценочные отношения |
||||
5/5=1 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.
IV итерация
1 этап: построение новой симплекс-таблицы.
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.9
Симплекс-таблица IV итерации
Оценочные отношения |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.9) нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
7 этап: проверка альтернативности решения.
Найденное решение является единственным, так как в строке целевой функции (таблица 5.9) нет нулевых элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.
Пример 5.2. Решить вышеприведенную задачу линейного программирования при условии, что целевая функция минимизируется:
Решение:
I итерация:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.
Рассмотрим решение ЗЛП симплекс-методом и изложим ее применительно к задаче максимизации.
1. По условию задачи составляется ее математическая модель.
2. Составленная модель преобразовывается к канонической форме. При этом может выделиться базис с начальным опорным планом.
3. Каноническая модель задачи записывается в форме симплекс-таблицы так, чтобы все свободные члены были неотрицательными. Если начальный опорный план выделен, то переходят к пункту 5.
Симплекс таблица: вписывается система ограничительных уравнений и целевая функция в виде выражений, разрешенных относительно начального базиса. Строку, в которую вписаны коэффициенты целевой функции F, называют F-строкой или строкой целевой функции.
4. Находят начальный опорный план, производя симплексные преобразования с положительными разрешающими элементами, отвечающими минимальным симплексным отношениям, и не принимая во внимание знаки элементов F-строки. Если в ходе преобразований встретится 0-строка, все элементы которой, кроме свободного члена, нули, то система ограничительных уравнений задачи несовместна. Если же встретится 0-строка, в которой, кроме свободного члена, других положительных элементов нет, то система ограничительных уравнений не имеет неотрицательных решений.
Приведение системы (2.55), (2.56) к новому базису будем называть симплексным преобразованием. Если симплексное преобразование рассматривать как формальную алгебраическую операцию, то можно заметить, что в результате этой операции происходит перераспределение ролей между двумя переменными, входящими в некоторую систему линейных функций: одна переменная из зависимых переходит в независимые, а другая наоборот - из независимых в зависимые. Такая операция известна в алгебре под названием шага жорданова исключения.
5. Найденный начальный опорный план исследуется на оптимальность:
а) если в F-строке нет отрицательных элементов (не считая свободного члена), то план оптимален. Если при этом нет и нулевых, то оптимальный план единственный; если же есть хотя бы один нулевой, то оптимальных планов бесконечное множество;
б) если в F-строке есть хотя бы один отрицательный элемент, которому соответствует столбец неположительных элементов, то <
в) если в F-строке есть хотя бы один отрицательный элемент, а в его столбце есть хотя бы один положительный, то можно перейти к новому опорному плану, более близкому к оптимальному. Для этого указанный столбец надо назначить разрешающим, по минимальному симплексному отношению найти разрешающую строку и выполнить симплексное преобразование. Полученный опорный план вновь исследовать на оптимальность. Описанный процесс повторяется до получения оптимального плана либо до установления неразрешимости задачи.
Столбец коэффициентов при переменной, включаемой в базис, называют разрешающим. Таким образом, выбирая переменную, вводимую в базис (или выбирая разрешающий столбец) по отрицательному элементу F-строки, мы обеспечиваем возрастание функции F.
Немного сложней определяется переменная, подлежащая исключению из базиса. Для этого составляют отношения свободных членов к положительным элементам разрешающего столбца (такие отношения называют симплексными) и находят среди них наименьшее, которое и определяет строку (разрешающую), содержащую исключаемую переменную. Выбор переменной, исключаемой из базиса (или выбор разрешающей строки), по минимальному симплексному отношению гарантирует, как уже установлено, положительность базисных компонент в новом опорном плане.
В пункте 3 алгоритма предполагается, что все элементы столбца свободных членов неотрицательны. Это требование не обязательно, но если оно выполнено, то все последующие симплексные преобразования производятся только с положительными разрешающими элементами, что удобно при расчетах. Если в столбце свободных членов есть отрицательные числа, то разрешающий элемент выбирают следующим образом:
1) просматривают строку, отвечающую какому-либо отрицательному свободному члену, например t-строку, и выбирают в ней какой-либо отрицательный элемент, а соответствующий ему столбец принимают за разрешающий (предполагаем, что ограничения задачи совместны);
2) составляют отношения элементов столбца свободных членов к соответствующим элементам разрешающего столбца, имеющим одинаковые знаки (симплексные отношения);
3) из симплексных отношений выбирают наименьшее. Оно и определит разрешающую строку. Пусть ею будет, например, р -строка;
4) на пересечении разрешающих столбца и строки находят разрешающий элемент. Если разрешающим оказался элемент y-строки, то после симплексного преобразования свободный член этой строки станет положительным. В противном случае на следующем шаге вновь обращаются к t-строке. Если задача разрешима, то через некоторое число шагов в столбце свободных членов не останется отрицательных элементов.
Нахождение исходного опорного плана, канонический вид ЗЛП
Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования - симплексного метода или метода последовательного улучшения плана.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений (называемой первоначальной) к соседней, в которой линейная функция принимает лучшее (по крайней мере, не худшее) значение по отношению к цели задачи; до тех пор, пока не будет найдено оптимальное решение - вершина, где достигается оптимальное значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода были разработаны российским ученым Л.В. Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного улучшения решения - необходимо освоить три основных элемента:
Способ определения какого-либо первоначального допустимого базисного решения задачи;
Правило перехода к лучшему (точнее, не худшему) решению;
Критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду, т.е. система ограничений должна быть представлена в виде уравнений.
В литературе достаточно подробно описываются: нахождение начального опорного плана (первоначального допустимого базисного решения), тоже - методом искусственного базиса, нахождение оптимального опорного плана, решение задач с помощью симплексных таблиц.
58. Основная теорема симплекс метода.
???????????????????????????????????????????????????????????????????????
59. Альтернативный оптимум в ЗЛП, вырожденность в ЗЛП.
Вырожденность в задачах линейного программирования
Рассматривая симплекс-метод, мы предполагали, что задача линейного программирования является невырожденной, т.е. каждый опорный план содержит ровно m положительных компонент, где m - число ограничений в задаче. В вырожденном опорном плане число положительных компонент оказывается меньше числа ограничений: некоторые базисные переменные, соответствующие данному опорному плану, принимают нулевые значения. Используя геометрическую интерпретацию для простейшего случая, когда n - m = 2 (число небазисных переменных равно 2), легко отличить вырожденную задачу от невырожденной. В вырожденной задаче в одной вершине многогранника условий пересекается более двух прямых, описываемых уравнениями вида xi = 0. Это значит, что одна или несколько сторон многоугольника условий стягиваются в точку. Аналогично при n - m = 3 в вырожденной задаче в одной вершине пересекается более 3-х плоскостей xi = 0. В предположении о невырожденности задачи
находилось только одно значение, по которому определялся индекс выводимого из базиса вектора условий (выводимой из числа базисных переменной). В
вырожденной задаче может достигаться на нескольких индексах сразу (для нескольких строк). В этом случае в находимом опорном плане несколько базисных переменных будут нулевыми. Если задача линейного программирования оказывается вырожденной, то при плохом выборе вектора условий, выводимого из базиса, может возникнуть бесконечное движение по базисам одного и того же опорного плана. Это - так называемое явление зацикливания. Хотя в практических задачах линейного программирования зацикливание явлеется довольно редким, возможность его не исключена. Один из приемов борьбы с вырожденностью состоит в преобразовании задачи путем "незначительного" изменения вектора правых частей системы ограничений на величины таким образом, чтобы задача стала невырожденной, и, в то же время, чтобы это изменение не повлияло реально на оптимальный план задачи. Чаще реализуемые алгоритмы включают в себя некоторые простые правила, снижающие вероятность возникновения зацикливания или его преодоления. Пусть переменную xj необходимо сделать базисной. Рассмотрим
множество индексов E0, состоящее из тех i, для которых достигается. Множество индексов i, для которых выполняется данное условие обозначим через E0,. Если E0, состоит из одного элемента, то из базиса исключается вектор условий Ai (переменная xi делается небазисной). Если E0 состоит более чем из одного элемента, то составляется множество E1, которое состоит из , на которых достигается . Если E1 состоит из одного индекса k, то из базиса выводится переменная xk. В противном случае составляется множество E2 и т.д. Практически правилом надо пользоваться, если зацикливание уже обнаружено.
Альтернативный оптимум в ЗЛП???????????????????????????
60. Метод искусственного базиса. М-задача. Теорема о связи между решениями исходной задачи и М-задачи.
Метод искусственного базиса.
Метод искусственного базиса используется для нахождения допустимого базисного решения задачи линейного программирования, когда в условии присутствуют ограничения типа равенств. Рассмотрим задачу:
max{F(x)=∑cixi|∑ajixi=bj, j=1,m; xi≥0}.
В ограничения и в функцию цели вводят так называемые «искусственные переменные» Rj следующим образом:
∑ajix+Rj=bj, j=1,m;F(x)=∑cixi-M∑Rj
При введении искусственных переменных в методе искусственного базиса в функцию цели им приписывается достаточно большой коэффициент M, который имеет смысл штрафа за введение искусственных переменных. В случае минимизации искусственные переменные прибавляются к функции цели с коэффициентом M. Введение искусственных переменных допустимо в том случае, если в процессе решения задачи они последовательно обращаются в нуль.
Симплекс-таблица, которая составляется в процессе решения, используя метод искусственного базиса, называется расширенной. Она отличается от обычной тем, что содержит две строки для функции цели: одна – для составляющей F = ∑cixi, а другая – для составляющей M ∑Rj Рассмотрим процедуру решения задачи на конкретном примере.
Пример 1. Найти максимум функции F(x) = -x1 + 2x2 - x3 при ограничениях:
x1≥0, x2≥0, x3≥0 .
Применим метод искусственного базиса. Введем искусственные переменные в ограничения задачи
2x1 + 3x2 + x3 + R1 = 3;
x1 + 3x3 + R2 = 2 ;
Функция цели F(x)-M ∑Rj= -x1 + 2x2 - x3 - M(R1+R2).
Выразим сумму R1 + R2 из системы ограничений: R1 + R2 = 5 - 3x1 - 3x2 - 4x3, тогда F(x) = -x1 + 2x2 - x3 - M(5 - 3x1 - 3x2 - 4x3) .
При составлении первой симплекс-таблицы (табл. 1) будем полагать, что исходные переменные x1, x2 , x3 являются небазисными, а введенные искусственные переменные – базисными. В задачах максимизации знак коэффициентов при небазисных переменных в F- и M-строках изменяется на противоположный. Знак постоянной величины в M-строке не изменяется. Оптимизация проводится сначала по M-строке. Выбор ведущих столбца и строки, все симплексные преобразования при испльзовании метода искусственного базиса осуществляются как в обычном симплекс-методе.
Максимальный по абсолютному значению отрицательный коэффициент (-4) определяет ведущий столбец и переменную x3, которая перейдет в базис. Минимальное симплексное отношение (2/3) соответствует второй строке таблицы, следовательно, переменная R2 должна быть из базиса исключена. Ведущий элемент обведен контуром.
В методе искусственного базиса искусственные переменные, исключенные из базиса, в него больше не возвращаются, поэтому столбцы элементов таких переменных опускаются. Табл. 2. сократилась на 1 столбец. Осуществляя пересчет этой таблицы, переходим к табл. 3., в которой строка M обнулилась, ее можно убрать. После исключения из базиса всех искусственных переменных получаем допустимое базисное решение исходной задачи, которое в рассматриваемом примере является оптимальным:
x1=0; x2=7/9; Fmax=8/9.
Если при устранении M-строки решение не является оптимальным, то процедура оптимизации продолжается и выполняется обычным симплекс-методом. Рассмотрим пример, в котором присутствуют ограничения всех типов:≤,=,≥
Условие задачи
Найти оптимальные величины производства продукции видов А, Б и В. Затраты сырья на единицу продукции: А – 5, Б – 2, В – 4. Объем сырья – 2000 единиц. Затраты оборудования на единицу продукции: А – 4, Б – 5, В – 4. Объем оборудования – 1000 единиц. Прибыль от реализации единицы продукции: А – 10, Б – 8, В – 12. Критерий – максимум прибыли предприятия. Производство продукции А должно быть не менее 100 ед. Производство продукции Б должно быть не менее 50 ед.
Решение задачи симплекс М методом
1) Определение оптимального плана производства
Пусть x1, x2, x3 - количество произведенной продукции вида А, Б, В, соответственно. Тогда математическая модель задачи имеет вид:
F = 10·x1 + 8·x2 + 12·x3 –>max
Вводим дополнительные переменные x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0, чтобы неравенства преобразовать в равенства.
Чтобы выбрать начальный базис, вводим искусственные переменные x8 ≥ 0, x9 ≥ 0 и очень большое число M (M –> ∞). Решаем М методом.
F = 10·x1 + 8·x2 + 12·x3 + 0·x4 + 0·x5 + 0·x6 + 0·x7– M·x8– M·x9 –>max
В качестве базиса возьмем x4 = 2000; x5 = 1000; x8 = 100; x9 = 50.
Данные заносим в симплекс таблицу
Симплекс таблица № 1
0 · 2000 + 0 · 1000 + (– M) · 100 + (– M) · 50 = – 150M
Вычисляем оценки по формуле:
Δ1 = 0 · 5 + 0 · 4 + (– M) · 1 + (– M) · 0 – 10 = – M – 10
Δ2 = 0 · 2 + 0 · 5 + (– M) · 0 + (– M) · 1 – 8 = – M – 8
Δ3 = 0 · 4 + 0 · 4 + (– M) · 0 + (– M) · 0 – 12 = – 12
Δ4 = 0 · 1 + 0 · 0 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ5 = 0 · 0 + 0 · 1 + (– M) · 0 + (– M) · 0 – 0 = 0
Δ6 = 0 · 0 + 0 · 0 + (– M) · (–1) + (– M) · 0 – 0 = M
Δ7 = 0 · 0 + 0 · 0 + (– M) · 0 + (– M) · (–1) – 0 = M
Δ2 = 0 · 0 + 12 · 0 + 10 · 0 + 8 · 1 – 8 = 0
Δ3 = 0 · 0 + 12 · 1 + 10 · 0 + 8 · 0 – 12 = 0
Δ4 = 0 · 1 + 12 · 0 + 10 · 0 + 8 · 0 – 0 = 0
Δ5 = 0 · (–1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 = 3
Δ6 = 0 · 1 + 12 · 1 + 10 · (–1) + 8 · 0 – 0 = 2
Δ7 = 0 · (–3) + 12 · 5/4 + 10 · 0 + 8 · (–1) – 0 = 7
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450
Ответ: x1 = 100; x2 = 50; x3 = 175/2 = 87.5; x4 = 1050; x5 = 0; x6 = 0; x7 = 0; Fmax = 2450То есть необходимо произвести x1 = 100 единиц продукции вида А, x2 = 50 единиц продукции вида Б и x3 = 87,5 единиц продукции вида В. Максимальная прибыль при этом составит Fmax = 2450 единиц.
Теорема о связи между решениями исходной задачи и М-задачи.
???????????????????????
