Калькулятор двойственный симплекс метод. Решение злп симплекс-методом. Особые случаи применения симплекс-метода

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

БП Симплексные
отношения
8 6 4 0 0 0 0 520 16 18 9 1 0 0 65/2 0 140 7 7 2 0 1 0 20 0 810 9 2 1 0 0 1 90 0 -8 -6 -4 0 0 0

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

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

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

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

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

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

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

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

БП Симплексные
отношения
8 6 4 0 0 0 0 200 0 2 31/7 1 -16/7 0 1400/31 8 20 1 1 2/7 0 1/7 0 70 0 630 0 -7 -11/7 0 -9/7 1 - 160 0 2 -12/7 0 8/7 0

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

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

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

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

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

БП Симплексные
отношения
8 6 4 0 0 0 4 1400/31 0 14/31 1 7/31 -16/31 0 8 220/31 1 27/31 0 -2/31 9/31 0 0 21730/31 0 -195/31 0 11/31 -65/31 1 7360/31 0 86/31 0 12/31 8/31 0

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

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

Инструкция для решения задач двойственным симплекс-методом . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word (см. пример решения двойственным симплекс-методом).

Количество переменных 2 3 4 5 6 7 8 9 10
Количество строк (количество ограничений) 2 3 4 5 6 7 8 9 10
При этом ограничения типа x i ≥ 0 не учитывайте.

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

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях) Доход G(X)
1 2 3
0 0 0 0
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x i имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

  1. Составление псевдоплана . Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
  2. Проверка плана на оптимальность . Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом .
  3. Выбор ведущих строки и столбца . Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
  4. Расчет нового опорного плана . Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса . Далее переход к этапу 2.
Более подробный алгоритм двойственного симплекс-метода . Особенности двойственного симплекс-метода Используются при решении методом Гомори .

Пример . Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание : Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x 1 + 2x 2 + x 3 при следующих условиях-ограничений.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x 4 . Во втором неравенстве смысла (≤) вводим базисную переменную x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A =
-1 -1 0 1 0
2 1 -1 0 1
Решим систему уравнений относительно базисных переменных:
x 4 , x 5 ,
Полагая, что свободные переменные равны нулю, получим первый опорный план:
X1 = (0,0,0,-10,8)
Базис B x 1 x 2 x 3 x 4 x 5
x 4 -10 -1 -1 0 1 0
x 5 8 2 1 -1 0 1
F(X0) 0 -4 -2 -1 0 0

Итерация №1

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.


Ведущей будет первая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.

Базис B x 1 x 2 x 3 x 4 x 5
x 4 -10 -1 -1 0 1 0
x 5 8 2 1 -1 0 1
F(X0) 0 -4 -2 -1 0 0
θ 0 -4: (-1) = 4 -2: (-1) = 2 - - -

4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса .
Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 5 -2 1 0 -1 1 1
F(X0) 20 -2 0 -1 -2 0

Представим расчет каждого элемента в виде таблицы:
B x 1 x 2 x 3 x 4 x 5
-10: -1 -1: -1 -1: -1 0: -1 1: -1 0: -1
8-(-10 1):-1 2-(-1 1):-1 1-(-1 1):-1 -1-(0 1):-1 0-(1 1):-1 1-(0 1):-1
0-(-10 -2):-1 -4-(-1 -2):-1 -2-(-1 -2):-1 -1-(0 -2):-1 0-(1 -2):-1 0-(0 -2):-1

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x 5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x 3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 5 -2 1 0 -1 1 1
F(X0) 20 -2 0 -1 -2 0
θ 0 - - -1: (-1) = 1 - -

4. Пересчет симплекс-таблицы. Выполняем преобразования.
Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1
Или более подробно:
B x 1 x 2 x 3 x 4 x 5
10-(-2 0):-1 1-(1 0):-1 1-(0 0):-1 0-(-1 0):-1 -1-(1 0):-1 0-(1 0):-1
-2: -1 1: -1 0: -1 -1: -1 1: -1 1: -1
20-(-2 -1):-1 -2-(1 -1):-1 0-(0 -1):-1 -1-(-1 -1):-1 -2-(1 -1):-1 0-(1 -1):-1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1

Оптимальный план можно записать так: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22

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

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

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

где 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 рубашка 2 рубашка 3 Запасы нитки (м.) 1 9 3 96 пуговицы (шт.) 20 10 30 640 ткань ( 1 2 2 44 Прибыль (р.) 2 5 4

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

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

Через и количество рубашек 1-го, 2-го и 3-го вида, предназначенных к выпуску.

Тогда ограничения на ресурсы будут иметь следующий вид:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разрешающим элементов является число 4/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 2-й итерации.

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

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

Разрешающим элементов является число 10/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 3-й итерации.

БП c Б A o x 1 x 2 x 3 x 4 x 5 x 6 Симплексные 2 5 4 0 0 0 отношения 0 x 4 0 96 1 9 3 1 0 0 32/3 x 5 0 640 20 10 30 0 1 0 64 x 6 0 44 1 2 2 0 0 1 22 F j - c j 0 -2 -5 -4 0 0 0 1 x 2 5 32/3 1/9 1 1/3 1/9 0 0 32 x 5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x 6 0 68/3 7/9 0 4/3 -2/9 0 1 17 F j - c j 160/3 -13/9 0 -7/3 5/9 0 0 2 x 2 5 5 -1/12 1 0 1/6 0 -1/4 -- x 5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 F j - c j 93 -1/12 0 0 1/6 0 7/4 3 x 2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 F j - c j 95 0 0 0 1/4 1/40 5/4

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

Необходимо шить 24 рубашки 1-го вида, 7 рубашек 2-го вида и 3 рубашки 3-го вида. При этом получаемая прибыль будет максимальна и составит 95 руб.

Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте , на Viber или заполнив форму . Стоимость решения домашней работы начинается от 7 бел.руб. за задачу (200 рос.руб.), но не менее 10 бел.руб. (300 рос.руб.) за весь заказ. Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 30 бел.руб. (1000 рос.руб.) за решение билета.

11.4. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

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

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

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

Рассматривая это условие с учетом двойственности, можно записать

.

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

Это позволило разработать новый метод решения задач линейного программирования, при использовании которого сначала получается недопустимое, но «лучшее, чем оптимальное» решение (в обычном симплекс-методе сначала находится допустимое , но неоптимальное решение). Новый метод, получивший название двойственного симплекс-метода , обеспечивает выполнение условия оптимальности решения и систематическое «приближение» его к области допустимых решений. Когда полученное решение оказывается допустимым, итерационный процесс вычислений заканчивается, так как это решение является и оптимальным.

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

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

при ограничениях

.

Перейдем к канонической форме:

при ограничениях

Начальная симплекс-таблица имеет вид

Базисные

переменные

x 1

x 2

x 3

x 4

x 5

Решение

x 3

x 4

x 5

–3

–4

–1

–3

–3

–6

–2

–1

Начальное базисное решение оптимальное, но не допустимое.

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

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

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

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

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

Переменные

x 1

x 2

x 3

x 4

x 5

Уравнение

x 4 -уравнение

–2

–4

–1

–3

Отношение

В качестве включаемой переменной выбирается x 2 . Последующее преобразование строк приводит к новой симплекс-таблице:

Базисные

переменные

x 1

x 2

x 3

x 4

x 5

Решение

x 3

x 2

x 5

–1

–1

Новое решение также оптимальное, но все еще недопустимое. В качестве новой исключаемой переменной выберем (произвольно) x 3 . Определим включаемую переменную.

Переменные

x 1

x 2

x 3

x 4

x 5

Уравнение

x 4 -уравнение

отношение