[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

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

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

Задача 5.3

Решить симплексным методом задачу F = x1 + 2 x2 max при ограничениях: x1 - x2 <= -1, x1 - x2 >= -3, x1 <= 3, Решение. Вводим дополнительные неотрицательные переменные x3, x4, x5 с соответствующими знаками: x1 - x2 + x3 = -1, x1 - x2 - x4 = -3, x1 + x5 = 3, В соответствии с правилом, на I шаге в качестве основных возьмем выравнивающие переменные. I шаг. Основные переменные: x3,x4,x5. Неосновные переменные: x1, x2. Выражаем основные переменные через неосновные: x3 = -l - x1 + x2, x4 = 3 + x1 - x2, x5 = 3 - x1 X1 =(0; 0; -1; 3; 3) - первое базисное решение недопустимое (отрицательная компонента выделена), поэтому оно не может быть оптимальным. Линейную функцию на недопустимом решении не рассматриваем. В системе выберем то уравнение, которое содержит отрицательный свободный член, т.е. первое уравнение (если таких уравнений несколько, выбираем любое из них). Поскольку переменная x3 принимает отрицательное значение при первом базисном решении, то ее необходимо увеличить. Это можно сделать за счет увеличения любой из неосновных переменных, входящих в первое уравнение с положительным коэффициентом, в данном случае - переменной x2. Если перевести эту переменную в основные, то она, став положительной, увеличит переменную x3. Как только x2 достигнет уровня 1, то x3 обратится в 0, т.е. исчезнет отрицательная компонента в решении. Можно считать, что переменная x3 станет неосновной. Однако рост переменной x3 ограничен условиями неотрицательности остальных переменных, которые определяют x2 = min{1; 3; } = 1, т.е. первое уравнение - разрешающее. При x2 = 1 переменная x3 = 0 и переходит в неосновные переменные. II шаг Основные переменные: x2,x4,x5. Неосновные переменные:x1, x3. Выражая новые основные переменные через новые неосновные, начиная с разрешающего уравнения, получаем x2= 1 + x1 + x3, x4= 2 - x3, x5= 3 - x1 . и базисное решение X2 = (0; 1; 0; 2; 3), которое является допустимым. поэтому выражаем через неосновные переменные линейную функцию F = х1+ х2 = 2 + 3х1 + 2х3 и продолжаем решение в соответствии с алгоритмом, ( проведите его самостоятельно).

[Список тем] [Вступление к этой теме] страницы темы: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [В начало страницы]