Билет № 29

1. Теорема о виде области допустимых решений задачи линейного программирования.

Теорема 3.2. Область допустимых решений задачи линейного программирования является выпуклым множеством.

Д о к а з а т е л ь с т в о. Пусть имеется задача линейного программирования

Z(X) = CX max (min),

AX = ,

.

Покажем, что если некоторые допустимые решения задачи, то , где , , , также является допустимым решением. Подставим в систему ограничений задачи, умножим полученные в результате этого равенства на и сложим их:

получим .

Учитывая, что , а , имеем .

Кроме того, так как , то , т.е. является допустимым решением.

Билет № 30

1. Теорема об улучшении опорного решения, её следствия.

Смотреть билет № 16.