§2 Некоторые теоремы о решении задач лп

Рассмотрим общую задачу ЛП (1-3). Допустим, что - решение.

Определение. Частное решение системы (2), соответствующие нулевым, не базисным переменным, называется базисным решением.

Базисное неотрицательное решение ((2)+(3)) называется опорным (начальным).

Без доказательств перечислим некоторые теоремы.

Теорема. Область допустимых решений системы (2) есть выпуклое множество.

Теорема. (о соответствии опорных решений и угловых точек)

Допустимое решение x является угловой точкой ОДР тогда и только тогда, когда оно опорное.

Система (2) может иметь не более чем n-r опорных решений, где n - число неизвестных , r – ранг системы (2)

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

Если система (2),(3) имеет ограниченную область ДР, то любое ее допустимое решение представимо в виде выпуклой линейной комбинации всех ее опорных решений. Т.е., если - опорные решения, то любое допустиое решение

Теорема. (о представлении неограниченной ОДР)

Если система (2),(3) имеет неограниченную ОДР, то любое допустимое решение представимо в виде:

где R_j – направляющие векторы неограниченных ребер области решений.

Теорема. (о существовании опорного решения)

Если система (2),(3) имеет хотя бы одно допустимое решение, то среди этих решений имеется хотя бы одно опорное решение.

Теорема. (о существовании опорного решения в ограниченной области)

Если ОДР стандартной задачи ЛП ограничена, то оптимальное решение существует и совпадает с хотя бы одним опорным.

Теорема. (об оптимальном решении в неограниченной области)

Если ОДР стандартной задачи ЛП неограниченна, то оптимальное решение существует и совпадает с хотя бы одним опорным, если целевая функция (x) ограниченна сверху в задаче максимизации, и снизу – в задаче минимизации.

Теорема. (фундаментальная в ЛП)

Если существует оптимальное решение задач ЛП, то решение совпадает хотя бы с одним из опорных решений.

Теорема. (об альтернативном оптимальном решении)

Если целевая функция (X) достигает минимума (максимума) в нескольких опорных решениях , то любое оптимальное решение является выпуклой линейной комбинацией альтернативных опорных решений, т.Е.

Фундаментальная теорема предлагает следующий алгоритм решения задач ЛП:

1. Найти все опорные решения

2. Вычислить значение целевой функции в опорных решениях

3. Выбрать наименьшее или наибольшее из них

§3. Графическое решение задач лп

Дадим графическое применение алгоритма на примере.

Пример. Небольшая фирма выпускает два вида красок для внутренних и наружных работ (I и E). Продукция обоих видов поступает в оптовую продажу. Для производства красок используется два продукта А и В.

Максимально возможные суточные запасы составляют 6 и 8 т. продуктов А и В соответственно. Расходы А и В на производство 1 тонны соответствующих красок приведены в таблице:

Исходный продукт	Расходы продукта в т. на одну тонну красок		Максимальный запас. в т.
	I	E
A	2	1	6
B	1	2	8

Изучение рынка сбыта показало, что спрос на краску I никогда не превышает спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т. в сутки. Оптовые цены 1 тонны краски I - $ 2000, E - $ 3000

Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продукции был бы максимальным?

Поставим математическую задачу.

Определим переменные :

x₁ – суточный объем производства краски I, в т.

x₂ - суточный объем производства краски E, в т.

Целевая функция

(x) = 2x₁ + 3x₂ (в тыс $) max

Ограничения:

Получили задачу ЛП о максимизации целевой функции (x) при указанных ограничениях.

Построим ОДР (область ОАВСDE на рис.).

Построим линию уровня целевой функции

Пусть с=6

Двигаем (х) в сторону ОДР. Возможны 3 ситуации:

1. Параллельный сдвиг приведет в положении, когда у прямой окажется только одна общая точка с ОДР. Отсюда, единственное оптимальное решение.

2. Прямая совпадает с одной из сторон многогранника. В этом случае экстремум достигается во всех точках границы области.

3. Внаправлении возрастания целевой функции ОДР неограниченна. В этом случае целевая функция может принимать любое значение, отсюда, задача на "max" не имеет решений.

В нашем случае – одна точка D. Следовательно, задача имеет единственное решение. Координаты D найдем как точку пересечения 1 и 2 прямых.

Оптимальный план: производить 4/3 т. краски I, 10/3 т. краски E. И при этом максимальный доход будет:

тыс. долларов