рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД

КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД - раздел Программирование, Методические указания по изучению методов математического программирования общие рекомендации по использованию программного обеспечения Постановка Задачи Нелинейного Программирования. ...

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

Найти вектор x=(x1...,xn), что минимизирует (максимизирует) функцию

F(x)= F(x1...,xn) (18.1)

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

Gi(x1...,xn) Ri 0, i=1...,m (18.2)

где символ Ri заменяет один из знаков £, =, ³.

Если хотя бы одна из функций F, Gi(i=1...,m) является нелинейной, то указанная постановка определяет задачу нелинейного программирования (ЗНЛП).

Совокупность точек (векторов) x, которые удовлетворяют (18.2), называется допустимой областью (множеством) и отражается через D.

Произвольная точка D зовется допустимым решением (точкой, планом, вектором).

Функция F(x) соотношения (18.1) называется целевой функцией.

Постановка задачи выпуклого программирования.

Найти вектор x=(x1...,xn), что минимизирует целевую функцию

F(x)= F(x1...,xn) (18.3)

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

Gi(x1...,xn0, i=1...,m (18.4)

xj³0, j=1...,n (18.5)

где функции F, Gi (i=1...,m) — выпуклые.

Таким образом, для задачи выпуклого программирования (ЗОП) целевая функция (18.3) — выпуклая, ограничение (18.4)(18.5) определяют выпуклое допустимое множество.

Постановка задачи выпуклого квадратичного программирования.

Найти вектор x, что минимизирует целевую функцию

F(x)= x D xТ + c xТ(18.6)

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

А xТ £ , x ³ 0 (18.7)

где c=(c1...,cn), x=(x1...,xn), D=||dkl||, k,l=1...n, A=||aij||, i=1...,m, j=1...,n, b=(b1...,bm), матрица D симметричная и неотъемлемо определена.

Таким образом, для задачи выпуклого квадратичного программирования (ЗОКП) целевая функция (18.6) — выпуклая квадратичная, ограничение (18.7) — линейные и определяют выпуклое многогранное допустимое множество.

Заметим, что для случая n=2, m=1 ЗОКП имеет вид:

d11 x12 + d22 x22 + 2 d12 x1 x2 + c1 x1 + c2 x2 ® min

a11 x1 + a12 x2 £ a10, xj ³ 0, j=1,2

к тому же D=||dkl||, k,l=1,2, d12= d21.

Основные утверждения.

Определение. Множество W зовется выпуклым, если для произвольных точек x,yÎW, и tÎ[0,1] выполняется tx+(1–t)yÎW.

Определение. Функция H(x), xÎWÌEn, где W — выпуклое множество, зовется выпуклой, если для произвольных точек x,yÎW и tÎ[0,1] выполняется неравенство H(tx+(1–t)ytH(x)+(1–t)H(y).

Теорема. Множество {x:H(x)£0}, где функция H(x)выпуклая, является выпуклым.

Теорема.Пересечение выпуклых множеств является выпуклым множеством.

Теорема.Квадратичная функция F(x)=xDxТ+cxТвыпуклая, если матрица Dнеотъемлемо определена.

Теорема. Матрица Dнеотъемлемо определена, если все ее диагональные миноры неотъемлемые:

det(D(k))³0, D(k)=||dij||, і,j=1...k.

Теорема Куна-Таккера.

Пусть допустимая область D={xÎEn:Gi(x)£0,i=1...,m,x³0} задачи выпуклого программирования (18.3)(18.5) удовлетворяет условие Слейтера: существует xÎD такое, что для всех i=1...,m Gi(x)<0, то есть множество D имеет внутренние точки.

Тогда для того, чтобы вектор x*был оптимальным решением задачи выпуклого программирования, необходимо и достаточно, чтобы существовал вектор u*³0 такой, что пар (x*,u*) является точкой седла функции Лагранжа:

L(x,u)= F(x)+(u1G1(x) +...+ umGm(x))

x=(x1...,xn0, u=(u1...,um0.

Говорят, что точка (x*,u*) является точкой седла функции L(x,u), если для всех x³0, u³0 имеют место неравенства

L(x*,u) £ L(x*,u*) £ L(x,u*).

Теорема Куна-Таккера.

Для непрерывно дифференцированных функций F(x), Gi(x), i=1...,m, теорема Куна - Таккера может быть сформулированна так.

Вектор x*является оптимальным решением задачи выпуклого программирования (18.3)–(18.5) тогда и только тогда, когда существует вектор u*³0 такой, что для пары (x*,u*) выполняются условия:

ÑxL(x*,u*0 ÑxL(x*,u*)(x*) Т=0, j=1...,n

ÑuL(x*,u*0 ÑuL(x*,u*)(u*) Т=0, i=1...,m.

Для задачи (18.6)–(18.7) выпуклое квадратичное программирование последние соотношения приобретают виду

c+2xD+uA ³0 (18. 8)

(c+2xD+uA)=0 (18. 9)

xAТb £0 (18.10)

(xAТb)=0 (18.11)

x ³ 0, u ³ 0.

Вспомогательная ЗЛП для ЗВКП.

Если ввести векторы y=(y1...,yn0 та v=(v1...,vm0, то соотношение (18.8)–(18.11) будут иметь вид:

c + 2 x D + u Ав = 0 (18.12)

x АО b + v = 0 (18.13)

в xТ = 0, v uТ = 0 (18.14)

x ³ 0, u ³ 0, в ³ 0, v ³ 0.

Заметим, что для случая n=2, m=1 будем иметь

2 d11 x1 + 2 d12 x2 + a11 u y1 = c1

2 d12 x1 + 2 d22 x2 + a12 u y2 = c2

a11 x1 + a12 x2 + v = a10

x1 y1 = 0, x2 y2 = y2, u v = 0

x1, x2, u, y1, y2, v ³ 0.

Система (18.12)–(18.13) состоит из n+m линейных уравнений относительно 2(m+n) неизвестных xj, yj (j=1...,n), ui, vi (i=1...,m).

Кроме того, как следует из условий (18.14), должно быть:

если xj > 0, то yj = 0 (18.15)

если yj > 0, то xj = 0 (18.16)

если ui > 0, то vi = 0 (18.17)

если vi > 0, то ui = 0. (18.18)

Следовательно, искомым решением системы (18.12)–(18.13) может быть произвольное неотъемлемое базисное ее решение, но такой, что переменные xj и yj (а также ui и vi) с одинаковыми индексами не могут быть в то же время базисными. Для отыскивания такого решения можно применить любой из известных методов ЛП, в частности, метод искусственного базиса. С этой целью запишем систему (18.12)–(18.13) в виде

2 x D + u Ав = – c (18.19)

x АО + v = b. (18.20)

Не ограничивая всеобщности, будем считать, что правые части этой системы неотъемлемые: –c³0, b³0 (поскольку, в другом случае соответствующие уравнения, их правую и левую часть, достаточно умножить на –1). Согласно метода искусственного базиса в каждое уравнение системы (18.19)–(18.20), которое не содержит базисной переменной, вводим искусственную переменную. Поскольку переменные vi (i=1...,m) можно считать базисными, то искусственные переменные z=(z1...,zn0 вводим только в уравнение (18.19) и рассматриваем вспомогательную КЗЛП

z iТ ® min (18.21)

2 x D + u Ав + z = – c (18.22)

x AТ+v = b (18.23)

x ³ 0, u ³ 0, в ³ 0, v ³ 0, z ³ 0 (18.24)

где i=(1,1...,1) — n-мерный единичный вектор.

Квадратичный симплекс-метод.

Задача (18.21)–(18.24) решается симплекс-методом.

Если найденный ДБР этой задачи удовлетворяет условиям дополняющей нежесткости (18.15)–(18.18), то он определяет оптимальное решение исходной ЗВКП. Иначе нужно перейти к новому ДБР. При этом в базисные включается новая переменная с нулевой оценкой.

Симплекс-метод с условиями (18.15)–(18.18) для решения вспомогательной КЗЛП (18.21)–(18.24), построенной на основе задачи выпуклого квадратичного программирования (18.6)–(18.7), и называют квадратичным симплекс-методом (алгоритм обычного симплекс-метода, а также все связанные с ним определения и утверждения приведены в методических указаниях к лабораторной работе №2).

Если в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) все искусственные переменные zj (j=1...,n) принимают нулевые значения, то, отбрасывая их, получим ДБР системы (18.19)–(18.20). Та его часть, которая отвечает переменным начальной задачи выпуклого квадратичного программирования (18.6)–(18.7), и будет ее оптимальным решением.

Если же в оптимальном решении вспомогательной КЗЛП (18.21)–(18.24) значение хотя бы одной из искусственных переменных отличное от нуля, то система (18.19)–(18.20) решений не имеет, а, следовательно, множество седловых точек функции Лагранжа начальной задачи выпуклого квадратичного программирования пустое.

Программное обеспечение.

Обучающий модуль, с помощью которого задача выпуклого квадратичного программирования Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.

Геометрическая интерпретация задачи нелинейного программирования осуществляется модулем, который вызывается из того же самого раздела.


Задание.

Решить квадратичным симплекс-методом задачи выпуклого квадратичного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1–№9), а также следующие задачи.

Во всех задачах выполняются условия: x1 ³ 0, x2 ³ 0.

 

1) x12 + x222 x1 4 x2 ® min 2) 2 x12 3 x22 + 4 x1 x2 + 12 x2 ® max
2 x1 + 3 x2 £ 6; 3 x1 + 4 x2 £ 12;

 

3) 2 x12 + x22x1 x2x1 ® min 4) x12 + 3 x22x12 x2 ®min
x1 + 2 x2 £ 1; x1 + 4 x2 £ 7;

 

5) 2x12 3x22+16x1+24 x2 ®max 6) x12 + x223 x18 x2 ® min
2 x1 + x2 £ 4; x1 +2 x2 £ 4;

 

7) x12x22 + x1 + 2 x2 ® max 8) x12x22 + x1 x2 + 5 x1 + 2 x2 ® max
x1 + 2 x2 £ 16; 2 x1 +3 x2 £ 15.

 

Ответы:

1) x* = (0.69; 1.54). 2) x* = (1.23; 2.07). 3) x* = (0.29; 0.14). 4) x* = (0.5; 0.33).

5) x* = (0.57; 2.86). 6) x* = (0.4; 1.8). 7) x* = (0.5; 1). 8) x* = (3.63; 2.58).


Лабораторная работа 19.

– Конец работы –

Эта тема принадлежит разделу:

Методические указания по изучению методов математического программирования общие рекомендации по использованию программного обеспечения

Содержание.. общие рекомендации по использованию программного обеспечения.. элементарные преобразования матриц метод гаусса..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: КВАДРАТИЧНЫЙ СИМПЛЕКС-МЕТОД

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Программного обеспечения
Программное обеспечение ПО–МО содержит диалоговые обучающие программы из линейных и нелинейных методов оптимизации (математического программирования), каждая из которых вызывается с п

Постановка задачи.
Решить систему линейных алгебраических уравнений a11x1 + . . . + a1n xn = a10 . . . . . . . . . . . . . . . . . .

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. СИМПЛЕКС-МЕТОД
Постановка задачи линейного программирования в стандартной форме (СЗЛП). Найти вектор x=

МОДИФИЦИРОВАН СИМПЛЕКС-МЕТОД.
Изложение модифицированного симплекс-метода. Модифицированный симплекс-метод (МСМ) непосредственно применяется к решению КЗЛП и осуществляет целенапра

ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
Изложение двойственного симплекс-метода. Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного програм

Постановка транспортной задачи.
В каждом из пунктов Pi, i=1...,m, производится ai единиц некоторого однородного продукта, а в каждом из пунктов Qj, j=1...,n, потребляется b

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

Свойства транспортной задачи.
1. Сбалансированная транспортная задача всегда допустимая и имеет оптимальное решение. 2. Ранг матрицы А ограничений транспортной

Основные теоремы.
1. Решение транспортной задачи базисное, если из его основных коммуникаций невозможно составить замкнутый маршрут (цикл). 2. ДБР

Метод северо-западного угла.
Метод состоит из однотипных шагов, поэтому его формальное изложение дадим лишь для 1-го шага. Заполняем северо-западную клеточку таблицы, покладая x11 = min{a1,

Алгоритм метода потенциалов.
1. Находится исходное допустимое базисное решение (ДБР), например, с помощью одного из упомянутых выше методов. 2. В дальнейшем метод потенциалов с

Программное обеспечение.
Обучающий модуль, с помощью которого транспортная задача Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗ–МО

СПОСОБНОСТЯМИ. МЕТОД ПОТЕНЦИАЛОВ
Постановка транспортной задачи с ограниченными пропускными способностями (ТЗО). В пункте Pi (i=1

Свойства ТЗО и основные теоремы.
1. Ранг сложенной из векторов Aij матрицы А, ограничений транспортной задачи равняется m+n–1, откуда выплывает, чт

Выходной ДБР ТЗО. 1 этап.
На множестве невычеркнутых клеточек транспортной таблицы находят клеточку (i1,j1) с минимальными транспортными расходами

Выходной ДБР ТЗО. II этап.
Пусть X=||xij||, i=1...,m, j=1...,n — матрица перевозок, построенная на первом этапе. Положим xi,n+1 = ai – (

Потенциалы.
Потенциалы строк ui, i=1...,m, и столбцов vj, j=1...,n, определяются как решение системы vj–ui=cij

Оценки.
Оценки Dijпеременных xij для всех небазисных клеточек вычисляются за формулой Dij=cij–vj+ui (оценки базисных переменных — нулевые). Те

Новый ДБР.
Среди всех клеточек (і,j), для присоединяется к совокупности базисных клеточек. которых не выполняется критерий оптимума, избирают клеточку с наибольшим модулем оценки Dij. Пометим та

Алгоритм метода потенциалов.
1. Строится выходной ДБР. 2. Дальше метод потенциалов состоит из однотипных шагов, на каждом из которых: i) Вычисляются потенциалы u

ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ НА СЕТИ. МЕТОД МИНТИ
Постановка задачи о кратчайшем пути на сети. На сети, что задается графом (I,U), где И — множество вершин,

МЕТОД ФОРДА-ФАЛКЕРСОНА
Постановка задачи о максимальном потоке на сети. На сети, что задается графом (I,U), где I — множество вершин,

Постановка целочисленной задачи линейного программирования.
Найти вектор x=(x1...,xn), что минимизирует целевую функцию L(x)= c1x1 + ... + cnxn (9.1)

Изложение метода Гомори-1.
Метод Гомори-1 является одним из методов отсечения, идея которых заключается в следующем. Решается вспомогательная ЗЛП (9.1)–(9.3), которую получают из исходной ЦЗЛП (9.1)–(9

Алгоритм метода Гомори-1.
1. Решаем вспомогательную ЗЛП (9.1)–(9.3). Пусть x(0) — ее оптимальное решение. Если оптимальное решение не существует, то исходная ЦЗЛП также

ПРОГРАММИРОВАНИЯ. МЕТОД ГОМОРИ-2
Постановка частично целочисленной задачи линейного программирования (ЧЦЗЛП). Найти вектор x=(x1...,xn

МЕТОД ГОМОРИ-3
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

ПРОГРАММИРОВАНИЯ. МЕТОД ДАЛЬТОНА-ЛЛЕВЕЛИНА
Постановка частично дискретной задачи линейного программирования (ЧДЗЛП). Найти вектор x=(x1...,xn

МЕТОД ВЕТВЕЙ И ГРАНИЦ.
Постановка целочисленной задачи линейного программирования (ЦЗЛП). Найти вектор x=(x1...,xn), что

Изложение метода Ленд-Дойга.
Решается вспомогательная ЗЛП (13.1)–(13.3), которая получена из исходной ЦЗЛП (13.1)–(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1

Алгоритм метода Ленд-Дойга.
1. Определяются множества D(k;r) условиями (13.2), (13.3) и дополнительными ограничениями, которые возникают в процессе разветвления

ЗАДАЧА О НАЗНАЧЕНИИ. ВЕНГЕРСКИЙ МЕТОД
Постановка задачи о назначении. Найти вектор (матрицу) X=(xij, і,j=1...,n), что минимизирует целевую функцию

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА
Постановка задачи такая же самая, как и в предыдущем разделе (14.1–14.4). Алгоритм метода Мака.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН
Постановка матричной игры двух лиц с нулевой суммой. Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданн

Метод золотого сечения.
Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм мето

Метод случайного поиска.
Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

Метод дихотомии (половинного деления).
Метод дихотомии (МД) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реа

Градиентные методы безусловной оптимизации.
Для задачи безусловной минимизации метод заключается в вычислении последовательности приближений x[s] по правилу x[s+1]=

Метод самого быстрого спуска.
Метод самого быстрого спуска представляет собой градиентный метод, в котором величина шага r[s] выбирается по правилу F(x[s]–r

Лiтература
1. Ю.М.Ермольев, И.И.Ляшко, В.С.Михалевич, В.И.Тюптя.Математические методы исследования операций. Киев, «Высшая школа», 1979. 2. Ю.Д.Попов. Линейное и нел

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги