Н. В. Куцубина системный анализ при принятии решений
жүктеу/скачать 6,77 Mb. Pdf көрінісі
|
| х
2 + 3 х 4 − 3 х 5 при ограничениях х 1 + х 2 + х 4 − х 5 + х 6 = 7, х 1 − х 2 + х 4 − х 5 + х 7 = 2, -3 х 1 + х 2 − 2 х 4 − 2 х 5 = 5, х 1 , х 2 , х 3 , х 4 , х 5 , х 6 , х 7 ≥ 0. Используя стандартную форму, получаем в матричных обозначениях: максимизировать Z = cx при ограничениях Ах = b, x ≥ 0. Основные определения можно сформулировать следующим образом: – допустимое решение представляет собой неотрицательный вектор х , для которого выполняются ограничения Ах = В ; – допустимая область S состоит из всех допустимых решений; – оптимальным решением называется такой допустимый вектор x 0 , для которого целевая функция сх 0 больше любого другого допустимого решения, т.е. тогда, когда x 0 S и cx 0 ≥ cx для вcex x 0 S; – оптимальное значение задачи. Пусть Z 0 – значение целевой функ- ции, соответствующее оптимальному значению, т.е. Z 0 = cx 0 ; – неединственность оптимального решения соответствует случаям, когда задача линейного программирования имеет более одного оптималь- ного решения; – неограниченный оптимум соответствует случаю, когда задача линейного программирования не обладает конечным оптимумом, т.е. max Z → ∞ или min Z → ∞ . При решении задач линейного программирования число уравнений меньше числа переменных ( m n ), т. е. задача имеет бесконечное множе- ство решений. Классическим методом решения систем линейных уравне- ний является метод Гаусса - Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду с помощью элементарных операций над строками: – умножением любого уравнения системы на положительное или от- рицательное число; – прибавлением к любому уравнению другого уравнения системы, умноженного на положительное или отрицательное число. В результате элементарных преобразований коэффициент при неко- торой переменной в одном из уравнений системы сводят к единице, в дру- гих уравнениях - к нулю. Переменные x 1 , x 2 ,..., x m , входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми – в остальные, называются базисными или зависимыми. Остальные n – m переменные ( x m +1 ,..., x m ) называются небазисными или независимыми переменными. Электронный архив УГЛТУ 107 При использовании m переменных ( x 1 , x 2 , ... , x m ) каноническая систе- ма имеет вид: + , + ⋯ + = ............................................................ + , + ⋯ + = . Допустимое базисное решение канонической системы имеет вид : = … = ; = ⋯ = = 0. Базисное решение называется допустимым базисным решением, если значения входящих в него переменных неотрицательны. В теории линейного программирования доказывается, что любая вершина допустимой области соответствует некоторому допустимому ре- шению системы ограничений. Поэтому оптимальное решение задачи ли- нейного программирования по методу Гаусса - Жордана состоит в нахож- дении всех возможных базисных решений и последующем выборе реше- ния, которому соответствует наилучшее значение целевой функции. При симплекс-методе анализируется лишь часть всех допустимых базисных решений по следующему алгоритму: 1) выбор начального допустимого базисного решения; 2) переход от начального решения к другому допустимому базисно- му решению с лучшим значением целевой функции; 3) продолжение поиска допустимых базисных решений, улучшаю- щих значение целевой функции. Если некоторое допустимое базисное ре- шение нельзя улучшить, оно является оптимальным. Решение завершается. Множество базисных переменных называется базисом жүктеу/скачать 6,77 Mb. Достарыңызбен бөлісу:
|