Билет № 17
1. Теоремы о взаимосвязи опорных решений и угловых точек области допустимых решений.
Смотреть билет № 1.
Билет № 18
1. Метод искусственного базиса решения задач линейного программирования, его обоснование. Леммы и теорема об оптимальности опорного решения.
Лемма 4.1. Любому допустимому решению
исходной задачи линейного программирования
соответствует допустимое решение
расширенной задачи
и, наоборот, любому допустимому
решению
расширенной задачи
соответствует допустимое решение
исходной задачи
.
При этом значения целевых функций
задач на соответствующих решениях
совпадают, т. е.
.
Д о к а з а т е л ь с т в о. Пусть допустимое решение. Тогда оно удовлетворяет системе ограничений и условиям неотрицательности задачи (4.22)
(4.25)
Дополним данное решение равными нулю переменными
,
имеем
.
Подставим
в систему ограничений расширенной
задачи (4.24), получим
Данное равенство выполняется, так как оно не отличается от тождества (4.25). Кроме того отрицательных координат не имеет и, следовательно, является допустимым решением.
Покажем, что значения целевых функций задач на соответствующих допустимых решениях совпадают. Подставим и в целевые функции, получим
Отсюда .
Лемма 4.2. Значение целевой функции
расширенной задачи на максимум
(минимум) на любом допустимом решении
,
у которого все искусственные переменные
равны нулю, больше
(меньше) значения целевой функции на
любом допустимом решении , у которого
хотя бы одна искусственная переменная
отлична от нуля.
Д о к а з а т е л ь с т в о. Подставим
и
в целевую функцию расширенной задачи
.
Так как допустимое решение
удовлетворяет условию неотрицательности
и по условию леммы хотя бы одна из
координат
,
то
и
.
Доказательство для задачи на минимум аналогично.
Теорема 4.2 (признак оптимальности решения). Если расширенная задача линейного программирования имеет оптимальное решение
,
у которого все искусственные переменные
равны нулю, то исходная задача имеет
оптимальное решение
,
которое получается из
отбрасыванием этих нулевых искусственных
переменных.
Д о к а з а т е л ь с т в о (от противного).
Пусть расширенная задача на максимум
имеет оптимальное решение
,
т.е.
.
По лемме 4.1 допустимому решению
соответствует допустимое решение
исходной задачи
такое, что
.
Покажем, что
оптимальное решение
исходной задачи, т.е.
.
Предположим, что оптимальным решением
исходной задачи является
,
т.е.
,
в частности
.
По лемме 4.1 существует допустимое
решение расширенной задачи
такое, что
.
Тогда
,
что противоречит оптимальности
.
Билет № 20
Обоснование метод искусственного базиса решения задач линейного программирования. Теорема об отсутствии оптимального решения ввиду неограниченности целевой функции.
Теорема 4.3 (признак отсутствия решения ввиду несовместности системы ограничений). Если расширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная отлична от нуля, то исходная задача не имеет решения ввиду несовместности системы ограничений.
Д о к а з а т е л ь с т в о (от
противного). Пусть расширенная задача
на максимум имеет оптимальное решение
,
т. е.
;
причем хотя бы одна из искусственных
переменных больше нуля. Покажем, что
система ограничений исходной задачи
в этом случае несовместна.
Предположим, что исходная задача
имеет некоторое допустимое решение
.
По лемме 4.1 ему соответствует
допустимое решение расширенной задачи
и
.
На основании леммы 4.2 имеем
,
что противоречит оптимальности
.
Теорема доказана.
Теорема 4.4 (признак отсутствия решения ввиду неограниченности целевой функции). Если расширенная задача не имеет решения ввиду неограниченности целевой функции, то и исходная задача также не имеет решения по той же причине.
Д о к а з а т е л ь с т в о (от противного).
Пусть расширенная задача на максимум
не имеет решения ввиду неограниченности
функции, то есть
+.
Предположим, что исходная задача
имеет оптимальное решение
.
По лемме 4.1 ему соответствует допустимое
решение расширенной задачи
и
.
Так как
+,
то найдется такое допустимое решение
,
что
.
Рассмотрим два случая:
1)
2) существует
.
1) Если
,
то допустимому решению
по лемме 4.1 соответствует допустимое
решение исходной задачи
и
,
т.е.
,
что противоречит предположению об
оптимальности решения
.
2) Если существует
,
тогда по лемме 4.2
,
что противоречит неограниченности
целевой функции (
+)
расширенной задачи
.