Критерий оптимальности опорного плана:
-
Если в индексной строке среди оценок оптимальности есть хотя бы одна положительная, то опорный план не является оптимальным.
-
Если в индексной строке все оценки оптимальности являются отрицательными числами, то опорный план является оптимальным и единственным.
-
Если в индексной строке небазисным переменным отвечают нулевые оценки, а среди оценок оптимальности нет положительных, то опорный план является оптимальным, но не единственным.
В нашем случае опорный план, соответствующий первой симплекс-таблице, оптимальным не является.
Для перехода к следующей симплекс-таблице в М-строке выбирают наибольшую положительную оценку, начиная со столбца “р1”. В нашем случае – это число 8 в столбце “р1”.
| | Столбец, содержащий наибольшую положительную оценку, называется разрешающим. Он показывает, какой вектор следует ввести в базис. |
В нашем случае вектор “р1” следует ввести в базис.
Найдем симплексное отношение оптимальности : элементы столбца “р0” разделим на положительные элементы разрешающего столбца.
| | Строка, соответствующая наименьшему отношению оптимальности , называется разрешающей. Она показывает, какой вектор следует вывести из базиса. |
В нашем случае . Таким образом, вектор р7 следует вывести из базиса. Кроме того вектор р7 можно исключить из рассмотрения, поскольку он является искусственным.
| | Генеральный элемент – это элемент, который расположен на пересечении разрешающего столбца и разрешающей строки. |
В нашем случае это число 7.
- Рецензенты:
- Содержание
- 1. Программа курса Введение
- Математические основы программирования
- Общий вид задачи линейного программирования
- Методы решения общей задачи линейного программирования
- Двойственные задачи линейного программирования
- Распределительные методы
- Элементы нелинейного программирования
- Элементы теории игр
- Введение
- Классификация задач математического программирования
- 2. Математическое программирование
- 2.1. Постановка задач линейного программирования
- Алгоритм графического метода решения злп
- 2.3. Симплекс-метод решения задачи линейного программирования
- Алгоритм симплекс-метода решения злп
- Пример 2.3.1. Решить злп (2.2.1), (2.2.5) симплекс-методом.
- Критерий оптимальности опорного плана:
- Переход к следующей симплекс-таблице осуществляют по правилам:
- 2.4. Двойственная задача линейного программирования
- 2.5. Элементы теории матричных игр
- Алгоритм принципа максимина (минимакса)
- Решение. Эта матричная игра имеет размерность (3х4), т.Е. Игрок а имеет три стратегии, а игрок в – четыре. Запишем ее в нормальной форме.
- Последовательность действий при решении игры
- 2.6. Транспортная задача. Метод потенциалов
- Алгоритм метода потенциалов состоит из следующих этапов:
- Критерий оптимальности плана перевозок
- 2.7. Задача о назначениях
- Алгоритм метода Фогеля
- Алгоритм венгерского метода решения задачи о назначениях
- 2.8. Дробно-линейное программирование
- Правила решения задачи дробно-линейного программирования графическим методом
- 2.9. Целочисленное программирование
- 2.10. Параметрическое программирование
- Алгоритм решения задачи параметрического программирования
- 3. Задания для самостоятельной работы