Решение задач дробно-линейного программирования симплексным методом

Задача 3.1. Найти максимальное значение функции z= на множестве решений системы ограничений

Решение. Введем обозначение:

(7)

Тогда z=

Обозначим .

Целевая функция запишется так: z=

Преобразуем систему ограничений. Умножив обе части всех ограничений на

(8)

Включим в систему ограничений (8) ограничение (7) и перейдем к переменным

(9)

Нетрудно убедиться в том, что мы получили задачу линейного программирования: найти максимальное значение z= на множестве решений системы (9).

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

Таблица 8

Базисные переменные						Свободные члены
	-2 -6		-2 -1
			-1
			2/3 4/3 -7/3	1/3 -8/3 -1/3 -2/3		2/3 2/3 1/3 -4/3

Имеем:

Найдем соответствующие значения

Итак, достигается при решении (2; 0; 0; 2).

Задача 3.2. Найти максимальное значение целевой функции

на множестве решений системы ограничений:

Решение. Обозначим

2

Преобразуем целевую функцию:

z = (10)

Система ограничений примет вид:

(11)

Теперь найдем наибольшее значение целевой функции (10) на множестве решений системы (11):

Таблица 9.

					Свободные члены
	-8 -4		-1	-1
	-8 -12		-1	-5 -2
	-20 -12			-9 -2
				25/41	20/41 12/41 1/41

при

Заметим, что если бы в оптимальном плане был бы равен 0, то 2 при оптимальном базисном решении стремилось бы к бесконечности. Отсюда следует неограниченность множества решений системы ограничений. В этом случае глобальный максимум z (конечный или бесконечный) достигается в бесконечно удаленных точках.

4. Метод множителей Лагранжа

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

при ограничениях:

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

где - множители Лагранжа.

Необходимое условие наличия условного экстремума выражаются системой (n+m) уравнений:

(12)

из которых могут быть найдены неизвестные где - точка, в которой возможен условный экстремум.

Достаточные условия наличия условного экстремума связана с изучением знака 2-го дифференциала функции Лагранжа:

для каждого набора значений , полученный из системы (12) при условии, что удовлетворяет уравнениям:

(12)

Функция имеет условный максимум в точке М₀, если для всевозможных значений , удовлетворяющих условиям (12), выполняется неравенство:

и условный минимум, если при этих условиях:

В случае двух переменных при одном ограничении , то функция Лагранжа имеет вид:

Система для нахождения стационарных (критических) точек состоит из трех уравнений:

Если - любое из решений этой системы, вместо изучения знака второго дифференциала, можно исследовать знак определителя

При этом:

1) если , то функция имеет в точке условный максимум,

2) если , то функция имеет в точке условный минимум.

Объясним идею метода на примере задачи нелинейного программирования, зависящей от двух переменных.

f(x₁, х₂)→max

g(x_l,x₂) = b

На плоскости x₁0x₂ уравнение g(x_x,x₂)=b определяет график некоторой функции, представленный на рис. 26. На нем показаны несколько линий уровня некоторой функции f(х_1гх₂) и выбранное в качестве примера направление ее возрастания.

рис. 26

В точке А, в которой функция f достигает максимального значения, совпадают касательные линии к графикам функций

f(х₁,х₂) = С иg(x_l,x₂)=b.

Следовательно, в точке А векторы-нормали к функциям g(x_l,x₂)=b и f(x₁,x₂)=C пропорциональны. Обозначим эти векторы соответственно через k и l. Получаем l = λk,где λ- некоторый коэффициент пропорциональности. Координатами векторов l и k являются значения частных производных функций f и g соответственно в точке А.

l=(дf/дx₁; дf/дx₂);

k=(дg/дx₁; дg/дx₂).

Из условия пропорциональности в точке А имеем

дf/дx₁=λ*дg/дx₂;

дf/дx₂=λ*дg/дx₂.

Для определения значений х₁,х₂,в которых функция f достигает максимума, к этим уравнениям надо добавить условие принадлежности точки А графику функции g(x₁, х₂) =b.

Окончательно получаем систему уравнений, определяющую опти­мальное решение поставленной задачи

дf/дx₁=λ*дg/дx₁

дf/дx₂=λ*дg/дx₂

g(x₁, х₂)=b

Введем новую функцию

F(x₁,х₂, λ) = f(x₁,х₂) + λ (b-g(x₁,х₂)).

Тогда последняя система перепишется в виде

дF(x₁,x₂, λ)/ дx₁=дf(x₁,x₂)/ дx₁- λ*д(x₁,x₂)/ дx₁=0

дF(x₁,x₂, λ)/ дx₂=дf(x₁,x₂)/ дx₂- λ*д(x₁,x₂)/ дx₂=0

дF/ дλ=b-g(x₁,x₂)=0

Функцию F и называют функцией Лагранжа.

Задача 4.1. Найти условный экстремум функции при условии методом Лагранжа.

Решение.

Для нашей задачи составляем функцию Лагранжа:

Находим частные производные:

Система уравнений принимает вид:

Решаем систему:

Далее находим вторые частные производные функции Лагранжа и составляем второй дифференциал

Следовательно

При , следовательно, в точке функция имеет условный минимум, равный:

При , следовательно, в точке функция имеет максимум, равный:

Теперь определить тип экстремумов в стационарных точках другим способом (с помощью определителя ):

При

следовательно, в точке для функция имеет условный минимум, равный

При

следовательно, в точке для функция имеет условный максимум, равный

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

-целочисленные координаты.

Решение. Составляем функция Лагранжа:

Находим частные производные функции Лагранжа:

Для нахождения стационарных точек, получаем систему уравнений:

Можно показать, что из последних уравнений системы следует уравнение четвертой степени относительно :

Корни этого уравнения:

а) при значении получим Стационарная точка

б) при значении , получим Стационарная точка

в) значения является посторонними корнями, им соответствуют стационарные точки с не целочисленными координатами (не соответствуют условию задачи).

Далее, находим вторые частные производные функции L и составляем второй дифференциал :

Следовательно

Из условий связи следуют равенства:

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

Откуда получаем:

Значит, в точке функция имеет условный максимум, равный

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

поэтому

Значит, в точке функция имеет условный минимум, равный

Дата добавления: 2015-11-14