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

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

Задачи линейного программирования можно решить следующими методами:

алгоритмом Флойда;

алгоритм Дейкстры на графах;

графический метод;

метод симплекс-таблиц и др.

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

В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

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

На каждом шаге цикла необходимо найти вершину U с минимальным расстоянием и флагом равным нулю. Затем нужно установить в ней флаг в 1 и проверяем все соседние с ней вершины U. Если расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то необходимо уменьшить его. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0. Последний случай возможен тогда и только тогда, когда граф G не связан.

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

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

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

Минимальное значение функции определено формулой (1).

(1)

Ограничения представлены формулами (2) и (3).

(2)

(3)

Пусть система (2) при условии (3) совместна. Каждое из неравенств из систем (2) и (3) определяет полуплоскость с граничными прямыми представлено формулой(4):

Линейная функция (1) при фиксированных значениях Z является уравнением прямой линии:

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

Найти точку многоугольника решений, в которой прямая
опорная и функция Z при этом достигает минимума.

Значения
уменьшаются в направлениивектора
, поэтому прямую Z=0 необходимо передвигать параллельно самой себе в направлении вектора N.

Если многоугольникрешений ограничен, то прямая дважды становится опорной по отношению к многоугольнику решений (в точкахB и E), причём минимальное значение принимает в точке E. Координаты точки
необходимо найти, решая систему уравнений прямых DE и EF.

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

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

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

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

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

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

Рисунок 1 – Начальное преобразование системы ограничений

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

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

Рисунок 2 – Преобразование системы неравенств

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

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

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

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

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

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

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

в новой таблице все элементы ключевого столбца = 0, кроме разрезающего, он всегда равен 1.

столбец, у которого в ключевой строке имеется 0,в новой таблице будет таким же.

строка, у которой в ключевом столбце имеется 0, в новой таблице будет такой же.

в остальные клетки новой таблицы записывается результат преобразования элементов старой таблицы, как показано на рисунке 3.

Рисунок 3 – Составление нового элемента в симплекс-таблице

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

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

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

После анализа собранной информации, была составлена задача линейного программирования по цеху №8 в ОАО «НефАЗ».На покрасочном конвейере, на котором окрашиваются детали. Необходимо покрасить оптимальное количество деталей за одну рабочую смену, чтобы прибыль была максимальной.

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

Симплекс - метод представляет собой итеративную процедуру решения задач ЛП, в каноническом виде (любую задачу ЛП можно привести к каноническому виду:

Всего в задаче будет n+m переменных.

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

Пример 1.

Решим задачу:

Для нахождения первоначального базисного решения разобьем переменные на основные и неосновные. Так как определитель матрицы коэффициентов при х 3 , х 4 х 5 и х 6 отличен от нуля (каждая из этих переменных входит только в одно ограничение причем с коэффициентом 1, то есть матрица коэффициентов при них будет единичной), то их можно взять за базисные переменные. Остальные переменные х 1 и х 2 будит неосновными.

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

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

1). Получим на первом шаге:

Выразим неосновные переменные через основные:

(*)

Получим базисное решение системы Х 1 =(0; 0; 18; 16; 5; 21). Если сравнить с графическим решением этой задачи, то Х 1 соответствует точке О(0;0) многоугольника ОАВСДЕ (см. рис. 1).

Так как это решение допустимое, нельзя исключать, что оно оптимальное.

,z(X 1)=0.

Функцию z можно увеличить за счет неосновной переменной (обе они входят в уравнение с коэффициентом >0). Это можно осуществить, перейдя к новому допустимому базисному решению, в котором одна из этих переменных станет основной. Если новое решение будет вырожденным, то целевая функция сохранит свое значение. Геометрически это переход к другой соседней вершине, в которой целевая функция будет по крайней мере не хуже. В рассматриваемой задаче можно переводить в базисные переменные как х 1 так и х 2 , так как обе входят в целевую функцию со знаком «+».

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

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

Любое уравнение системы (*) (кроме последнего) определяет оценочное отношение – границу роста переменной х 2 , сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х 2 , если они имеют разные знаки. Так как в последнее ограничение х 2 не входит (входит с коэффициентом 0), то рост х 2 не ограничен, х 2 <∞. Будем так же считать, сто граница переменной х 2 равно ∞, если коэффициент перед х 2 и свободный член имеют одинаковые знаки. Нет ограничений на рост х 2 и в том случае, если свободные член равен 0. Но если при этом коэффициент при х 2 отрицательный, то рост этой переменной ограничен 0.

Так как неотрицательность должны сохранять все переменные, по новая базисная переменная х 2 =min(6; 16; 5; ∞)=5. Уравнение, которое соответствует минимальной оценке, называется разрешающим. В этом примере – это третье уравнение

Следовательно, переменная х 5 =0 и переходит в небазисные переменные.

2). Получим на втором шаге:

Из третьего уравнения системы выразим:х 2:

Подставляя правую часть равенства во все остальные уравнения вместо х 2 получим:

Получим новое базисное решение системы Х 2 =(0; 5; 3; 11; 0; 21). Это соответствует точке А(0;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные:
,z(X 2)=15.

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

х 1 =min(∞; 13; 11/2; ∞)=3, следовательно второе уравнение разрешающее и х 3 выводится из базиса.

3). Получим на третьем шаге:

Из второго уравнения системы выразим:х 1:

Подставляя правую часть равенства во все остальные уравнения вместо х 1 получим:

Получим новое базисное решение системы Х 3 =(3; 5; 0; 5; 0; 12). Это соответствует точке В(3;5) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные:
,z(X 3)=21.

Аналогично первым двум шагам введем в базисные переменные х 5 .

х 5 =min(∞; 5; 1;4/3)=1, следовательно, третье уравнение разрешающее и х 4 выводится из базиса.

4). Получим на четвертом шаге:

Из третьего уравнения системы выразим:х 5:

Подставляя правую часть равенства во все остальные уравнения, вместо х 5 получим:

Получим новое базисное решение системы Х 4 =(6; 4; 0; 0; 1; 6). Это соответствует точке С(6;4) многоугольника ОАВСДЕ (см. рис. 1).

Выразим целевую функцию через неосновные переменные: ,z(X 4)=24.

Целевую функцию нельзя улучшить переходя к другому базисному решению, так как все коэффициенты при небазисных переменных меньше 0, следовательно, задача решена. Максимальная прибыль при этом равна 24, а оптимальный план производства: 6 единиц первой продукции и 4 единицы второй продукции. Дополнительные переменные показывают разницу между затратами ресурсов каждого вида и их потреблением. х 3 =х 4 =0, следовательно ресурсы S 1 иS 2 расходуются полностью в процессе производства, а остатки S 3 иS 4 равны 1 и 3 соответственно.

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

Алгоритм симплекс - метода:

Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума (z max =). Если минимум конечен, то выбираем строку q, на которой он достигается (если их несколько, то любую), и называем ее разрешающей строкой. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент a qs .

Переходим к следующей таблице по правилам (преобразования Гаусса-Жордана или правило прямоугольника):

1. в левом столбце записываем новый базис: вместо основной переменной x q – переменную x s ;

   в столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1- на пересечении строки и столбца, соответствующих одной и той же базисной переменной; 0 – во всех других позициях столбцов базисных переменных;

   Новую строку q получаем из старой делением на разрешающий элемент a qs ;

   все остальные элементы а ij " вычисляем по правилу:

(2)

Пример 6.

Решим задачу:

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

Целевую функцию представим в виде z-2x 1 -3x 2 =0.

Базисными переменными будут являться дополнительные переменные x 3 ,x 4 ,x 5 ,x 6 .

Заполним первую симплекс-таблицу:

Проверяем критерий оптимальности задачи. В последней оценочной строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю – (-3). Следовательно s=2, переменная х 2 является вводимой базис, а соответствующий ей столбец – разрешающим.

Находим оценочные отношения и выбираем из них минимальное (=5). Следовательно, q=3, переменная х 5 является выводимой из базиса, а соответствующая ей строка – разрешающей.

в новом базисе основные переменные x 3 ,x 4 ,x 2 ,x 6 ;

расставляем 0 и1; например, на пересечении столбца и строки, соответствующих переменной х 3 ставим 1, а остальные элементы столбца х 3 равны 0 и т.д. Третья строка получается делением на разрешающий элемент а 33 =1. Остальные клетки таблицы заполняем по формулам (2). Например:

Получаем вторую симплекс таблицу:

Критерий оптимальности вновь не выполнен. Теперь разрешающий первый столбец и х 1 – вводимая переменная. Считаем оценочные отношения и находим разрешающую строку – первая и выводимую из базиса переменную – х 3 . Разрешающий элемент а 11 .

Переходим к новой симплекс-таблице:

И на этот раз критерий оптимальности не выполнен.

Выводимая переменная х 4 ; вводимая х 5 . Переходим к новой таблице.

Критерий оптимальности выполнен, значит z max =24. Оптимальное решение (6; 4; 0; 0; 1; 3).

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

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

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

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

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

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

Решение:

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

Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную 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).

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

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

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

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

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

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

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

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

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

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

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

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

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