Линейное программирование симплекс метод c. Симплекс-метод решения задач линейного программирования. Примеры решения ЗЛП методом искусственного базиса

x 1

+x 2

+x 3

x 1

+x 2

+x 3

x 1

+x 2

+x 3

≤ = ≥

Предупреждение

Очистить все ячейки?

Закрыть Очистить

Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.

Симплекс метод

Примеры решения ЗЛП симплекс методом

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

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

Запишем текущий опорный план:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x при . min (40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x 3 . Сделаем исключение Гаусса для столбца x 2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x 1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x 4 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Текущий опорный план является оптимальным, так как в строках 4 под переменными нет отрицательных элементов.

Решение можно записать так: .

Значение целевой функции в данной точке: F (X )=.

Пример 2. Найти максимум функции

Р е ш е н и е.

Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.

Симплекс таблица примет вид:

Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x 2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при . Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.

Примеры решения ЗЛП методом искусственного базиса

Пример 1. Найти максимум функции

Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

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

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

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 1. Из базиса выходит вектор x 2 . Сделаем исключение Гаусса для столбца x 1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x 3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем при соответствует строке 3. Из базиса выходит вектор x 5 . Сделаем исключение Гаусса для столбца x 3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.

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

Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.

Решение исходной задачи можно записать так:

Пример 2. Найти оптимальный план задачи линейного программирования:

Матрица коэффициентов системы уравнений имеет вид:

Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.

Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.

Симплекс таблица примет вид:

В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.

Двумерные задачи линейного программирования решаются графически . Для случая N=3 можно рассмотреть трехмерное пространство и целевая функция будет достигать своё оптимальное значение в одной из вершин многогранника.

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме . Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r , то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X 1 , X 2 , ..., X r . Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему , например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными , их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением , если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X 1 , X 2 , ..., X r , то решение {b 1 , b 2 ,..., b r , 0, ..., 0} будет опорным при условии, что b 1 , b 2 ,..., b r ≥ 0 .

Симплекс-метод основан на теореме, которая называется фундаментальной теоремой симплекс-метода. Среди оптимальных планов задачи линейного программирования в канонической форме обязательно есть опорное решение ее системы ограничений. Если оптимальный план задачи единственен, то он совпадает с некоторым опорным решением. Различных опорных решений системы ограничений конечное число. Поэтому решение задачи в канонической форме можно было бы искать перебором опорных решений и выбором среди них того, для которого значение F самое большое. Но, во-первых, все опорные решения неизвестны и их нужно находить, a, во-вторых, в реальных задачах этих решений очень много и прямой перебор вряд ли возможен. Симплекс-метод представляет собой некоторую процедуру направленного перебора опорных решений. Исходя из некоторого, найденного заранее опорного решения по определенному алгоритму симплекс-метода мы подсчитываем новое опорное решение, на котором значение целевой функции F не меньше, чем на старом. После ряда шагов мы приходим к опорному решению, которое является оптимальным планом.

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

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

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

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

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

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

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

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X 1 , X 2 , ..., X r и что при этом b 1 , b 2 ,..., b r ≥ 0 (соответствующее базисное решение является опорным).

Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т.е. задача записывается в виде системы равенств:

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

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

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

В самом общем виде задача линейного программирования математически записывается следующим образом:

где X = (x 1 , x 2 , ... , x n ) ; W – область допустимых значений переменных x 1 , x 2 , ... , x n ;f(Х) – целевая функция.

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

Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f(Х) не ограничена сверху на допустимом множестве W .

Методы решения оптимизационных задач зависят как от вида целевой функции f(Х) , так и от строения допустимого множества W . Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.

Характерные черты задач линейного программирования следующие:

показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x 1 , x 2 , ... , x n ) ;

ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.

Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

(2) (3) (4) (5)

При этом система линейных уравнений (3) и неравенств (4), (5), определяющая допустимое множество решений задачи W , называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности .

Допустимое решение – это совокупность чисел (план ) X = (x 1 , x 2 , ... , x n ) , удовлетворяющих ограничениям задачи. Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

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

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

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

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

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

если некоторая переменная x j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x 3 = x 3 + - x 3 - , где x 3 + , x 3 - ≥ 0 .

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

min L = 2x 1 + x 2 - x 3 ; 2x 2 - x 3 ≤ 5; x 1 + x 2 - x 3 ≥ -1; 2x 1 - x 2 ≤ -3; x 1 ≤ 0; x 2 ≥ 0; x 3 ≥ 0.

Введем в каждое уравнение системы ограничений выравнивающие переменные x 4 , x 5 , x 6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x 6 вводятся в левую часть со знаком "+", а во второе уравнение переменная x 5 вводится со знаком "-".

2x 2 - x 3 + x 4 = 5; x 1 + x 2 - x 3 - x 5 = -1; 2x 1 - x 2 + x 6 = -3; x 4 ≥ 0; x 5 ≥ 0; x 6 ≥ 0.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

2x 2 - x 3 + x 4 = 5; -x 1 - x 2 + x 3 + x 5 = 1; -2x 1 + x 2 - x 6 = 3.

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

Алгоритм симплекс-метода находит оптимальное решение, рассматривая ограниченное количество допустимых базисных решений. Алгоритм симплекс-метода всегда начинается с некоторого допустимого базисного решения и затем пытается найти другое допустимое базисное решение, "улучшающее" значение целевой функции. Это возможно только в том случае, если возрастание какой-либо нулевой (небазисной) переменной ведет к улучшению значения целевой функции. Но для того, чтобы небазисная переменная стала положительной, надо одну из текущих базисных переменных сделать нулевой, т.е. перевести в небазисные. Это необходимо, чтобы новое решение содержало в точности m базисных переменных. В соответствии с терминологией симплекс-метода выбранная нулевая переменная называется вводимой (в базис), а удаляемая базисная переменная - исключаемой (из базиса).

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

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

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

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

F = с 1 х 1 +с 2 х 2 +…+с n x n max

х 1 0, х 2 0,…, х n 0.

1-й шаг . Вводим добавочные переменные и записываем полученную систему уравнений и линейную функцию в виде расширенной системы.

F–c 1 x 1 –c 2 x 2 –…–c n x n =0=c p.

2-й шаг. Составляем первоначальную симплекс-таблицу.

Переменные	Основные и добавочные переменные	свободные члены (решение)	Оценочное отношение
Переменные		свободные члены (решение)	Оценочное отношение

3-й шаг. Проверяем выполнение критерия оптимальности – наличие в последней строке отрицательных коэффициентов. Если таких нет, то решение оптимально и F * =c o , базисные переменные равны соответствующим коэффициентам b j , неосновные переменные равны нулю, т. е. X * =(b 1 ,b 2 ,…, b m , 0, …, 0).

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

Для определения разрешающей строки, рассчитаем оценочные отношения и заполним последний столбец таблицы.

Оценочное отношение i-ой строки равно

, если b i и a is имеют разные знаки;

, если b i =0 и а is <0;

, если a is =0;

0, если b i =0 и а is >0;

В столбце оценочных отношений находим минимальный элемент min который определяет разрешающую строку g.

Если минимума нет, то задача не имеет конечного оптимума I и является неразрешимой.

На пересечении разрешающих строки и столбца находится разрешающий элемент а gs .

5-й шаг . Строим следующую таблицу. Для этого

Переходим к третьему шагу.

М-метод Иногда при решении ЗЛП в матрице коэффициентов при неизвестных системы ограничений нет единичных столбцов, из которых можно составить единичную матрицу, т.е. возникает проблема выбора базисных переменных, либо первоначальное решение является недопустимым. В таких случаях используют метод искусственного базиса (М - метод). Во все ограничения, где нет базисных переменных, вводятся искусственные переменные . В целевую функцию искусственные переменные вводятся с коэффициентом (- М) для задач на max и с коэффициентом (+ М) для задач на min, где М – достаточно большое положительное число . Затем решается расширенная задача по правилам симплексного метода. Если все искусственные переменные окажутся равными нулю, т.е. будут исключены из базиса, то либо будет получено оптимальное решение исходной задачи, либо исходная задача решается далее и находится ее оптимальное решение или устанавливается ее неразрешимость. Если хотя бы одна из искусственных переменных окажется отличной от нуля, то исходная задача не имеет решения

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

1. Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3стр

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

3. Алгоритм симплексного метода решения задач линейного программирования. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11стр

4. Пример решения задачи симплексным методом. . . . . . . . . . . . . . . . . . 11-15стр

5.Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16стр

6.Список используемой литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17стр

1. Введение

Работа посвящена наиболее распространенному методу решения задачи линейного программирования (симплекс-методу). Симплекс-метод является классическим и наиболее проработанным методом в линейном программировании. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.

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

1. Указать способ нахождения оптимального опорного решения

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

3. Задать критерии, которые позволяют своевременно прекратить перебор опорных решений на оптимальном решении или следать заключение об отсутствии оптимального решения.

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

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

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям.

Реализация решения задачи симплекс-методом наглядно показана на блок-схеме (рис.1).

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

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

Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).

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

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

Алгоритм перехода к следующей таблице такой:

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

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

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

Основное содержание симплексного метода заключается в следующем:

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

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

Для того, чтобы решить задачу симплексным методом необходимо выполнить следующее:

Привести задачу к каноническому виду
Найти начальное опорное решение с "единичным базисом" (если опорное решение отсутствует, то задача не имеет решение ввиду несовместимости системы ограничений)
Вычислить оценки разложений векторов по базису опорного решения и заполнить таблицу симплексного метода
Если выполняется признак единственности оптимального решения, то решение задачи заканчивается
Если выполняется условие существования множества оптимальных решений, то путем простого перебора находят все оптимальные решения

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

Пример 26.1

Решить симплексным методом задачу:

Решение:

Приводим задачу к каноническому виду.

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).

Получаем:

Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.

Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).

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

Δ k = C б X k — c k

C б = (с 1 , с 2 , ... , с m) — вектор коэффициентов целевой функции при базисных переменных
X k = (x 1k , x 2k , ... , x mk) — вектор разложения соответствующего вектора А к по базису опорного решения
С к — коэффициент целевой функции при переменной х к.

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

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

В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.

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

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:

Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).

Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

Метод линейного программирования в экономическом анализе

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

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

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

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

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

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

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

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

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

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

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

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

Возможно, будет полезно почитать: