Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

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

II) ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ | Симплексный метод | Графический метод | Транспортная задача | Общая задача нелинейного программирования | Задачи с линейной целевой функцией и нелинейной системой ограничений | Задачи с линейной системой ограничений, но линейной целевой функцией | Пример решения транспортной задачи в среде MS Excel | Изготовление продукции из нескольких компонент | Простая распределительная сеть (транспортная задача) |


Читайте также:
  1. GR: основная цель, задачи и средства GR-менеджера
  2. I. Цели и задачи освоения учебной дисциплины
  3. I. Этапы решения задач на компьютере.
  4. II. Основные задачи и их реализация
  5. II. Цели и задачи.
  6. IV.Некоторые задачи
  7. PMCS стала первым Облачным партнером Microsoft по управлению проектами предоставив решение с интеграцией с Office 365

Задача 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)

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

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

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

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

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

При этом:

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

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

 

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

f(x1, х2)→max

g(xl,x2) = b

На плоскости x10x2 уравнение g(xx,x2)=b определяет график некоторой функции, представленный на рис. 26. На нем показаны несколько линий уровня некоторой функции f(хх2) и выбранное в качестве примера направление ее возрастания.

 

рис. 26

 

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

f(х12) = С иg(xl,x2)=b.

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

l=(дf/дx1; дf/дx2);

k=(дg/дx1; дg/дx2).

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

дf/дx1=λ*дg/дx2;

дf/дx2=λ*дg/дx2.

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

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

дf/дx1=λ*дg/дx1

дf/дx2=λ*дg/дx2

g(x1, х2)=b

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

F(x12, λ) = f(x12) + λ (b-g(x12)).

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

дF(x1,x2, λ)/ дx1=дf(x1,x2)/ дx1- λ*д(x1,x2)/ дx1=0

дF(x1,x2, λ)/ дx2=дf(x1,x2)/ дx2- λ*д(x1,x2)/ дx2=0

дF/ дλ=b-g(x1,x2)=0

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

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

Решение.

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

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

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

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

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

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

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

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

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

При

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

При

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

поэтому

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

 


Дата добавления: 2015-11-14; просмотров: 77 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Задачи с нелинейной целевой функцией и нелинейной системой ограничений.| Градиентный метод

mybiblioteka.su - 2015-2024 год. (0.022 сек.)