Cтраница 3
Для решения полностью целочисленных задач линейного программирования с произвольным числом переменных используется метод Гомори. Он состоит в последовательном отсечении от допустимого множества U нецелочисленной задачи частей, не содержащих точек с целыми координатами. [31]
Доказать следующий вариант теоремы 4.6. Пусть в задаче (4.26) матрица С положительно определена. Если же задача (4.30) не имеет решения, то допустимое множество задачи (4.26) пусто. [32]
А является линейной комбинацией ее первых I строк. Если задача (5.2) допустима, то это значит, что все строки матрицы А с номерами, большими I, можно отбросить, и допустимое множество задачи (5.2) пе изменится. [33]
Рассмотрим теперь аналитическую задачу, заданную каким-то выбором функций ( компонент векторных полей, функций Гамильтона и т.п.), которые могут зависеть от параметров. Допустимое множество задачи - это минимальное допустимое множество, содержащее данные задачи. Задача называется аналитически разрешимой, если ее решение есть допустимая функция параметров. [34]
Мы хотим найти подобную теорему для неравенств. Для этого целесообразно начать с той же системы Ах Ь, но при дополнительном ограничении х О, т.е. с ответа на вопрос, когда система Ах Ь имеет не просто решение, а неотрицательное решение. Другими словами, нужно найти условия, при которых допустимое множество задачи с ограничениями-равенствами является непустым. [35]
Теорема двойственности представляет собой центральный результат теории линейного программирования. Существуют различные методы ее доказательства - и чисто алгебраические, без использования результатов типа теорем об отделимости, и доказательства, основанные на принципиально новых идеях типа метода штрафных функций. Теория выпуклых многогранных множеств является неотъемлемой частью линейного программирования, поскольку, она полностью описывает структуру допустимых множеств задач линейного программирования. [36]