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

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

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

где 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, где М – достаточно большое положительное число . Затем решается расширенная задача по правилам симплексного метода. Если все искусственные переменные окажутся равными нулю, т.е. будут исключены из базиса, то либо будет получено оптимальное решение исходной задачи, либо исходная задача решается далее и находится ее оптимальное решение или устанавливается ее неразрешимость. Если хотя бы одна из искусственных переменных окажется отличной от нуля, то исходная задача не имеет решения

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

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

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

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Краткая теория

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

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

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

1. умение находить начальный опорный план;
2. наличие признака оптимальности опорного плана;
3. умение переходить к нехудшему опорному плану.

Пример решения задачи

Условие задачи

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

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

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

Решение задачи

Построение модели

Через обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.

Тогда целевая функция, выражающая получаемую прибыль:

Ограничения по материально-денежным ресурсам:

Кроме того, по смыслу задачи

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

Приведение к каноническому виду ЗЛП

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

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

Решение симплекс-методом

Заполняем симплексную таблицу 0-й итерации.

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

Переход к следующей итерации осуществляем следующим образом:

Ведущий столбец соответствует .

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

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

Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .

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

Получаем таблицу 1-й итерации:

Ключевой столбец для 1-й итерации соответствует .

Находим ключевую строку, для этого определяем:

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.

Вектор выводим из базиса и вводим вектор .

Получаем таблицу 2-й итерации:

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

Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.

Двойственная задача ЛП

Запишем модель двойственной задачи.

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

1) если прямая задача решается на максимум, то двойственная - на минимум, и наоборот;

2) в задаче на максимум ограничения-неравенства имеют смысл ≤, а в задаче минимизации - смысл ≥;

3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;

4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;

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

6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство;

7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.

Транспонируем матрицу исходной задачи:

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

Решение двойственной задачи ЛП

Соответствие между переменными исходной и двойственной задачи:

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

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

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

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

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

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

Исходные данные задачи на симплекс-метод

Предприятие выпускает 4 вида изделий, обрабатывая их на 3-х станках.

Нормы времени (мин./шт.) на обработку изделий на станках, заданы матрицей A:

Фонд времени работы станков (мин.) задан в матрице B:

Прибыль от продажи каждой единицы изделия (руб./шт.) задана матрицей C:

Цель производственной задачи

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

Решение задачи табличным симплекс-методом

(1) Обозначим X1, X2, X3, X4 планируемое количество изделий каждого вида. Тогда искомый план: (X1, X2, X3, X4 )

(2) Запишем ограничения плана в виде системы уравнений:

(3) Тогда целевая прибыль:

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

(4) Для решения получившейся задачи на условный экстремум, заменим систему неравенств системой линейных уравнений путем ввода в нее дополнительных неотрицательных переменных (X5, X6, X7 ).

(5) Примем следующий опорный план :

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Занесем данные в симплекс-таблицу :

В последнюю строку заносим коэффициенты при целевой функции и само ее значение с обратным знаком;

(7) Выбираем в последней строке наибольшее (по модулю ) отрицательное число.

Вычислим b = Н / Элементы_выбранного_столбца

Среди вычисленных значений b выбираем наименьшее .

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

• Сам разрешающий элемент обращается в 1.
• Для элементов разрешающей строки – a ij (*) = a ij / РЭ (то есть каждый элемент делим на значение разрешающего элемента и получаем новые данные ).
• Для элементов разрешающего столбца – они просто обнуляются.
• Остальные элементы таблицы пересчитываем по правилу прямоугольника.

a ij (*) = a ij – (A * B / РЭ)

Как видите, мы берем текущую пересчитываемую ячейку и ячейку с разрешающим элементом. Они образуют противоположные углы прямоугольника. Далее перемножаем значения из ячеек 2-х других углов этого прямоугольника. Это произведение (A * B ) делим на разрешающий элемент (РЭ ). И вычитаем из текущей пересчитываемой ячейки (a ij ) то, что получилось. Получаем новое значение - a ij (*) .

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

Так как у нас в последней строке снова имеются отрицательные числа, начинаем новую итерацию вычислений.

(10) Так как в последней строке нет отрицательных элементов, это означает, что нами найден оптимальный план производства! А именно: выпускать мы будем те изделия, которые перешли в колонку «Базис» - X1 и X2. Прибыль от производства каждой единицы продукции нам известна (матрица C ). Осталось перемножить найденные объемы выпуска изделий 1 и 2 с прибылью на 1 шт., получим итоговую (максимальную! ) прибыль при данном плане производства.

ОТВЕТ:

X1 = 32 шт., X2 = 20 шт., X3 = 0 шт., X4 = 0 шт.

P = 48 * 32 + 33 * 20 = 2 196 руб.

Галяутдинов Р.Р.

© Копирование материала допустимо только при указании прямой гиперссылки на

Шаг 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 .

Ведущий столбец здесь – столбец, соответствующий переменной . Ведущая строка – строка, соответствующая переменной. После проведения преобразований получим симплексную таблицу:

Еще одна итерация завершена. Переходим к новой итерации.

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