Решение задач линейного программирования
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу.
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
- Шаг №1
- Шаг №2
- Видеоинструкция
- Оформление Word
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:
| F(x) → min | F(x) → max |
Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.
Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.
Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x1 + 2x2 — 2x3 → min при ограничениях:
4x1 + 3x2 — x3≤10
— 2x2 + 5x3≥3
x1 + 2x3=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x4; во втором неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
4x1 + 3x2-1x3 + 1x4 + 0x5 = 10
0x1-2x2 + 5x3 + 0x4-1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = — x1 — 2x2 + 2x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(0 • 3):-2 | 3-(-2 • 3):-2 | -1-(5 • 3):-2 | 1-(0 • 3):-2 | 0-(-1 • 3):-2 | 10-(3 • 3):-2 |
| 0 : -2 | -2 : -2 | 5 : -2 | 0 : -2 | -1 : -2 | 3 : -2 |
| 1-(0 • 0):-2 | 0-(-2 • 0):-2 | 2-(5 • 0):-2 | 0-(0 • 0):-2 | 0-(-1 • 0):-2 | 9-(3 • 0):-2 |
Получаем новую матрицу:
| 4 | 0 | 6 1 /2 | 1 | -1 1 /2 | 14 1 /2 |
| 0 | 1 | -2 1 /2 | 0 | 1 /2 | -1 1 /2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 • 6 1 /2):2 | 0-(0 • 6 1 /2):2 | 6 1 /2-(2 • 6 1 /2):2 | 1-(0 • 6 1 /2):2 | -1 1 /2-(0 • 6 1 /2):2 | 14 1 /2-(9 • 6 1 /2):2 |
| 0-(1 • -2 1 /2):2 | 1-(0 • -2 1 /2):2 | -2 1 /2-(2 • -2 1 /2):2 | 0-(0 • -2 1 /2):2 | 1 /2-(0 • -2 1 /2):2 | -1 1 /2-(9 • -2 1 /2):2 |
| 1 : 2 | 0 : 2 | 2 : 2 | 0 : 2 | 0 : 2 | 9 : 2 |
Получаем новую матрицу:
| 3 /4 | 0 | 0 | 1 | -1 1 /2 | -14 3 /4 |
| 1 1 /4 | 1 | 0 | 0 | 1 /2 | 9 3 /4 |
| 1 /2 | 0 | 1 | 0 | 0 | 4 1 /2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 /4x1 + x4 — 1 1 /2x5 = -14 3 /4
1 1 /4x1 + x2 + 1 /2x5 = 9 3 /4
1 /2x1 + x3 = 4 1 /2
Выразим базисные переменные через остальные:
x4 = — 3 /4x1 + 1 1 /2x5-14 3 /4
x2 = — 1 1 /4x1 — 1 /2x5+9 3 /4
x3 = — 1 /2x1+4 1 /2
Подставим их в целевую функцию:
F(X) = — x1 — 2(- 1 1 /4x1 — 1 /2x5+9 3 /4) + 2(- 1 /2x1+4 1 /2)
или
F(X) = 1 /2x1 + x5-10 1 /2 → max
Система неравенств:
— 3 /4x1 + 1 1 /2x5-14 3 /4 ≥ 0
— 1 1 /4x1 — 1 /2x5+9 3 /4 ≥ 0
— 1 /2x1+4 1 /2 ≥ 0
Приводим систему неравенств к следующему виду:
3 /4x1 — 1 1 /2x5 ≤ -14 3 /4
1 1 /4x1 + 1 /2x5 ≤ 9 3 /4
1 /2x1 ≤ 4 1 /2
F(X) = 1 /2x1 + x5-10 1 /2 → max
Упростим систему.
3 /4x1 — 1 1 /2x2 ≤ -14 3 /4
1 1 /4x1 + 1 /2x2 ≤ 9 3 /4
1 /2x1 ≤ 4 1 /2
F(X) = 1 /2x1 + x2-10 1 /2 → max
Алгоритм симплексного метода решения задачи линейного программирования.
- Получить нулевое уравнение. Для этого функцию цели выразить через свободные переменные имеющегося опорного решения и перенести все переменные в левую часть. Присоединить нулевое уравнение к системе ограничений как дополнительное уравнение.
- Рассмотреть оценки свободных переменных. Если все оценки неотрицательны (неположительны), то имеющееся решение доставляет максимум (минимум) функции цели. Если в задаче требуется найти максимум (минимум), то выписать найденное оптимальное решение и соответствующее максимальное (минимальное) значение функции цели. В противном случае в качестве разрешающего выбрать столбец p, которому соответствует отрицательная (положительная) оценка.
- Найти соотношения
для всех,В качестве разрешающей выбрать строку, которой соответствует наименьшее из найденных соотношений. - Выполнить одну итерацию метода Жордано-Гауса. Перейти к пункту 2.
для всех
,
В качестве разрешающей выбрать строку, которой соответствует наименьшее из найденных соотношений.Особые случаи решения задач симплекс-алгоритмом.
- После выбора разрешающего столбца может оказаться, что что разрешающую строку выбрать невозможно. Это может быть только тогда, когда среди коэффициентов разрешающего столбца нет положительных элементов. В этом случае задача линейного программирования решений не имеет.
- После отыскания оптимального решения оценки некоторых свободных переменных равны нулю. Это значит, что имеет место альтернативный оптимум. Действительно, если ввести в базис переменную, имеющую нулевую оценку, то получится другое, также оптимальное решение.
- После выбора разрешающего столбца и нахождения отношений вида имеет несколько таких минимальных отношений. Если выбор разрешающей строки производить бессистемно, то может произойти «зацикливание», т.е. ситуация, когда циклически находится некоторая группа одних и тех же опорных решений. В этом случае для предотвращения зацикливания в качестве разрешающей следует всегда выбирать строку с наименьшим номером в системе ограничений.
имеет несколько таких минимальных отношений. Если выбор разрешающей строки производить бессистемно, то может произойти «зацикливание», т.е. ситуация, когда циклически находится некоторая группа одних и тех же опорных решений. В этом случае для предотвращения зацикливания в качестве разрешающей следует всегда выбирать строку с наименьшим номером в системе ограничений.Пример. Решить задачу симплекс-методом. 
Решение.
- Ранг матрицы системы уравнений
равен 4. Ранг расширенной матрицы также равен 4, следовательно, четыре переменные (базисные) можно выразить через две (свободные), т.е. 
. Причем целевая функция 
выражена через эти же свободные переменные. Составим следующую таблицу.
 |  |  |  |  |  | Свободные члены |
| 2 | 3 | 1 | 0 | 0 | 0 | 19 |
| 2 | 1 | 0 | 1 | 0 | 0 | 13 |
| 0 | 3 | 0 | 0 | 1 | 0 | 15 |
| 3 | 0 | 0 | 0 | 0 | 1 | 18 |
| -7 | -5 | 0 | 0 | 0 | 0 | 0 |
В индексной строке два отрицательных элемента: -7 и -5. Например, выбираем -5. Просматривая столбец для 
и выбираем наименьший результат. Он соответствует выделенной строке в таблице. Т.о. получили разрешающий элемент 3, стоящий на пересечении третьей строки и второго столбца. Все элементы выделенной строки делим на 3, а к каждой из остальных строк прибавляем вновь полученную, умноженную на такое число, чтобы в клетках столбца для 
появились нули. Этим завершается первая итерация.
- Далее все рассуждения повторяются для второй таблицы. Новый разрешающий элемент есть 2.
 |  |  |  |  |  | Свободные члены |
| 2 | 0 | 1 | 0 | -1 | 0 | 4 |
| 2 | 0 | 0 | 1 | -1/3 | 0 | 8 |
| 0 | 1 | 0 | 0 | 1/3 | 0 | 5 |
| 3 | 0 | 0 | 0 | 0 | 1 | 18 |
| -7 | 0 | 0 | 0 | 5/3 | 0 | 25 |
3)Те же рассуждения применяем к третьей таблице.
 |  |  |  |  |  | Свободные члены |
| 1 | 0 | 1/2 | 0 | -1/2 | 0 | 2 |
| 0 | 0 | -1 | 1 | 2/3 | 0 | 4 |
| 0 | 1 | 0 | 0 | 1/3 | 0 | 5 |
| 0 | 0 | -3/2 | 0 | 3/2 | 1 | 12 |
| 0 | 0 | 7/2 | 0 | -11/6 | 0 | 39 |
4)Далее получим
 |  |  |  |  |  | Свободные члены |
| 1 | 0 | -1/4 | 3/4 | 0 | 0 | 5 |
| 0 | 0 | —3/2 | 3/2 | 1 | 0 | 6 |
| 0 | 1 | 1/2 | -1/2 | 0 | 0 | 3 |
| 0 | 0 | 3/4 | -9/4 | 0 | 1 | 3 |
| 0 | 0 | 3/4 | 11/4 | 0 | 0 | 50 |
Поскольку в индексной строке нет отрицательных оценок мы получили оптимальный план (5, 3, 0, 0, 6, 3) и наибольшее значение целевой функции 
. Метод искусственного базиса применяется для решения задач линейного программирования симплексным методом в случае, когда задача не имеет начального опорного решения с базисом из единичных векторов. Согласно данному методу для задачи линейного программирования составляется так называемая расширенная задача, которая решается симплексным методом. На основе результатов решения расширенной задачи либо находится оптимальное решение исходной задачи, либо устанавливается причина ее отсутствия. Пусть имеется каноническая задача линейного программирования 
, 
(j=1,2,…,l, l
). Без ограничений общности можно считать, что правые части уравнений системы ограничений неотрицательны. Для исходной задачи составляют расширенную, используя при этом искусственные переменные. Искусственными переменными называют неотрицательные переменные, которые вводятся в ограничения-равенства для получения начального опорного решения с базисом из единичных векторов. Каждая искусственная переменная вводится в левую часть одного из уравнений системы ограничений с коэффициентом +1 и в целевую функцию в задаче на минимум с коэффициентом +М, а в задаче на максимум с коэффициентом –М. число М сколь угодно большое по сравнению с единицей. В общем случае расширенная задача на максимум имеет вид: 
,
(j=1,2,…,l,l
). Если расширенная задача линейного программирования имеет оптимальное решение 
, у которого все искусственные переменные равны нулю, то исходная задача имеет оптимальное решение 
, которое получается из 
отбрасыванием нулевых искусственных переменных (признак оптимальности решения). Если расширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная отлична от нуля, то исходная задача не имеет решения виду несовместности системы ограничений (признак отсутствия решения ввиду несовместности системы ограничений). Если расширенная задача не имеет решения, ввиду неограниченности целевой функции, то исходная задача не имеет решения по той же причине (признак отсутствия решения ввиду неограниченности).