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

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

Назначение сервиса . Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:

• в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
• модифицированным симплекс-методом ; в столбцовой форме; в строчечной форме.

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа x i ≥ 0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом . При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода .

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

Алгоритм симплекс-метода включает следующие этапы:

1. Составление первого опорного плана . Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
2. Проверка плана на оптимальность . Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
3. Определение ведущих столбца и строки . Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
4. Построение нового опорного плана . Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса .

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

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

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

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

Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.

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

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

Замечание 2 . Пусть в некоторой крайней точке все симплексные разности неотрицательные D k ³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой А k - небазисный вектор, у которого D k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x k , значение целевой функции не изменится.

Замечание 3 . Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей(в столбцах балансовых переменных) - оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.

Замечание 4 . При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.

Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.

Аналитическое введение в симплекс-метод

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

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

Например, пусть дана система

Здесь число уравнений равно 2, а неизвестных - 3, уравнений меньше. Выразим x 1 и x 2 через x 3:

Это общее решение системы. если переменной x 3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x 3 =1 → x 1 =1 → x 2 =6. Имеем (1, 6, 1) - частное решение. Пусть x 3 =2 → x 1 =-3, x 2 = 1, (-3, 1, 2) - другое частное решение. Таких частных решений бесконечно много.

Переменные x 1 и x 2 называются базисными , а переменная x 3 - не базисная, свободная .

Совокупность переменных x 1 и x 2 образует базис: Б (x 1 , x 2). Если x 3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x 1 , x 2).

Базисным называется решение, соответствующее нулевым значениям свободных переменных .
В качестве базисных можно было взять и другие переменные: (x 1 , x 3) или (x 2 , x 3).
Как переходить от одного базиса Б (x 1 , x 2) к другому базису Б (x 1 , x 3)?
Для этого надо переменную x 3 перевести в базисные, а x 2 - в небазисные т. е. в уравнениях надо x 3 выразить через x 2 и подставить в 1-е:

Б (x 1 , x 3 ), таково: (-19/5; 0; 11/5).

Если теперь от базиса Б (x 1 , x 3) нам захочется перейти к базису Б (x 2 , x 3), то

Базисное решение, соответствующее базису Б (x 2 , x 3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x 1 , x 3) - отрицательное x 1 < 0, нас в ЗЛП интересуют только неотрицательные решения.

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

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

Пример . Решить задачу ЛП.

Функцию F = x 2 - x 1 → min необходимо минимизировать при заданной системе ограничений:
-2x 1 + x 2 + x 3 = 2
x 1 + x 2 + x 5 = 5
x 1 - 2x 2 + x 4 = 12
x i ≥ 0, i = 1, 5

Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x 3 , x 5 , x 4 - как дополнительные.
Запишем ограничения, выбрав базис из переменных Б { x 3 , x 4 , x 5 }:

Этому базису соответствует базисное неотрицательное решение
x 1 = 0, x 2 = 0, x 3 = 2, x 4 = 2, x 5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F = x 2 - x 1 .
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F = 0 - 0 = 0 - значение функции равно 0. Но его можно уменьшить, если x 1 будет возрастать, т. к. коэффициент в функции при x 1 отрицателен. Однако при увеличении x 1 значения переменных x 4 , x 5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x 1 не может быть увеличена больше чем до 2, иначе x 4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x 5 - отрицателен. Итак, из анализа равенств следует, что переменную x 1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б 2 , введя переменную x 1 в базис вместо x 4 .
Б 2 {x 1 , x 3 , x 5 }.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x 1 из второго уравнения и подставим в остальные, в том числе и в функцию.

Базисное решение, соответствующее базису Б 3 {х 1 , х 2 , х 3 }, выписывается (4, 1, 9, 0, 0), и функция принимает значение F = -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x 4 = 0, x 5 = 0 значение F = -3. как только x 4 , x 5 станут положительными, значение F только увеличится, т. к. коэффициенты при x 4 , x 5 положительны. Значит, функция F достигла своего оптимального значения F * = -3. Итак, наименьшее значение F , равное -3, достигается при x 1 * = 4, x 2 * = 1, x 3 * = 9, x 4 * = 0, x 5 * = 0.

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

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

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

Симплекс-метод – один из наиболее эффективных методов численного решения задач ЛП. Суть понятия «симплекс» заключается в следующем. Для тела в k -мерном пространстве симплексом называется множество, состоящее из k +1 вершин этого тела. Так, при k = 2, т.е. на плоскости, симплексом будут вершины треугольника; при k = 3 симплексом являются вершины четырехгранника, например тетраэдра, и т.д. Такое название методу дано по той причине, что в его основе лежит последовательный перебор вершин ОДЗП с целью определения координат той вершины, в которой функция цели имеет кстремальное значение.

Разбивается на два основных этапа. На первом этапе находят одно из решений, удовлетворяющее системе ограничений . Системы, в которых переменных больше, чем ограничений N > m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных. При этом остается система m уравнений с m неизвестными, которая имеет решение, если определитель системы отличен от нуля. В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободными переменными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получим базисное решение.

В системе из m уравнений с N неизвестными общее число базисных решений при N > m определяется числом сочетаний

Базисное решение, в котором все x i 0, i = 1,m , называется допустимым базисным решением. Таким образом, первый этап решения, используя симплекс-метод, завершается нахождением допустимого базисного решения, хотя бы и неудачного.

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

1) базисные переменные и функция цели выражаются через небазисные переменные;

2) по определенному правилу выбирается та из небазисных переменных, изменение значения которой способно улучшить значение F(x) , и она вводитя в базис;

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

4) базисные переменные и функция цели выражаются через новые небазисные переменные, и повторяются операции 2) и 3).

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

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

Пример 1. На приобретение оборудования для нового участка выделено 20 тыс. y.e. Оборудование должно быть размещено на площади, не превышающей 72 м 2 . Может быть заказано оборудование двух видов: 1) оборудование стоимостью 5 тыс. y.e., занимающее площадь 6 м 2 и дающее 8 тыс. ед. продукции за смену; 2) оборудование стоимостью 2 тыс. y.e., занимающее площадь 12 м 2 и дающее за смену 4 тыс. ед. продукции. Найти оптимальный вариант приобретения оборудования, обеспечивающий максимум общей производительности участка, используя симплекс-метод.

Обозначим неизвестное количество оборудования первого и второго видов соответственно через x 1 и x 2 . Функция цели может быть записана следующим образом: F(x) = 8x 1 + 4x 2 (max). Ограничения по площади: 6x 1 +12x 2 ≤72; ограничения по стоимости: 5x 1 + 2x 2 ≤20 ; ограничения на знак переменных x 1 ≥0 ; x 2 ≥0.

Разделим коэффициенты первого из ограничений на 6 и приведем ограничения к виду равенств, вводя дополнительные переменные x 3 и x 4:

x 1 + 2x 2 + x 3 =12, (1)

5x 1 + 2x 2 + x 4 = 20 . (2)

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

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

Тогда x 1 и x 3 будут небазисными переменными (НП). Выразим базисные переменные и F(x) через небазисные.

(3)

Из второго ограничения следует, что

x 4 = 20 - 2x 2 - 5x 1 . (4)

С учетом выше приведенного выражения получим

x 4 = 8 - 4x 1 + x 3 . (5)

Тогда

F(x) = 8x 1 + 4x 2 = 24 + 6x 1 - 2x 3 . (6)

На каждом шаге НП приравниваются к нулю, следовательно, БП и F(x) будут равны свободным членам в соответствующих выражениях:

x 1 = 0, x 3 = 0, x 2 = 6, x 4 = 8, F(x) = 24.

Это решение соответствует координатам вершины A ОДЗП на рис. 1. Оптимальность решения проверяется по выражению F(x) для функции цели. Переменная x 3 входит в это выражение с отрицательным коэффициентом; если вводить x 3 в базис на следующем шаге, то она примет положительное значение, и от числа 24 некоторая величина будет вычитаться, т.е. значение F(x) уменьшится. Если же вводить в базис на следующем шаге x 1 , то значение функции цели увеличится, т.е. улучшится.

Применяя симплекс-метод, из базиса исключают ту переменную, которая раньше обратится в нуль при введении в базис x 1 . Анализируя (3) и (5), определяем, что из базиса следует исключить x 4 . На следующем шаге местами поменяются переменные x 1 и x 4 .

2-й шаг симплекс-метода. x 1 и x 2 – базисные переменные, x 3 и x 4 – небазисные. Выразим базисные переменные и F(x) через небазисные переменные. Из (5) следует

x 1 =2+(1/4)x 3 -(1/4)x 4 (7)

Рис. 1. Графическая интерпритация к примеру 1, используя симплекс-метод.

Подставив (7) в (3), получим

x 2 =5-(5/8)x 3 +(1/8)x 4

Тогда F(x) = 8x 1 + 4x 2 = 36 - (1/2)x 3 -(3/4)x 4 . В результате x 3 = x 4 = 0 (как небазисные), x 1 = 2, x 2 = 5, F = 36 . Это решение соответствует координатам вершины В на рис. 1. Найденное будет оптимальным, улучшить значение F(x) нельзя, так как переменные x 3 и x 4 входят в выражение для функции цели с отрицательными коэффициентами.

Таким образом, применяя симплекс-метод, нашли, что максимальная производительность участка 36 тыс. ед. продукции за смену будет обеспечена при закупке 2 ед. оборудования первого вида и 5 ед. оборудования второго вида. Дополнительные переменные x 3 и x 4 имеют смысл неиспользованных ресурсов. В данном примере все ресурсы по площади и по стоимости использованы полностью (x 3 = x 4 = 0).

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

1. Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3стр

2. Симплексный метод решения задач линейного программирования. . . 4-10стр

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

4. Пример решения задачи симплексным методом. . . . . . . . . . . . . . . . . . 11-15стр

5.Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .16стр

6.Список используемой литературы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17стр

1. Введение

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

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

1. Указать способ нахождения оптимального опорного решения

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

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

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

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

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

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

Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как

К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.

Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.

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

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе к другим базисным решениям.

Реализация решения задачи симплекс-методом наглядно показана на блок-схеме (рис.1).

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

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

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

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

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

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

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

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

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

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

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

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

Содержание

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

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

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

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

Пусть x 1 , x 2 , x 3 - количество реализованных товаров, в тыс. руб., 1, 2, 3 - ей групп, соответственно. Тогда математическая модель задачи имеет вид:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

= 26.667

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

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

Вычисляем:

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

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

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

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

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

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

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

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

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

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

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

Вычисляем:

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

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

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

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

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

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

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

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

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

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

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

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

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

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

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

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

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

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

Y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;