- •Билет № 1
- •1. Теоремы о взаимосвязи опорных решений задачи линейного программирования и угловых точек области допустимых решений.
- •Билет № 3
- •1. Необходимые и достаточные условия разрешимости транспортной задачи.
- •Билет № 4
- •1. Свойство системы ограничений транспортной задачи. Взаимосвязь линейной зависимости векторов-условий и циклов.
- •Билет № 5
- •1. Методы построения опорного решения транспортной задачи. Метод вычёркивания.
- •Билет № 6
- •Билет № 8
- •2. Теорема об единичном базисе.
- •Билет № 9
- •2. Теорема о двух линейно независимых системах векторов.
- •Билет № 10
- •2. Теорема о двух системах векторов, которым соответствуют равносильные системы уравнений.
- •Билет № 12
- •2. Общая теория систем уравнений. Теорема Кронекера-Капелли.
- •Билет № 13
- •2. Фундаментальная система решений однородной системы уравнений, теорема о её существовании.
- •Билет № 14
- •2. Необходимые и достаточные условия существования обратной матрицы.
- •Билет № 15
- •1. Построение начального опорного решения и переход от одного опорного решения к другому в симплексном методе (вывод формул).
- •Билет № 16
- •Теорема об улучшении опорного решения, её следствия.
- •Билет № 17
- •1. Теоремы о взаимосвязи опорных решений и угловых точек области допустимых решений.
- •Билет № 18
- •1. Метод искусственного базиса решения задач линейного программирования, его обоснование. Леммы и теорема об оптимальности опорного решения.
- •Билет № 20
- •Обоснование метод искусственного базиса решения задач линейного программирования. Теорема об отсутствии оптимального решения ввиду неограниченности целевой функции.
- •Билет № 21
- •1. Первая теорема двойственности, её доказательство.
- •Билет № 22
- •Вторая теорема двойственности, её доказательство.
- •Билет № 29
- •1. Теорема о виде области допустимых решений задачи линейного программирования.
- •Билет № 30
- •1. Теорема об улучшении опорного решения, её следствия.
Билет № 22
Вторая теорема двойственности, её доказательство.
Теорема 5.2. Для того, чтобы допустимые решения , являлись оптимальными решениями пары двойственных задач, необходимо и достаточно, чтобы выполнялись следующие равенства
; (5.22)
. (5.23)
Иначе, если при подстановке оптимального решения в систему ограничений i-е ограничение исходной задачи выполняется как строгое неравенство, то i-я координата оптимального решения двойственной задачи равна нулю и, наоборот, если i-я координата оптимального решения двойственной задачи отлична от нуля, то i-е ограничение исходной задачи удовлетворяется оптимальным решением как равенство.
Д о к а з а т е л ь с т в о. Необходимость. Пусть и оптимальные решения пары двойственных задач (5.21).
1. Покажем, что в этом случае выполняются равенства (5.22).
Подставим оптимальные решения X, Y в системы ограничений своих задач, получим
;
.
Затем каждое из тождеств умножим на соответствующую переменную двойственной задачи и после этого просуммируем их, получим
.
Отсюда следует
.
Так как X, Y оптимальные решения, то по первой теореме двойственности Z(X) = F(Y). Поэтому заменим в последнем соотношении знаки "" на "=", получим
. (5.24)
Отсюда можно записать
.
Учитывая, что и , а следовательно и , приходим к выводу, что каждое слагаемое суммы равно нулю, т.е. справедливы равенства (5.22)
.
2. Аналогично докажем справедливость равенств (5.23). Используя выражения (5.24), запишем
.
Учитывая, что и , делаем вывод, что каждое слагаемое суммы равно нулю, т.е.
.
Необходимость доказана.
Достаточность. Пусть равенства (5.22), (5.23) выполняются. Докажем, что в этом случае и являются оптимальными решениями.
Просуммируем каждую группу данных равенств, получим
;
.
Из данных равенств следует, что Z(X) = F(Y). Из первой теоремы двойственности (теорема 5.1) следует, что значения целевых функций пары двойственных задач равны только на оптимальных решениях. Поэтому можно утверждать, что X и Y являются оптимальными решениями. Теорема доказана полностью.
Билет № 24
2. Теорема о двух линейно независимых системах векторов. Теорема о числе векторов, входящих в базис.
Смотреть билет № 9.
Билет № 26
2.. Необходимые и достаточные условия существования обратной матрицы.
Смотреть билет № 14.
Билет № 27
1. Построение начального опорного решения и переход от одного опорного решения к другому в симплексном методе (вывод формул).
Смотреть билет № 15.
Билет № 28
1. Теорема об экстремуме целевой функции задачи линейного программирования.
Теорема 3.3. Целевая функция задачи линейного программирования достигает экстремума в угловой точке области допустимых решений; причем, если целевая функция достигает экстремума в нескольких угловых точках области допустимых решений, то она также достигает экстремума в любой выпуклой линейной комбинации этих точек.
Д о к а з а т е л ь с т в о. Будем считать, что решается задача на нахождение максимума целевой функции
Z(X) = CX max,
AX = ,
.
Докажем, что целевая функция достигает экстремума в угловой точке области допустимых решений G от противного. Если является оптимальным решением, то . Предположим, что оптимальное решение задачи не является угловой точкой (рис.3.5).
|
Тогда по теореме 3.1 , , (j = 1, 2, …, n) – угловые точки области G. Найдем . |
Среди значений выберем наибольшее. Пусть это будет ,
т.е. = . Тогда ,
что противоречит тому, что оптимальное решение в задаче на максимум. Следовательно, является угловой точкой области G.
2. Докажем второе утверждение теоремы. Пусть угловые точки области допустимых решений являются оптимальными решениями, т.е. и . Выпуклая линейной комбинации этих угловых точек равна
.
Найдем значение целевой функции
т.е. этот вектор также является оптимальным решением.