Задач линейного программирования. Он в последовательном построении , характеризующей рассматриваемый процесс. Решение разбивается на три основных этапа: выбор переменных, построение системы ограничений и поиск целевой функции.
Исходя из этого разделения, условие задачи можно перефразировать следующим образом: экстремум целевой функции Z(X) = f(x1, x2, … ,xn) → max (min) и соответствующие переменные, если известно, что они удовлетворяют системе ограничений: Φ_i (x1, x2, … ,xn) = 0 при i = 1, 2, …, k;Φ_i (x1, x2, … ,xn)) 0 при i = k+1, k+2, …, m.
Систему ограничений нужно привести к каноническому виду, т.е. к системе линейных уравнений, где число переменных больше числа уравнений (m > k). В этой системе обязательно найдутся переменные, которые можно выразить через другие переменные, а если это не так, то их можно ввести искусственно. В этом случае первые называются базисом или искусственным базисом, а вторые – свободными.
Удобнее рассмотреть симплекс-метод на конкретном примере. Пусть дана линейная функция f(x) = 6x1 + 5x2 + 9x3 и система ограничений:5x1 + 2x2 + 3x3 ≤ 25;x1 + 6x2 + 2x3 ≤ 20;4x1 + 3x3 ≤ 18.Требуется найти максимальное значение функции f(x).
РешениеНа первом этапе задайте начальное (опорное) решение системы уравнений абсолютно произвольным образом, которое при этом должно удовлетворять данной системе ограничений. В данном случае требуется введение искусственного , т.е. базисных переменных x4, x5 и x6 следующим образом:5x1 + 2x2 + 3x3 + x4 = 25;x1 + 6x2 + 2x3 + x5 = 20;4x1 + 3x3 + x6 = 18.
Как видите, неравенства преобразовались в равенства благодаря добавленным переменные x4, x5, x6, которые являются неотрицательными величинами. Таким образом, вы привели систему к каноническому виду. Переменная x4 входит в первое уравнение с коэффициентом 1, а в два – с коэффициентом 0, то же справедливо для переменных x5, x6 и соответствующих уравнений, что соответствует определению базиса.
Вы подготовили систему и нашли начальное опорное решение – X0 = (0, 0, 0, 25, 20, 18). Теперь представьте коэффициенты переменных и свободные члены уравнений (цифры справа от знака «=») в виде таблицы для оптимизации дальнейших вычислений (см. рис).
Суть симплекс-метода состоит в том, чтобы привести эту таблицу к такому виду, в котором все цифры в строке L будут неотрицательными величинами. Если же выяснится, что это невозможно, то система вообще не имеет оптимального решения. Для начала выберите самый минимальный элемент этой строки, это -9. Цифра стоит в третьем столбце. Преобразуйте соответствующую переменную x3 в базисную. Для этого разделите строку на 3, чтобы в ячейке получилась 1.
Теперь нужно, чтобы ячейки и обратились в 0. Для этого отнимите от соответствующие цифры третьей строки, на 3. От элементов второй строки - элементы третьей, умноженные на 2. И, наконец, от элементов строки L - умноженные на (-9). Вы получили второе опорное решение: f(x) = L = 54 при x1 = (0, 0, 6, 7, 8, 0).
Если в условии задачи есть ограничения со знаком ≥, то их можно привести к виду ∑a ji b j , умножив обе части неравенства на -1. Введем m дополнительных переменных x n+j ≥0(j =1,m ) и преобразуем ограничения к виду равенств
(2)
Предположим, что все исходные переменные задачи x 1 , x 2 ,..., x n – небазисные. Тогда дополнительные переменные будут базисными, и частное решение системы ограничений имеет вид
x 1 = x 2 = ... = x n = 0, x n+ j = b j , j =1,m . (3)
Так как при этом значение функции цели F 0 = 0 , можно представить F(x) следующим образом:
F(x)=∑c i x i +F 0 =0 (4)
Начальная симплекс-таблица (симплекс-табл. 1) составляется на основании уравнений (2) и (4). Если перед дополнительными переменными x n+j стоит знак «+», как в (2), то все коэффициенты перед переменными x i и свободный член b j заносятся в симплекс-таблицу без изменения. Коэффициенты функции цели при ее максимизации заносятся в нижнюю строку симплекс-таблицы с противоположными знаками. Свободные члены в симплекс-таблице определяют решение задачи.
Алгоритм решения задачи следующий:
1-й шаг. Просматриваются элементы столбца свободных членов. Если все они положительные, то допустимое базисное решение найдено и следует перейти к шагу 5 алгоритма, соответствующему нахождению оптимального решения. Если в начальной симплекс-таблице есть отрицательные свободные члены, то решение не является допустимым и следует перейти к шагу 2.
2-й шаг. Для нахождения допустимого решения осуществляется , при этом нужно решать, какую из небазисных переменных включить в базис и какую переменную вывести из базиса.
Таблица 1.
базисные переменные | Свободные члены в ограничениях | Небазисные переменные | |||||
x 1 | x 2 | ... | x l | ... | x n|||
x n+1 | b 1 | a 11 | a 12 | ... | a 1l | ... | a 1n |
x n+2 | b 2 | a 21 | a 22 | ... | a 2l | ... | a 2n |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+r | b2 | a r1 | a r2 | ... | a rl | ... | a rn |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
. | . | . | . | . | . | . | . |
x n+m | b m | a m1 | a m2 | ... | a ml | ... | a mn |
F(x) max | F 0 | -c 1 | -c 2 | ... | -c 1 | ... | -c n |
Для этого выбирают любой из отрицательных элементов столбца свободных членов (пусть это будет b 2 ведущим, или разрешающим. Если в строке с отрицательным свободным членом нет отрицательных элементов, то система ограничений несовместна и задача не имеет решения.
Одновременно из БП исключается та переменная, которая первой изменит знак при увеличении выбранной НП x l . Это будет x n+r , индекс r которой определяется из условия
т.е. та переменная, которой соответствует наименьшее отношение свободного члена к элементу выбранного ведущего столбца. Это отношение называется симплексным отношением. Следует рассматривать только положительные симплексные отношения.
Строка, соответствующая переменной x n+r , называется ведущей, или разрешающей. Элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим, или разрешающим элементом. Нахождением ведущего элемента заканчивается работа с каждой очередной симплекс-таблицей.
3-й шаг. Рассчитывается новая симплекс-таблица, элементы которой пересчитываются из элементов симплекс-таблицы предыдущего шага и помечаются штрихом, т.е. b" j , a" ji , c" i , F" 0 . Пересчет элементов производится по следующим формулам:
Сначала в новой симплекс-таблице заполнятся строка и столбец, которые в предыдущей симплекс-таблице были ведущими. Выражение (5) означает, что элемент a" rl на месте ведущего равен обратной величине элемента предыдущей симплекс-таблицы. Элементы строки a ri делятся на ведущий элемент, а элементы столбца a jl также делятся на ведущий элемент, но берутся с противоположным знаком. Элементы b" r и c" l рассчитываются по тому же принципу.
Остальные формулы легко записать с помощью .
Прямоугольник строится по старой симплекс-таблице таким образом, что одну из его диагоналей образует пересчитываемый (a ji) и ведущий (a rl) элементы (рис. 1). Вторая диагональ определяется однозначно. Для нахождения нового элемента a" ji из элемента a ji вычитается (на это указывает знак « – » у клетки) произведение элементов противоположной диагонали, деленное на ведущий элемент. Аналогично пересчитываются элементы b" j , (j≠r) и c" i , (i≠l).
4-й шаг. Анализ новой симплекс-таблицы начинается с 1-го шага алгоритма. Действие продолжается, пока не будет найдено допустимое базисное решение, т.е. все элементы столбца свободных членов должны быть положительными.
5-й шаг. Считаем, что допустимое базисное решение найдено. Просматриваем коэффициенты строки функции цели F(x) . Признаком оптимальности симплекс-таблицы является неотрицательность коэффициентов при небазисных переменных в F-строке.
Рис. 1. Правило прямоугольника
Если среди коэффициентов F-строки имеются отрицательные (за исключением свободного члена), то нужно переходить к другому базисному решению. При максимизации функции цели в базис включается та из небазисных переменных (например x l), столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента c l в нижней строке симплекс-таблицы. Это позволяет выбрать ту переменную, увеличение которой приводит к улучшению функции цели. Столбец, соответствующий переменной x l , называется ведущим. Одновременно из базиса исключается та переменная x n+r , индекс r которой определяется минимальным симплексным отношением:
Строка, соответствующая x n+r , называется ведущей , а элемент симплекс-таблицы a rl , стоящий на пересечении ведущей строки и ведущего столбца, называется ведущим элементом.
6-й шаг. по правилам, изложенным на 3-м шаге. Процедура продолжается до тех пор, пока не будет найдено оптимальное решение или сделан вывод, что оно не существует.
Если в процессе оптимизации решения в ведущем столбце все элементы неположительные, то ведущую строку выбрать невозможно. В этом случае функция в области допустимых решений задачи не ограничена сверху и F max ->&∞.
Если же на очередном шаге поиска экстремума одна из базисных переменных становится равной нулю, то соответствующее базисное решение называется вырожденным. При этом возникает так называемое зацикливание, характеризующееся тем, что с определенной частотой начинает повторяться одинаковая комбинация БП (значение функции F при этом сохраняется) и невозможно перейти к новому допустимому базисному решению. Зацикливание является одним из основных недостатков симплекс-метода, но встречается сравнительно редко. На практике в таких случаях обычно отказываются от ввода в базис той переменной, столбцу которой соответствует максимальное абсолютное значение отрицательного коэффициента в функции цели, и производят случайный выбор нового базисного решения.
Пример 1. Решить задачу
max{F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0}
Симплексным методом и дать геометрическую интерпретацию процесса решения.
Графическая интерпретация решения задачи представлена на рис. 2. Максимальное значение функции цели достигается в вершине ОДЗП с координатами . Решим задачу с помощью симплекс-таблиц. Умножим второе ограничение на (-1) и введём дополнительные переменные, чтобы неравенства привести к виду равенств, тогда
Исходные переменные x 1 и x 2 принимаем в качестве небазисных, а дополнительные x 3 , x 4 и x 5 считаем базисными и составляем симплекс-таблицу(симплекс-табл. 2). Решение, соответствующее симплекс-табл. 2, не является допустимым; ведущий элемент обведен контуром и выбран в соответствии с шагом 2 приведенного ранее алгоритма. Следующая симплекс-табл. 3 определяет допустимое базисное решение, ему соответствует вершина ОДЗП на рис. 2 Ведущий элемент обведен контуром и выбран в соответствии с 5-м шагом алгоритма решения задачи. Табл. 4 соответствует оптимальному решению задачи, следовательно: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F max = 20.
Рис. 2. Графическое решение задачи
Шаг 0. Подготовительный этап.
Приводим задачу ЛП к специальной форме (15).
Шаг 1. Составляем симплекс-таблицу , соответствующую специальной форме:
Заметим,
что этой таблице соответствует допустимое
базисное решение
задачи (15). Значение целевой функции на
этом решении
Шаг 2. Проверка на оптимальность
Если
среди элементов индексной строки
симплекс – таблицы
нет ни одного положительного элемента
то
,
оптимальное решение задачи ЛП найдено:.
Алгоритм завершает работу.
Шаг 3. Проверка на неразрешимость
Если
среди
есть положительный элемент
,
а в соответствующем столбце
нет ни одного положительного элемента
,
то целевая функцияL
является неограниченной снизу на
допустимом множестве. В этом случае
оптимального решения не существует.
Алгоритм завершает работу.
Шаг 4. Выбор ведущего столбца q
Среди
элементов
выбираем максимальный положительный
элемент
.Этот
столбец объявляем ведущим (разрешающим).
Шаг 5. Выбор ведущей строки p
Среди
положительных элементов столбца
находим элемент
,
для которого выполняется равенство
.
Строку
p
объявляем ведущей (разрешающей). Элемент
объявляем ведущим (разрешающим).
Шаг 6. Преобразование симплексной таблицы
Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем, вместо небазисной пере меннойзаписываем;
б)
ведущий элемент заменяем обратной
величиной
;
в)
все элементы ведущего столбца (кроме
)
умножаем на
;
г)
все элементы ведущей строки (кроме
)
умножаем на;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый – соответствующий элемент ведущего столбца;
второй – соответствующий элемент ведущей строки;
третий
– обратная величина ведущего элемента
.
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2.
2.3. Алгоритм симплекс-метода для задачи на максимум
Алгоритм
симплекс-метода для задачи на максимум
отличается от алгоритма для задачи на
минимум только знаками индексной строки
коэффициентов в целевой функции
,
а именно:
На
шаге 2:
:
На
шаге 3
.
Целевая функция является неограниченной
сверху на допустимом множестве.
На
шаге 4
:
.
2.4. Пример решения задачи симплекс-методом
Решить задачу, записанную в виде (15).
Составим симплексную таблицу:
Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение не является оптимальным. Значение целевой функции для этого базисаL=0.
Выбираем ведущий столбец – это столбец, соответствующий переменной .
Выбираем
ведущую строку. Для этого находим
.
Следовательно, ведущая строка соответствует
переменной.
Проводим преобразование симплексной таблицы, вводя переменную в базис и выводя переменнуюиз базиса. Получим таблицу:
Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид . Значение целевой функции на этом базисеL= -2 .
Ведущий столбец здесь – столбец, соответствующий переменной . Ведущая строка – строка, соответствующая переменной. После проведения преобразований получим симплексную таблицу:
Еще одна итерация завершена. Переходим к новой итерации.
Строка целевой функции не содержит положительных значений, значит, соответствующее базисное решение является оптимальным, и алгоритм завершает работу.
Рассмотрим симплекс -метод
для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
- Исходную задачу переводим в канонический вид путем введения дополнительных переменных. Для неравенства вида ≤ дополнительные переменные вводят со знаком (+ ), если же вида ≥ то со знаком (— ). В целевую функцию дополнительные переменные вводят с соответствующими знаками с коэффициентом, равным 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г.
Решение линейного программирования на заказ
Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на
Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.
Симплекс-метод, решение задачи с начальным базисом
1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").
Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:
Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами: -система ограничений должна быть системой уравнений с базисом; -свободные члены всех уравнений в системе должны быть неотрицательны.
Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод . Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод , т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.
симплекс-метод итерация 0
Отношение |
|||||||
Для улучшения решения перейдем к следующей итерации симплекс-метода , получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x 2 (коэффициент -6).
Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).
Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x 2 заменит в базисе s 1 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.
Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).
1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:
2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.
3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.
4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.
Строки таблицы «Итерация 1» получаем по следующему правилу:
Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).
Например для z-строки имеем:
Старая z-строка (-4 -6 0 0 0 0) -(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).
Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.
симплекс-метод итерация 1
Отношение |
|||||||
Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.
симплекс-метод итерация 2
Отношение |
|||||||
Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.
симплекс-метод итерация 3
Отношение |
|||||||
В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.