Читайте также:
|
|
Чтобы приступить к решению задачи линейного программирования симплексным методом, необходимо выбрать исходный базис. Выбор исходного базиса зависит от системы ограничений. Система ограничений задачи линейного программирования может быть записана в трех основных формах.
1. Система записана неравенством вида ≤ (меньше или равно).
2. Ограничения задачи линейного программирования выражены линейными уравнениями
3. Ограничения задачи выражены неравенством вида ≥ (больше или равно). При ограничениях, записанных по первой форме, в уравнения вводятся свободные переменные (по одной свободной переменной в каждом соотношении), которые и включаются в исходный базис.
Если ограничения записаны в виде равенств (вторая форма ограничений), то возможны следующие приемы.
1. Если некоторая переменная входит только в j-e уравнение (соотношение), причем с коэффициентом, равным единице, то ее можно включить в исходный базис.
2. Ограничения, выраженные в виде равенств, записываются в следующем виде:
где: уi - искусственная переменная, ввод которой делается с целью построения исходного базиса.
Чтобы окончательное решение имело смысл, каждая искусственная переменная у,- на заключительной симплекс-итерации должна обращаться в нуль. Если на последней симплекс-итерации по крайней мере одна из переменных уi войдет в базис с положительным значением, то это означает несовместимость условий задачи, т. е. задача не имеет допустимых решений.
3. Если ограничения задачи выражены неравенством ≥, то в левую часть неравенств вводятся неотрицательные переменные с коэффициентом (-1). В полученных уравнениях дополнительные переменные не могут быть приняты за базисные, так как они входят в уравнения с отрицательным коэффициентом. Для нахождения допустимого исходного базиса, в этом случае может быть задан конкретный набор переменных, предназначенный для формирования исходного базиса.
При некоторых итерациях вычислительные процедуры, предписанные правилами 1 и 2, в части, касающейся перехода от одного базиса к другому, могут оказаться неоднозначно определенными. Например, когда в результате оценки коэффициентов в строке 0 две или более двух переменных являются по правилу 1 в равной степени «перспективными» с точки зрения улучшения пробного решения, выбор одной из этих переменных осуществляется произвольным способом.
Если, согласно правилу 2, две или более двух переменных промежуточного базиса должны одновременно принять нулевые значения в силу включения в очередной базис новой переменной, из старого базиса подлежит исключению только одна из них. Другие переменные из упомянутых переменных остаются в базисе, принимая при этом нулевые значения. Базис, полученный в результате такой замены, называется вырожденным.
Если на этапе применения правила 1 при выполнении какой-либо итерации обнаруживается, что ни в одну из строк ограничений переменная, включенная в очередной базис, не входит с положительным коэффициентом, то оптимальное решение является неограниченным. В этом случае значение новой базисной переменной можно (без нарушения условия неотрицательности остальных переменных) выбирать сколь угодно большим, что приводит к неограниченному возрастанию значения целевой функции.
Дата добавления: 2015-08-09; просмотров: 349 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
Вычислительная процедура симплексного метода | | | Анализ модели на чувствительность |