Решить графоаналитическим методом.
Задача 1
max (X) = - 2x1 + x2 + 5x3
при 4x1 + 2x2 + 5x3 12
6x1 - 3x2 + 4x3 = 18
3x1 + 3x2 - 2x3 16
Х ≥ 0
Здесь число n = 3 и число m = 3.
Выразим из ограничений и х3:
≥ 0
Подставим его в целевую функцию
max (X) =
Получим новые ограничения:
х ≥ 0
Получили задачу линейного программирования в основном виде для n = 2
Вычисляем градиент :
= =
Рисунок 1
Прямые a, c, d и e пересекаются и образуют четырехугольник ACDE. Определим max φ (Х), который удовлетворяет условию Х>=0:
Это точка D (0,7; 4,7; 0).
Функция φ (Х*) в точке D:
φ (Х*) = 38,3
Найти экстремумы методом множителей Лагранжа
Задача 2
extr φ (X) = 4x1 - x22 - 12
при x12 + x22 = 25
Составим функцию Лагранжа:
L (X,λ) = 4x1 - x22 - 12 + λ (x12 + x22 - 25)
h (X) = x12 + x22 - 25 = 0 - функция ограничения.
Составим систему уравнений из частных производных и приравняем их нулю.
Решим данную систему уравнений:
2x2 (λ - 1) = 0
Предположим, что x2 ≠ 0, тогда λ = 1 подставим в первое уравнение системы.
4 - 2x1 = 0
2x1 = - 4
x1 = 2
Подставим x1 в третье уравнение системы.
4 +x22 - 25 = 0
x22 - 21 = 0
x22 = 21
x2 = ±4,5826
Параболоид вращения функции h (x).
В двухмерной проекции график выглядит так:
Рисунок 2.
На рис.2 видно, что в точках А1 и А2 функция φ (X) = h (X). В этих точках функция φ (X) равна минимальному значению.
(X*,λ*) N | X1* | X2* | λ* | φ (X*) | Примечание |
1 | 2 | 4,5826 | 1 | -24,25 | Min |
2 | 2 | -4,5826 | 1 | -24,25 | Min |
Решить обобщенным методом множителей Лагранжа или на основе условий Куна-Таккера.
Задача 3
extr φ (X) = 9 (x1 - 5) 2 + 4 (x2 - 6) 2 =
при 3x1 + 2x2 >= 12
x1 - x2 <= 6
Решим задачу на основе условий Куна-Таккера.
Составим функцию Лагранжа.
L (X,λ) = + λ1 (3x1 + 2x2 - 12) + λ2 (x1 - x2 - 6) =
Составим систему уравнений из частных производных и приравняем их нулю.
Решим систему уравнений.
1) Предположим, что λ2 ≠ 0, тогда из уравнения (d) получим
x2 = х1 - 6
Пусть λ1 = 0 и x1 ≠ 0, тогда из уравнения (а) получим
18x1 - 90 - λ2 = 0, λ2 = 18х1 - 90
Пусть x2 ≠ 0, тогда из уравнения (b) получим
8x2 - 48 - λ2 = 0
Подставив в уравнение выражения для x2 и λ2, получим
x1 = 4
x2 = - 2
x1* = 4; x2* = - 2; φ (Х) * = 265
Трехмерный график целевой функции для данной задачи
Двухмерная проекция
Рисунок 3
На рис.3 видно, что в точке А функция b (X) = a (X), которые находятся в параболоиде вращения целевой функции.
В этой точке функция φ (X) равна максимальному значению.
2) Предположим, что λ2 = 0 и x2 ≠ 0, тогда из уравнения (b) получим
8x2 - 48 + 2λ1 = 0
x2 =
x2 = 6 -
Предположим, что x1 ≠ 0, тогда из уравнения (а) выразим x1.
18х1 - 90 + 3λ1 = 0
18 = 90 - 3λ1
х1 =
х1 = 5 -
Подставим выражения для x1 и x2 в уравнение (с) системы.
а) = 0, x1 = 5; x2 = 6
б) = 15
x1 = 2,5; x2 = 2,25
Подставив корни x1 = 5; x2 = 6 в целевую функцию получим φ (Х) = 0, а корни x1 = 2,5; x2 = 2,25 - получим φ (Х) = 112,49
Таким образом:
x1* = 5; x2* = 6; φ* (Х) = 0
На рис.4 видно, что в точке В функция φ (X) = a (X). В этой точке функция φ (X) равна минимальному значению.
Рисунок 4
X* N | X1* | X2* | φ (X*) | Примечание |
1 | 5 | 6 | 0 | Min |
2 | 4 | -2 | 265 | Max |
Получить выражение вектор-функции и матрицы Якоби системы и составить алгоритм численного решения задачи на основе условий Куна-Таккера.
Задача 4
max φ (X) = - x12 - x22 +2х2
при x1 + x2 >= 18
x1 + 2 x2 >= 14
Х>=0
Найдем выражение вектор-функции системы.
Составим функцию Лагранжа.
L (X,λ) = - x12 - x22 + 2х2 + λ1 (x1 + x2 - 18) + λ2 (x1 + 2x2 - 14)
Вектор-функция системы:
Составим матрицу Якоби.
Составим алгоритм численного решения задачи:
Рисунок 5.
Другие работы по теме:
Распределение температуры по сечению балки
Методика численного решения задач нестационарной теплопроводности. Расчет распределения температуры по сечению балки явным и неявным методами. Начальное распределение температуры в твердом теле (временные граничные условия). Преимущества неявного метода.
Автоматизированния система обучения программированию
Актуальной проблемой совершенствования учебного процесса является разработка программного обеспечения для его проведения. Очевидным пробелом является почти полное отсутствие средств обучения основам программирования.
Численное интегрирование функций
Характеристика методов численного интегрирования, квадратурные формулы, автоматический выбор шага интегрирования. Сравнительный анализ численных методов интегрирования средствами MathCAD, а также с использованием алгоритмических языков программирования.
Передаточная функция дискретной системы
Определение связи между выходом и входом для непрерывных систем. Вычисление передаточной функции и основы структурного метода дискретной системы. Расчет передаточной функции дискретной системы с обратной связью. Передаточные функции цифровых алгоритмов.
Замечательное уравнение кинематики
В предлагаемой статье рассмотрена возможность расширения сферы применения кинематических уравнений для решения задач механики. Показана возможность переноса метода составления простейших уравнений движения.
Методы прямоугольников и трапеций
Простейшим методом численного интегрирования является метод прямоугольников. Он непосредственно использует замену определенного интеграла интегральной суммой (3.20). В качестве точек ξi могут выбираться левые (ξ = xi-1) или правые (ξi = xi) границы элементарных отрезков. Обозначая f{xi) = yi, ∆xi = hi, получаем следующие формулы метода прямоугольников соответственно для этих двух случаев:
Модели и методы принятия решений
Нахождение экстремумов функций методом множителей Лагранжа. Выражение расширенной целевой функции. Схема алгоритма численного решения задачи методом штрафных функций в сочетании с методом безусловной минимизации. Построение линий ограничений.
Некоторые алгоритмы реализации UPSCALING
Средневзвешенное осреднение.. Осреднение фильтрационного сопротивления.. Расчет тензора проницаемости с учетом трубок тока. Определение тензора проницаемости по результатам численного моделирования.
Первая битва при мысе Финистерре 1747
Первая битва при мысе Финистерре — морское сражение состоялось 14 мая 1747 года, у мыса Финистерре между британским и французским флотом во время Войны за австрийское наследство.
Тарьян, Роберт
Введение 1 Образование 2 Карьера 2.1 Алгоритмы и структуры данных 3 Награды Список литературы Введение Роберт Андре Тарьян (англ. Robert Endre Tarjan, 30 апреля 1948 года, Помона, США) — известный американский учёный в области теории вычислительных систем. Родился 30 апреля 1948 года в калифорнийском городе Помона.
Кан, Дэвид
Дэвид Кан (англ. David Kahn) — американский историк, писатель и криптограф, автор фундаментального[1] труда по истории криптографии «Взломщики кодов», консультант Конгресса США по вопросам криптографии[2].
Лейзерсон, Чарльз Эрик
Чарльз Эрик Лейзерсон — профессор, американский специалист в области компьютерных наук, информатики. Специализируется на теории параллельных и распределённых вычислений и частично — практическим её применениям. Работая в этом направлении, разработал язык программирования Cilk для многопотоковых вычислений, который использует один из лучших алгоритмов захвата задачи (англ. work-stealing) при планировании.
Трахенбергский план
— план ведения согласованных боевых действий против Наполеона, составленный союзниками летом 1813 года во время войны 6-й коалиции за освобождение Европы.
Шнайер, Брюс
Брюс Шнайер (Bruce Schneier; род. 15 января 1963, Нью-Йорк) — американский криптограф, писатель и специалист по компьютерной безопасности. Президент и основатель криптографической компании Counterpane Systems, член совета директоров Международной ассоциации криптологических исследований и член консультативного совета Информационного центра электронной приватности.
Изучение принципов микропрограммного управления
Цель работы: Изучение принципов построения микропрограммного устройства управления. Теория: Развитие микроэлектронной базы запоминающих устройств позволило создать память, параметры которой существенно снизили влияние микропрограммирования на производительность процессора и ЭВМ в целом.
Алгоритмические языки: обработка одномерных массивов
Работа с массивами, их ввод и вывод, организация программ циклической структуры. Способы описания и использования массивов, алгоритмы их сортировки, сортировка выбором и вставками. Алгоритмы поиска элемента в неупорядоченном и упорядоченном массивах.
Решение обыкновенных дифференциальных уравнений
Команды, используемые при решении обыкновенных дифференциальных уравнений в системе вычислений Maple. Произвольные константы решения дифференциального уравнения второго порядка, представленном рядом Тейлора. Значения опции method при численном решении.
Алгоритмы численного решения задач
Графоаналитический метод решения задач. Получение задачи линейного программирования в основном виде. Вычисление градиента и поиск экстремумов методом множителей Лагранжа. Параболоид вращения функции. Поиск решения на основе условий Куна-Таккера.
Тесты по Информатике 2
Тест по информатике Алгоритмы: виды, свойства 9 класс по учебнику Угриновича Н.Д. Алгоритм-это: Указание на выполнение действий, Система правил, описывающая последовательность действий, которые необходимо выполнить для решения задачи,
Операционные узлы ЭВМ
1. Линейные алгоритмы Составить программу вычисления объема цилиндра и конуса, которые имеют одинаковую высоту Н и одинаковый радиус основания R. 2. Ветвящиеся алгоритмы – I раздел
Алгоритмы и исполнители
Алгоритмы и исполнители Тип урока: Изучение нового материала Вид урока: Комбинированный Цели урока: Закрепить понятие алгоритма как одного из основных понятий информатики.
Циклические алгоритмы
Циклические алгоритмы Алгоритмы содержащие команды повторения, называют циклическими. Команды повторения составляют цикл. Цикл - это такая форма организации действий, при которой одна последовательность действий повторяется несколько раз( или не разу), до тех пор , пока выполняются некоторые условия.
Место УСО в АСУ процесса бурения
Одно из главных различий между системами обработки данных и АСУ ТП состоит в том, что последняя должна быть способна в реальном времени получать информацию о состоянии объекта управления, реагировать на эту информацию.
Денежный поток 2
Денежный поток поток наличных денег (англ. Cash Flow; CF) — это абстрагированный от его экономического содержания численный ряд, состоящий из последовательности распределённых во времени платежей. Используется для расчёта показателей экономической эффективности инвестиций, а также для анализа движения денежных средств экономического субъекта во времени.