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

Решение:

I итерация:

х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:

Приведем целевую функциюк следующему виду:

На основе полученной задачи сформируем исходную симплекс-таблицу:

Таблица 5.3

Исходная симплекс-таблица

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

3 этап: проверка совместности системы ограничений ЗЛП.

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

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

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

6 этап: проверка оптимальности.

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

Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1

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

Таблица 5.4

Исходная симплекс-таблица

В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».

Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.

9.1. Преобразование разрешающего элемента.

Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:

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

9.2. Преобразование разрешающей строки.

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

9.3. Преобразование разрешающей колонки.

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

9.4. Преобразование остальных элементов симплекс-таблицы.

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

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

«х3 »: .

Аналогично преобразуются значения других клеток:

«х3 х1 »: ;

«х4 »: ;

«х4 х1 »: ;

«х6 »: ;

«х6 х1 »: ;

«»: ;

«х1 »: .

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

II итерация:

1 этап: составление симплекс-таблицы.

Таблица 5.5

Симплекс-таблица II итерации

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):

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

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

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

8.2. Определение разрешающей строки.

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

Таблица 5.6

Симплекс-таблица II итерации

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.

III итерация

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

Таблица 5.7

Симплекс-таблица III итерации

2 этап: определение базисного решения.

В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

6 этап: проверка оптимальности найденного базисного решения.

Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.

8 этап: определение разрешающего элемента.

8.1. Определение разрешающей колонки.

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

8.2. Определение разрешающей строки.

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

Таблица 5.8

Симплекс-таблица III итерации

9 этап: преобразование симплекс-таблицы.

Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.

IV итерация

1 этап: построение новой симплекс-таблицы.

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

Таблица 5.9

Симплекс-таблица IV итерации

2 этап: определение базисного решения.

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

3 этап: проверка совместности системы ограничений.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.

4 этап: проверка ограниченности целевой функции.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.

5 этап: проверка допустимости найденного базисного решения.

Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.

6 этап: проверка оптимальности найденного базисного решения.

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

7 этап: проверка альтернативности решения.

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

Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.

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

Решение:

I итерация:

1 этап: формирование исходной симплекс-таблицы.

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

В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.

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

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

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

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

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-й группы будет снижать оптимальную прибыль на
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.

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

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

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

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

2x 1 +5x 2 +3x 3 +8x 4 →min

Ограничивающие условия:

3x 1 +6x 2 -4x 3 +x 4 ≤12
4x 1 -13x 2 +10x 3 +5x 4 ≥6
3x 1 +7x 2 +x 3 ≥1

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

Так как наша задача - задача минимизации, то нам необходимо преобразовать ее к задаче на поиск максимума. Для этого изменим знаки коэффициентов целевой функции на противоположные. Элементы первого неравенства записываем без изменений, добавив в него дополнительную переменную x 5 и изменив знак "≤" на "=". Т. к. второе и третье неравенства имеют знаки "≥" необходимо поменять знаки их коэффициентов на противоположные и внести в них дополнительные переменные x 6 и x 7 соответственно. В результате получем эквивалентную задачу:

3x 1 +6x 2 -4x 3 +x 4 +x 5 =12
-4x 1 +13x 2 -10x 3 -5x 4 +x 6 =-6
-3x 1 -7x 2 -x 3 +x 7 =-1

Переходим к формированию исходной симплекс таблицы. В строку F таблицы заносятся коэффициенты целевой функции с противоположным знаком.

Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение.В строке F имеются отрицательные элементы, это означает что полученое решение не оптимально. Определим ведущий столбец. Для этого найдем в строке F максимальный по модулю отрицательный элемент - это -1.988 Ведущей строкой будет та для которой отношение свободного члена к соответствующему элементу ведущего столбца минимально. Ведущей строкой является X2, а ведущий элемент: 0.313.

Так как в строке F нет отрицательных элементов, то найдено оптимальное решение. Так как исходной задачей был поиск минимума, то оптимальным решением будет свободный член строки F, взятый с противоположным знаком. F=1.924
при значениях переменных равных: x 3 =0.539, x 1 =0.153. Переменные x 2 и x 4 не входят в базис, поэтому x 2 =0 x 4 =0.

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач симплекс-методом. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

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

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

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод . Составим первую симплекс-таблицу (Итерация 0) для решения задачи на симплекс-метод , т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

симплекс-метод итерация 0

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

Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x 2 заменит в базисе s 1 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z-строки имеем:

Старая z-строка (-4 -6 0 0 0 0) -(-6)*Новая разрешающая строка -(0 -6 0 0 -6 -120) =Новая z-строка (-4 0 0 0 6 120).

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

симплекс-метод итерация 1

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

симплекс-метод итерация 2

Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.

симплекс-метод итерация 3

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.

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

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

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

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

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

.

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

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

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