Экстремумы линейных функций.

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

Доказательство:

Т.к. ОДР – ограниченная, то по второй теореме Вейерштрасса непрерывная функция на замкнутом и ограниченном интервале принимает максимальное и минимальное значение.

Пусть х – допустимое решение.

Доказать, что Х – опорное решение.

Пусть х₁,х₂,…,x_s – угловые точки (опорные решения) ОДР, тогда

(*)

Поскольку Х – допустимое решение, то для любой точки х

Т.к. x_k – допустимое решение, то (**)

Из (*) и (**):

Теорема 2. Если ОДР ЗЛП – ограниченная, а функция не ограничена сверху (снизу), то задача отыскания максимума f (минимума f) не имеет решений.

Min f (max f) существует и достигается по крайней мере в одном из опорных решений.

Без доказательства.

Теорема 3. Если max (min) достигается в нескольких опорных решениях х₁,х₂,…,х_l, то любая выпуклая линейная комбинация оптимальн. опорн. реш. есть также оптимальное решение.

Доказательство:

Рассмотрим вектор Y, который является линейной комбинацией оптим. реш.

Теорема доказана.

Теоремы 1,2,3 можно обобщить в основную теорему линейного программирования.

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

Основная теорема указывает схему, которая может быть использована при решении ЗЛП.

Схема решения ЗЛП.

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

2. Подсчитать значения линейной функции на каждом опорном решении.

3. Сравнивая найденные значения, установить опорн. реш.

Недостаток схемы: нужно исследовать каждое опорное решение.

Эта схема предполагает беспорядочный перебор опорных решений.

Симплексный метод предполагает упорядоченный перебор опорных решений так, что на каждом следующем опорном решении значение функции ближе к оптимальному решению, чем предыдущее (идея последовательного улучшения решения).

Три элемента симплексного метода:

1. Нахождение исходного опорного решения.

2. Правило перехода к следующему, лучшему опорному решению.

3. Критерий, который позволяет установить оптимальность опорного решения или необходимость его дальнейшего улучшения, или отсутствия решения.

Симплексный метод.

Пример.

Найти max функции при усл.

(1)

(2)

(3)

(4)

Умножим соответствующие уравнения системы (1) на соответствующие числа (коэф.) и сложим с равенством (4).

- числа, оценки свободных переменных

(5) х₄=х₅=0 f(Х_оп)=

(5) - приведённое выражение для линейной функции.

Т.к. для опорн. реш. значения всех свободных переменных равны нулю, то, положив в равенстве (5) значения свободных переменных равными нулю, мы сразу находим значение линейной функции на данном опорном решении.

Определение. Говорят, что ЗЛП приведена к симплексной форме, если сис. ограничительных уравнений разрешена относительно базисных неизвестных, свободные члены уравнений «≥0», а линейная функция выражена через свободные неизвестные. ← Отыскав исходн. опорн. реш., и получив приведённое выражение лин. функции, мы привели ЗЛП к симплексной форме.

Перепишем сист. лин. уравнений (2) в виде таблицы, добавив к ней в качестве последней строки строчку с коэффициентами значения (5), считая что уравнение разрешено относительно базисной переменной f.

ci	Баз. неиз.				-2
bi	x1	x2	x3	x4	x5
	x1 x2 x3					-1	-1
	f					-4	-2

Теорема.

Пусть ЗЛП записана в симплексной форме, тогда:

1⁰. и в каждом столбце с такой оценкой имеем хотя бы один положительный элемент, тогда решение можно улучшить, т.е. перейти к опорному решению Х₁, в котором значение линейной функции будет больше

2⁰. Существует отрицательная оценка свободных переменных такая, что столбец которой не содержит положительных элементов, то ЗЛП не имеет решения ввиду неограниченности целевой функции в ОДР.

3⁰. Все оценки свободных переменных «≥0». В этом случае соответствующее опорное решение будет оптимальным.

Все

Доказательство:

П.1. Найдём в симплексной таблице элемент из следующих условий:

1) s-й столбец:

2) k-я строка:

С разрешающим элементом a_ks выполним преобразование однократного замещения.

x_s→базисн., x_k-своб.неизв.

П.2. Пусть ЗЛП приведена к симплексной форме, и система ограничительных уравнений разрешена относительно базисн. неизв., и все свободные члены неотрицательны.

Построим какое-либо неотрицательное решение Х системы .

Возьмём для своб. перем. следующие неотрицательные значения.

Из системы найдём значения базисн. неизв.

Получим неотриц. реш. системы . Теперь, используя приведённое выражение для линейной функции, мы получим значение линейной функции на построенном решении.

Из этого равенства видно, что если переменной x_s придать сколь угодно большие значения, то значение лин. функции можно сделать сколь угодно большим положительным числом, т.о. линейная функция не ограничена сверху в ОДР.

П.3. Все оценки

Пусть Х₀ – соответствующее опорное решение. Требуется доказать, что для любого другого опорного решения Х₁

Признак существования множества оптимальный решений.

Если все оценки свободн. перем. , то введение любой переменной в базис приведёт к уменьшению функции f, т.к. и, следовательно, существует только одно оптимальное решение.

Если же какая-то оценка свободной переменной окажется равной нулю , то введение переменной х_s в базис не изменит значение линейной функции f, т.к. будет «=0», и поэтому можно перейти к новому опорному решению, для которого , т.о. признаком существования множества решений является наличие хотя бы одной нулевой оценки свободных переменных при неотрицательности всех остальных оценок.

Если нулевых оценок окажется несколько, то введением в базис кажд. из соотв. своб. перем. можно найти несколько оптимальных решений.

Транспортная задача

Формулировка задачи.

В m сосредоточен однородный груз в количествах Этот груз нужно перевезти n потребителям в количествах Известны числа - стоимость перевозки единицы груза от i-го поставщика j-му потребителю (тариф перевозки).

Будем считать, что потребности в грузе равны его запасам: (задача с правильным балансом).

Обозначим - объём груза, перевозимого от i-го поставщика j-му потребителю.

Условия транспортной задачи будем записывать в виде транспортной таблицы.

bj ai	b1	b2	…	bn
a1	c11	c12	…	c1n
a2	c21	c22	…	c2n
…
am	cm1	cm2	…	cmn

Введём вектор

Х – план перевозок.

План перевозок должен удовлетворять следующим условиям

1.

(1)

Условие (1) – требование того, чтобы грузы от каждого поставщика были вывезены полностью.

2.

(2)

Условие (2) – требование того, чтобы запросы каждого потребителя были полностью удовлетворены.

(3)

Математическая формулировка транспортной задачи:

Найти такой план Х, удовлетворяющий системам ограничений (1) и (2), условиям неотрицательности (3) и обеспечивающий минимум целевой функции f.

Симплекс-процесс:

1. Определение исходного опорного решения.

2. Оценка этого решения.

3. Переход к лучшему решению путём однократного замещения одной базисной переменной на свободную.

Однако специфичность системы ограничений (1) , (2) позволяет систематизировать для её решения более простой вычислительный алгоритм, чем симплексный метод.

Особенности системы ограничений (1), (2):

1. Коэффициенты при неизвестных (1), (2) равны единице.

2. Каждая неизвестная встречается в двух и только двух уравнениях, причем одно из уравнений входит систему (1), а другое – в (2).