Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
учить простейшее частное решение системы необходимо свободные переменные приравнять нулю, учитывая при этом неотрицательность всех переменных.
Допустимым базисным решением (ДБР) является такое, при котором все переменные неотрицательны. В противном случае базисное решение недопустимо.
Частное допустимое базисное решение, с которого начинают решение, называют начальным допустимым базисным решением (НДБР).
Чтобы найти НДБР, удобно ЗЛП записать в каноническом виде.
Канонический вид ЗЛП - это такой стандартный вид, в котором в каждом i-ом уравнении найдется такая переменная хI, что коэффициент перед ней в данном уравнении равен +1, а в других уравнениях и в выражении целевой функции эти коэффициенты равны нулю. Если при этом все b , то говорят о допустимом каноническом виде, в противном случае - о недопустимом.
Например.
Случай. Исходная задача ЗЛП содержит все ограничения со знаком .
, , ,(x) = .
Стандартная форма ЗЛП является одновременно и каноническим допустимым видом.
, , ,
, - дополнительные, уравновешивающие переменные
(x) = - .
При этом хj = 0, - свободные переменные, хn+I = bi, - - базисные переменные - НДБР.
Случай. Ограничения исходной ЗЛП содержат неравенства разных знаков и уравнения.
, , ,
,
, , , (x) = .
Стандартная форма ЗЛП не совпадает с каноническим видом.
, ,
, ,
, ,
, - дополнительные, уравновешивающие переменные.(x) = - .
Чтобы построить канонический вид и получить НДБР используют метод искусственного базиса. В каждое уравнение, не содержащее переменную, создающую канонический вид, вводят искусственную неотрицательную переменную.
, ,
, , ,
, , , (x) = - .
Новые искусственные переменные создают канонический вид. Однако, вводя в ограничения-равенства искусственную переменную, изменяют исходные условия.
Чтобы преобразованная задача соответствовала исходной, необходимо, чтобы в окончательном решении искусственные переменные равнялись нулю. Этого можно достичь, если вспомогательная целевая функция, равная сумме искусственных переменных, будет равна нулю, то естьb
G(x) = или G(x) = .
Оптимальное решение вспомогательной задачи соответствует НДБР исходной задачи.
3. Симплекс-метод
При решении ЗЛП симплекс-методом удобно представить задачу в табличном виде.
№б.п.х1...хj*...xnb0xa1a11...a1j*...a1nb1.....................xai*ai*1...ai*j*...ai*nbi*.....................xamam1...amj*...amnbmF(x)C1...Cj*...CnF0
ПРИЗНАК ОПТИМАЛЬНОСТИ. План х* = (х1, х2, ..., хn) считается оптимальным, если все коэффициенты целевой функции неотрицательны, Сj 0,. Тогда значение Fmax равно значению, стоящему в правом нижнем углу таблицы.
Если имеется хотя бы один отрицательный коэффициент целевой функции, следует перейти к новому базисному решению, значение целевой функции при котором будет меньше. Для этого используют следующие правила:
- Среди отрицательных коэффициентов целевой функции выбирают максимальный по модулю. Столбец, в котором стоит этот коэффициент, называют разрешающим и помечают *.
Находят отношения , т.е. отношения свободных членов ограничений к элементам матрицы коэффициентов ограничений, стоящим в разрешающем столбце и имеющим положительные значения. Среди этих отношений выбирают минимальное. Строка, в которой стоит это минимальное отношение, называется разрешающий и помечается *. Если среди элементов разрешающего столбца не будет ни одного положительного, то задача оптимизации не имеет решения.
- Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим и отмечается .
- Производится замена базисного допустимого решения на другое, при этом таблица будет иметь следующее содержание:
а) свободная переменная хj*, стоящая в разрешающем столбце, становится базисной, а
базисная переменная хai* , стоящая в разрешающей строке, - свободной;
б) все элементы разрешающей строки в новой таблице имеют значения
(штрихом отмечены новые значения);
в) все остальные элементы таблицы определяются по формулам:
(ii*), (ii*),
(ii*), .
Каждая новая таблица проверяется на оптимальность. Операции 1)-4) осуществляются до тех пор, пока не будет получено оптимальное значение целевой функции.
Лекция 4, 5
Устойчивость решений ЗЛП при небольших изменениях условий. Двойственный симплекс-метод
Вопросы:
. Обращенный базис, симплекс - множители.
. Изменение значений правых частей ограничений.
. Изменение значений коэффициентов целевой функции.
. Включение дополнительных переменных.
. Включение дополнительных ограничений.
. Двойственный симплекс-метод.
. Проблемы вырождения, зацикливания.
1. Обращенный базис, симплекс - множители
Рассмотрим решение ЗЛП симплекс-методом с точки зрения алгебры. В матричном виде стандартная форма ЗЛП имеет вид: , Ах = b, где Аmxn. Представим матрицу А в виде склеенных двух матриц А = Вmxm Rmx(n-m). Здесь Вmxm - матрица, состоящая из столбцов матрицы А, соответствующих переменным, которые в оптимальной таблице являются базисными. Матрица Rmx(n-m) состоит из всех оставшихся столбцов. Предположим известна матрица В-1. Умножим слева ограничения ЗЛП на В-1:
В-1(ВR)x = B-1b, здесь х = (хб.п., хсв.п.) (ЕmB-1R)x = B-1b xб.п. = B-1b, хсв.п. = 0.
В НДБР б