Шпаргалка по Математическому программированию (стр. 3 из 8)
2. Преобразование ограничений. Если какое–либо из ограничений в модели имеет вид неравенства, то оно преобразуется в равенство прибавлением (если неравенство имеет тип ≤) или вычитанием (если неравенство имеет тип ≥) из его левой части. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая – Х7 и т.д.
16. Переход от канонической формы модели ЗЛП к стандартной
Для перехода от канонической формы к стандартной можно каждое из
уравнений заменить системой неравенств:
Другой способ состоит в приведении системы уравнений к специальному виду и дальнейшему исключению некоторых переменных.
С помощью метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое выделение осуществляется с помощью эквивалентных (элементарных) гаусовских преобразований. К ним относятся:
а) умножение любого уравнения на константу отличную от нуля;
б) прибавление к любому уравнению любого другого уравнения, умноженного на любую константу.
Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:
Далее находим х1, х2 … хn . Далее подставляем в целевую функцию z выражениех1 и х2 … хn.
Записываем задачу в стандартной форме.
17. Понятие гиперплоскости полуплоскости, опорная гиперплоскость.
18. Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП
19. Выпуклое множество: крайние (угловые) точки множества. Выпуклый многогранник
Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий.
 |
Выпуклое множество
Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
Теорема 1. Любую точку отрезка можно представить в виде выпуклой комбинации его угловых точек.
х = λ1 А + λ2 В
λ1, λ2 ≥ 0 выпуклая комбинация точек угловых точек А и В
λ1 + λ2 = 1
Теорема 2. Любую точку выпуклого замкнутого множества можно представить в виде выпуклой комбинации его угловых точек.
20. алгоритм графического метода решения задач ЛП
Алгоритм графического метода.
1. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме.
2. Проверяется количество неизвестных переменных. Если это количество больше трёх, то задача не может быть решена графическим методом (существуют другие эффективные методы решения таких задач).
3. Строится область допустимых значений переменных для ЗЛП.
4. Строится направляющий вектор c .
5. Через ОДЗ проводится исходная изоцель (перпендикулярно направляющему вектору).
6. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.
7. Для того, чтобы определить координаты оптимальной точки, необходимо решить систему соответствующих линейных уравнений.
8. Для нахождения оптимального значения целевой функции необходимо оптимальные значения переменных подставить в целевую функцию и вычислить её значение.
20. алгоритм графич. метода решения задач ЛП
Алгоритм графического метода.
1. Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.
2. Строится направляющий вектор С по коэффициентам при переменных целевой функции.
3. Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.
4. Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи.
5. Для определения координат оптимальной точки необходимо решить систему соответствующих линейных уравнений тех условий, на пересечении которых находится оптимальная точка.
6. Для нахождения оптимального значения целевой функции, необходимо координаты оптимальной точки подставить в целевую функцию и вычислиь ее значение.
23. теоремы об области допустимых значений задачи ЛП и о целевой ф-ции
Теорема об ОДЗ. Область допустимых решений задачи ЛП выпуклое множество (замкнутое и ограниченное в n-мерном пространстве)
Теорема 2. О целевой функции задачи линейного программирования.
Целевая функция ЗЛП принимает своё оптимальное значение в одной из угловых точек области допустимых значений переменных. Если целевая функция принимает своё оптимальное значение в нескольких угловых точках, то такое же значение она принимает и в любой точке, являющейся выпуклой комбинацией данных угловых точек.
24. Теорема об угловой точке. Достаточное и необходимое условие
25. Следствия из теоремы о свойствах решений задач ЛП и выводы. Понятие опорного плана.
Следствия из теорем.
Определение. План 
= (х1,х2,…,хn), положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП.
Следствие1. Опорный план имеет не более m положительных координат.
Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае вырожденным.
Следствие 2. Каждая угловая точка ОДЗ является опорным планом.
27. Алгоритм симплексного метода.
При решении задач ЛП симплексным методом необходимо выполнить следующую последовательность действий.
1. Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.
2. Выделяется начальный опорный план и значение целевой функции при этом опорном плане.
3. Проводится построение исходной симплексной таблицы.
4. Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.
5. В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.
6. Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле 0 < Ө ≤
. Данная строка называется разрешающей строкой.7. Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и СБ. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.
После построения каждой таблицы можно проверить правильность вычислений с использованием формул вычисления оценок, приведенных в предыдущем параграфе.
28. выбор базиса и построение начального опорного плана при решении задач симплекс методом.
29. Симплекс-таблицы, их заполнение. Формулы расчета коэффициентов индексной строки.
30. Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.
Теорема 1: Если для некоторого вектора Āj в системе
Х1 + а1m+1Xm+1 + а1m+2Xm+2 + … + а1nXn = a1
Х2 + а2m+1Xm+1 + а2m+2Xm+2 + … + а2nXn = a2