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

ИСПОЛЬЗОВАНИЕ ТАБЛИЧНОГО СИМПЛЕКС-МЕТОДА ДЛЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ДЛЯ ОПТИМИЗАЦИИ ЭКОНОМИЧЕСКИХ ЗАДАЧ

ВВЕДЕНИЕ

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

1. КРАТКИЙ ОБЗОР АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ДАННОГО ТИПА

1.1 Математическое программирование

Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи математического программирования формулируются следующим образом: найти экстремум некоторой функции многих переменных f (x 1 , x 2 , ... , x n) при ограничениях g i (x 1 , x 2 , ... , x n) * b i , где g i - функция, описывающая ограничения, * - один из следующих знаков £ , = , ³ , а b i - действительное число, i = 1, ... , m. f называется функцией цели (целевая функция).

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

Задачу линейного программирования можно сформулировать так. Найти max

при условии: a 11 x 1 + a 12 x 2 + . . . + a 1n x n £ b 1 ;

a 21 x 1 + a 22 x 2 + . . . + a 2n x n £ b 2 ;

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

a m1 x 1 + a m2 x 2 + . . . + a mn x n £ b m ;

x 1 ³ 0, x 2 ³ 0, . . . , x n ³ 0 .

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

В матричной форме задачу линейного программирования записывают следующим образом. Найти max c T x

при условии

где А - матрица ограничений размером (m´n), b (m ´ 1) - вектор-столбец свободных членов, x (n ´ 1) - вектор переменных, с Т = - вектор-строка коэффициентов целевой функции.

Решение х 0 называется оптимальным, если для него выполняется условие с Т х 0 ³ с Т х, для всех х Î R(x).

Поскольку min f(x) эквивалентен max [ - f(x) ] , то задачу линейного программирования всегда можно свести к эквивалентной задаче максимизации.

Для решения задач данного типа применяются методы:

1) графический;

2) табличный (прямой, простой) симплекс - метод;

3) метод искусственного базиса;

4) модифицированный симплекс - метод;

5) двойственный симплекс - метод.

1.2 Табличный симплекс - метод

Для его применения необходимо, чтобы знаки в ограничениях были вида “ меньше либо равно ”, а компоненты вектора b - положительны.

Алгоритм решения сводится к следующему:

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

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

искусственные переменные, которые так же вводятся и в целевую функцию со знаками, определяемыми типом оптимума.

Формируется симплекс-таблица.

Рассчитываются симплекс-разности.

Принимается решение об окончании либо продолжении счёта.

При необходимости выполняются итерации.

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

1.3 Метод искусственного базиса

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

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

1.4 Модифицированный симплекс - метод

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

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

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

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

Для производства двух видов изделий А и В используется три типа технологического оборудования. На производство единицы изделия А идёт времени, часов: оборудованием 1-го типа - а 1 , оборудованием 2-го типа - а 2 , оборудованием 3-го типа - а 3 .На производство единицы изделия В идёт времени, часов: оборудованием 1-го типа - b 1 , оборудованием 2-го типа - b 2 , оборудованием 3-го типа - b 3 .

На изготовление всех изделий администрацияпредприятия может предоставить оборудование 1-го типа не более, чем на t 1 ,оборудование 2-го типа не более, чем на t 2 , оборудование 3-го типа не более, чем на t 3 часов.

Прибыль от реализации единицы готового изделия А составляет a рублей, а изделия В - b рублей.

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

а 1 = 1 b 1 = 5 t 1 = 10 a = 2

а 2 = 3 b 2 = 2 t 2 = 12 b = 3

а 3 = 2 b 3 = 4 t 3 = 10

3. РАЗРАБОТКА И ОПИСАНИЕ АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ

3.1 Построение математической модели задачи

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

1. Определение переменных, для которых будет составляться математическая модель.

Так как требуется определить план производства изделий А и В, то переменными модели будут:

x 1 - объём производства изделия А, в единицах;

x 2 - объём производства изделия В, в единицах.

2. Формирование целевой функции.

Так как прибыль от реализации единицы готовых изделий А и В известна, то общий доход от их реализации составляет 2x 1 + 3x 2 (рублей). Обозначив общий доход через F, можно дать следующую математическую формулировку целевой функции: определить допустимые значения переменных x 1 и x 2 , максимизирующих целевую функцию F = 2x 1 + 3x 2 .

3. Формирование системы ограничений.

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

x 1 + 5x 2 £10;3x 1 + 2x 2 £ 12 ; 2x 1 + 4x 2 £ 10 .

Так как объёмы производства продукции не могут принимать отрицательные значения, то появляются ограничения неотрицательности:

x 1 ³ 0 ; x 2 ³ 0 .

Таким образом, математическая модель задачи представлена в виде: определить план x 1 , x 2 , обеспечивающий максимальное значение функции:

max F = max (2x 1 + 3x 2)

при наличии ограничений:

x 1 + 5x 2 £10;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 £ 10 .

x 1 ³ 0 ; x 2 ³ 0 .

3.2 Решение задачи вручную

Табличный метод ещё называется метод последовательного улучшения оценки. Решение задачи осуществляется поэтапно.

1. Приведение задачи к форме:

x 1 + 5x 2 £10;

3x 1 + 2x 2 £ 12 ;

2x 1 + 4x 2 £ 10 .

x 1 ³ 0 ; x 2 ³ 0 .

2. Канонизируем систему ограничений:

x 1 + 5x 2 + x 3 =10;

3x 1 + 2x 2 + x 4 = 12 ;

2x 1 + 4x 2 + x 5 = 10 .

x 1 ³ 0 ; x 2 ³ 0 .

A 1 A 2 A 3 A 4 A 5 A 0

3. Заполняется исходная симплекс-таблица и рассчитываются симплекс-разности по формулам:

- текущее значение целевой функции - расчёт симплекс-разностей, где j = 1..6 .
. Алгоритм симплекс-метода

Пример 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 итерации

				Оценочные отношения
				3/1=3 – min

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 итерации

				Оценочные отношения
				5/5=1 – min

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

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

IV итерация

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

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

Таблица 5.9

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

				Оценочные отношения
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

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 . Выразим базисные переменные через свободные.

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

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

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

Предприятие выпускает 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 руб.

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

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

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

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1

Исходная таблица для задачи имеет следующий вид:

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

x 1 , x 2 , x n - исходные переменные, x n+1 , x n+2 , x n+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные , а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным .

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

Подготовительный этап

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

F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → max

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1

a 2,1 x 1 +a 2,2 x 2 +...a 2,n x n +x n+2 =b 2

.......................................

a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m

В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a 0,n =-a 0,n . Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.

Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче

	x 1	x 2	...	x n-1	x n	b
F	-a 0,1	-a 0,2	...	-a 0,n-1	-a 0,n	-b 0
x n+1	a 1,1	a 1,2	...	a 1,n-1	a 1,n	b 1
x n+2	a 2,1	a 2,2	...	a 2,n-1	a 2,n	b 2
...	...	...	...	...	...	...
x n+m	a m,1	a m,2	...	a m,n-1	a m,n	b m

Шаг 1. Проверка на допустимость.

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

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

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

Шаг 2. Проверка на оптимальность.

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

Если в строке F есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки F максимальный по модулю (исключая значение функции b 0)

a 0,l =min{a 0,i }

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

b k /a k,l =min {b i /a i,l } при a i,l >0, b i >0

k - cтрока, для которой это отношение минимально - ведущая. Элемент a k,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (x k) исключается из базиса, переменная соответствующая ведущему столбцу (x l) включается в базис.

Пересчитываем симплекс-таблицу по . Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2

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

Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.

Правила преобразований симплексной таблицы.

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

• Вместо базисной переменной x k записываем x l ; вместо небазисной переменной x l записываем x k .
• ведущий элемент заменяется на обратную величину a k,l "= 1/a k,l
• все элементы ведущего столбца (кроме a k,l) умножаются на -1/a k,l
• все элементы ведущей строки (кроме a k,l) умножаются на 1/a k,l
• оставшиеся элементы симплекс-таблицы преобразуются по формуле a i,j "= a i,j - a i,l x a k,j / a k,l

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

Преобразуемый элемент a i,j и соответствующие ему три сомножителя как раз и являются вершинами ”прямоугольника”.

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Пример(1) решения задачи ЛП методом симплекс-таблиц
3.7. Пример(2) решения задачи ЛП методом симплекс-таблиц

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

x 1 + a 1,m+1* x m+1 + ... + a 1s* x s +...+ a 1n * x n = b 1 ;

x 2 + a 2,m +1* x m+1 + ... + a 2s * x s +...+ a 2n* x n = b 2 ;

x m + a m,m+1* x m+1 + ... + a ms* x s +...+ a mn* x n = b m .

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

3.1. Приведение математической модели к каноническому виду

Приведем математическую модель задачи к каноническому виду. Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства эксклюзивно, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменых: при ">=" - переменная вводится в неравенство с коэффициентом +1; при "<=" - с коэффициентом (-1).

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

Также можно переориентировать целевую функцию с минимума на максимум или наоборот умножив все коэффициенты при переменных в этой функции на (-1).

3.2. Векторный анализ

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

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

3.3. Метод искусственных переменных

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

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

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

Этап 2. Допустимое базисное решение, найденное на первом этапе, улучшается в соответствии с целевой функцией исходной задачи ЛП на основе симплекс-метода, т.е. оптимальная таблица 1 этапа превращается в начальную таблицу этапа 2 и изменяется целевая функция.

3.4. Построение симплекс-таблицы

Выбираем начальное допустимое базисное решение. Базисным решением называется решение, полученное при нулевых значениях небазисных переменных, т.е. x i =0, i=m+1,...,n. Базисное решение называется допустимым базисным решением , если значения входящих в него базисных переменных неотрицательны, т.е. x j = b j >=0, j=1,2,...,m. В этом случае целевая функция примет следующий вид: S = c b* x b = c 1* b 1 + c 2* b 2 +...+c m* b m . Заполняем первоначальную таблицу симплекс - метода:

Таблица 2.3

c b	x b	c 1	c 2	...	c m	c m+1	...	c n	b i
	базис	x 1	x 2	...	x m	x m+1	...	x n
с 1	x 1	1	0	...	0	a 1,m+1	...	a n	b 1
с 2	x 2	0	1	...	0	a 2,m+1	...	a 2 n	b 2
...	...	...	...	...	...	...	...	...	...
c m	x m	0	0	...	1	a m,m+1	...	a m n	b m
									S

3.5. Анализ симплекс-таблицы

1. Вычисляем вектор относительных оценок c при помощи правила скалярного произведения

c j = c j - c b* S j ,

где

с b - вектор оценок базисных переменных;

S j - j-тый столбец в канонической системе, соответствующей рассматриваемому базису.

Дополняем первоначальную таблицу c - строкой.

Таблица 2.4

базис x 1 x 2 ... x m x m+1 ... x n с 1 x 1 1 0 ... 0 a 1,m+1 ... a 1 n b 1 с 2 x 2 0 1 ... 0 a 2,m+1 ... a 2 n b 2 ... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 a m,m+1 ... a m n b m 0 0 ... 0 ... W

c b	x b	c 1	c 2	...	c m	c m+1	...	c n	b i
c- строка

3. Если все оценки c j <=0 (c j >= 0), i=1,...,n, то текущее допускаемое решение - максимальное (минимальное). Решение найдено.

4. Впротивном случае в базис необходимо ввести небазисную переменную x r с наибольшим значением c j вместо одной из базисных переменных (табл. 2.5).

1. При помощи правила минимального отношения min(b i /a ir) определяем переменную x p , выводимую из базиса. Если коэффициент a ir отрицателен, то b i /a ir = бесконечность. В результате пересечение столбца, где находится вводимая небазисная переменная x r и строки, где находится выводимая базисная переменная x p определит положение ведущего элемента таблицы (табл. 2.6).

Таблица 2.5

						c m+1					b i
	базис					x m+1
с 1						a 1,m+1		a 1 r		a 1 n
с 2						a 2,m+1		a 2 r		a 2 n
						a m,m+1		a m r		a m n	b m
c - строка

Таблица 2.6

c m+1

b i

b i / a ir

x m+1

с 1

a 1,m+1

a 1 r

a 1 n

b 1 /a 1r

с 2

a 2,m+1

a 2 r

a 2 n

b 2 /a 2r

с p

a p,m+1

a pr

a pn

b p /a pr

a m,m+1

a m r

a m n

b m

b m /a nr

c - стро - ка

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

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