- •Билет № 1
- •2. Теорема о решении однородной системы линейных уравнений.
- •Билет № 2
- •2. Необходимые и достаточные условия разрешимости транспортной задачи линейного программирования.
- •Билет № 3
- •2. Базис системы векторов. Теорема о единственности разложения вектора по базису.
- •Билет № 4
- •2. Теорема об улучшении опорного решения задачи линейного программирования, её следствия (признак оптимальности опорного решения).
- •Билет № 5
- •2. Теорема об оптимальности опорного решения задачи линейного программирования с искусственными переменными.
- •Билет № 6
- •2. Теоремы об отсутствии оптимального решения задачи линейного программирования с искусственными переменными.
- •Билет № 7
- •2. Теорема об экстремуме целевой функции задачи линейного программирования.
- •Билет № 8
- •2. Первая теорема двойственности.
- •Билет № 9
- •2. Вторая теорема двойственности.
- •Билет № 10
- •2. Построение начального опорного решения задачи линейного программирования и переход от одного опорного решения к другому.
- •Ответы к задачам
Билет № 5
2. Теорема об оптимальности опорного решения задачи линейного программирования с искусственными переменными.
Теорема 4.2 (признак оптимальности решения). Если расширенная задача линейного программирования имеет оптимальное решение ,
у которого все искусственные переменные равны нулю, то исходная задача имеет оптимальное решение , которое получается из отбрасыванием этих нулевых искусственных переменных.
Д о к а з а т е л ь с т в о (от противного). Пусть расширенная задача на максимум имеет оптимальное решение , т.е. . По лемме 4.1 допустимому решению соответствует допустимое решение исходной задачи такое, что .
Покажем, что оптимальное решение исходной задачи, т.е.
.
Предположим, что оптимальным решением исходной задачи является , т.е. , в частности . По лемме 4.1 существует допустимое решение расширенной задачи такое, что . Тогда , что противоречит оптимальности .
Билет № 6
2. Теоремы об отсутствии оптимального решения задачи линейного программирования с искусственными переменными.
Теорема 4.3 (признак отсутствия решения ввиду несовместности системы ограничений). Если расширенная задача имеет оптимальное решение, у которого хотя бы одна искусственная переменная отлична от нуля, то исходная задача не имеет решения ввиду несовместности системы ограничений.
Д о к а з а т е л ь с т в о (от противного). Пусть расширенная задача на максимум имеет оптимальное решение , т. е. ; причем хотя бы одна из искусственных переменных больше нуля. Покажем, что система ограничений исходной задачи в этом случае несовместна.
Предположим, что исходная задача имеет некоторое допустимое решение . По лемме 4.1 ему соответствует допустимое решение расширенной задачи и . На основании леммы 4.2 имеем , что противоречит оптимальности . Теорема доказана.
Теорема 4.4 (признак отсутствия решения ввиду неограниченности целевой функции). Если расширенная задача не имеет решения ввиду неограниченности целевой функции, то и исходная задача также не имеет решения по той же причине.
Д о к а з а т е л ь с т в о (от противного). Пусть расширенная задача на максимум не имеет решения ввиду неограниченности функции, то есть +. Предположим, что исходная задача имеет оптимальное решение . По лемме 4.1 ему соответствует допустимое решение расширенной задачи и . Так как +, то найдется такое допустимое решение , что .
Рассмотрим два случая:
1) 2) существует .
1) Если , то допустимому решению по лемме 4.1 соответствует допустимое решение исходной задачи и , т.е.
,
что противоречит предположению об оптимальности решения .
2) Если существует , тогда по лемме 4.2 , что противоречит неограниченности целевой функции ( +) расширенной задачи .