- •30. Идея симплекс метода, ее геометрическая иллюстрация.
- •31. Алгоритм симплекс метода
- •32. Выбор базиса и построение начального опорного плана при решении задачи симплекс методом.
- •33. Симплекс таблицы, их заполнение. Формы расчета коэффициентов индексной строки
- •34.Теорема оптимальности плана задач линейного программирования, следствие из теоремы. Оценки оптимальности при решении задачи симплекс-методом.
- •36.Разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для пересчета симплекс-табл.
- •37.Правило «четырехугольника» для пересчета симплекс табл.
- •38.Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задач линейного программирования симплекс-методом.
- •40. Построение м-задачи в методе искусственного базиса.
- •41.Построение индексной строки в методе искусственного базиса.
- •42. Критерий оптимальности в методе искусственного базиса
- •39. В каких случаях примется метод искусственного базиса?
- •54. Вырожденное распределение в транспортных задачах; избавление от вырожденности. Вычеркиваемая комбинация.
- •55.Теорема оптимальности транспортной задачи.
- •56.Потенциалы и способ их расчета.
- •57.Расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.
- •58. Перераспределение поставок в транспортной задаче
- •59. Цепочки перераспределения, их виды.
- •60. Выбор объема перераспределения
- •61. Случай построения вырожденного построения при перераспределении поставок в транспортной задаче и избавление от вырожденности.
- •62.Признак единственности оптимального распределения транспортной задачи и признак множества оптимальных распределений.
- •63. Алгоритм метода потенциалов.
- •64. Учет затрат на производство и транспортировку продукции. Транспортные задачи с запретами на поставки.
- •65. Учет ограничений по пропускной способности маршрутов, учет обязательности некоторых поставок в транспортной задаче.
- •67. Идея метода динамического программирования
- •68. Требования, предъявленные к задачам динамического программирования:
- •69. Экономическая постановка и построение математической модели решаемой методом дп (на примере распределения капиталовложений) Рекуррентное соотношение Беллмана.
- •70.Решение задачи о распределении капитальных вложений; алгоритм ее решения.
- •73. Параметрическое линейное программирование
36.Разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для пересчета симплекс-табл.
Если в индексной строке стоят отрицат. или – 0-ые оценки, то проверяемы опорный план – оpt, если положительные, то необходимо пересчитать С-Т. Для этого необх. выделить векторы, которые вводятся и выводятся из базиса. На их пересечении будет стоять разрешающий эл-т таблицы. В базис вводится вектор, которому соответствует положительная оценка оpt, если их несколько, то вводится вектор с наибольшей положительной оценкой Opt. Из базиса выводится вектор, которому соответствует симплексное отношение, опред. по ф.: Q=min (bi/Xij). Пересчет С-Т проводят по правилу полных Жордановых исключений: 1 метод: с помощью элементарных преобразований Гауса делают так, чтобы направляющий столбец стал единичным, т.е. таким как столбец, соответствующий вектору выводимому из базиса. Используют 2 элемент.преобразования – 1) направляющая строка умножается на любое число, отличное от «0», 2) направляющ. строка умножается на любое число и векторно складывается с любой др. строкой табл.2 метод (правило четырехугольника): 1) направляющая строка делится на разрешающий эл-т табл., 2) направляющий столбец записывается как единичный, 3) Те строкии столбцы, кот. имеют в направляющей строке/столбце «0» переносятся без изменений, остальные числа табл. пересчитываются так: эл-т новойсимпл. табл.= эл-ту, стоящему на этом же месте в старой табл. минус произведение эл-тов, стоящих на диагонале противоположной к разрешающему эл-ту, деленное на разрешающий эл-т табл.
37.Правило «четырехугольника» для пересчета симплекс табл.
(правило четырехугольника): 1) направляющая строка делится на разрешающий эл-т табл., 2) направляющий столбец записывается как единичный, 3) Те строкии столбцы, кот. имеют в направляющей строке/столбце «0» переносятся без изменений, остальные числа табл. пересчитываются так: эл-т новойсимпл. табл.= эл-ту, стоящему на этом же месте в старой табл. минус произведение эл-тов, стоящих на диагонале противоположной к разрешающему эл-ту, деленное на разрешающий эл-т табл.
38.Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задач линейного программирования симплекс-методом.
При решении задач симплекс-методом возможны следующие варианты:
1. Единственность. Если оценки всех свободных векторов строго отрицательные, то полученный опорный план – оптимальный и единственный.
2. Альтернативный оптимум – множество оптимальных решений.
Если среди неположительных оценок свободных векторов есть хоть одна нулевая, то полученный опорный план оптимальный, но не единственный. Можно перейти к другим опорным планам (вводят в базис векторы, которым соответствуют нулевые оценки)
3. ЗЛП не имеет оптимального решения, т.к. функция не ограничена снизу. Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательные и нулевые, то данный вектор можно ввести в базис. Но никакой из базисных векторов нельзя вывести из базиса. Дальнейшее уменьшение ЦФ возможно при переходе к неопорному плану.
4. ЗЛП не имеет решения, т.к. система ограничений противоречива. Но при решении симплекс-методом должен быть исходный опорный план, значит система уравнений не противоречива. Этот случай не может встретиться при решении обычным симплекс методом.
5. ОДЗ из 1 точки – решение задачи тривиально и можно его получить без использования симплекс-метода.