Двойственные задачи линейного программирования

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

Рубрика Математика
Вид дипломная работа
Язык русский
Дата добавления 30.04.2011
Размер файла 2,6 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

Одним из приоритетных направлений процесса информатизации современного общества является информатизация образования - внедрение средств новых информационных технологий в систему образования. Это сделает возможным:

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

- совершенствование методологии и стратегии отбора содержания, методов и организационных форм обучения, соответствующих задачам развития личности обучаемого в современных условиях информатизации общества;

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

- создание и использование компьютерных тестирующих, диагностирующих, контролирующих и оценивающих систем.

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

В работе рассмотрена одна из сторон процесса информатизации общества и образования - создание одной из форм обучения с использованием средств новых информационных технологий - электронно-методическое пособие «Двойственные задачи линейного программирования».

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

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

Вышеуказанные аспекты определили актуальность исследования и явились причиной разработки и создания электронного учебного пособия на тему «Двойственные задачи линейного программирования».

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

В качестве предмета исследования рассматривается содержание и реализация электронного пособия.

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

Для достижения поставленной цели необходимо решить следующие задачи:

- Изучить необходимую методическую литературу по линейному программированию; выполнить анализ предметной области, на основании которого будет подобран материал для электронного учебного пособия;

- определить требования к электронным образовательным ресурсам;

- выбрать наиболее подходящие средства реализации;

- спроектировать структуру и создать дизайн электронного пособия;

- систематизировать, оцифровать, и структурировать собранный материал;

- наполнить содержанием структуру электронного образовательного ресурса;

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

целевая функция линейное программирование

1. Теоретическая часть

1.1 Основные определения

Задача линейного программирования - это нахождение минимума линейной функции f: n > 1, заданной на некотором замкнутом выпуклом множестве, выделенном линейными неравенствами.

Общая задача линейного программирования имеет вид:

Дана система m линейных уравнений и неравенств с n переменными

(1)

и линейная функция F = c1x1 + c2x2 +… + cnxn min (max)

Система (1) называется системой ограничений, а функция F - линейной функцией, линейной формой, целевой функцией или функцией цели.

Более кратко общую задачу линейного программирования можно представить в виде:

arg ,

x={x|Axb, A=, b=(T)}

Задачу линейного программирования записывают и в других формах - канонической и нормальной. Канонической задачей - обозначение Зк, назовем такую:

Зк: arg ,

x={x|Axb, ?0, j=)}

Нормальной задачей - обозначение Зн, назовем такую

Зн: arg ,

x={x|Axb, ?0, j=)}

1.2 Выпуклые множества и функции

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

На следующем рисунке изображены два множества на плоскости : одно выпуклое, а другое нет.

Рис. 1

Выпуклыми в пространстве являются, например, такие множества: всё пространство , его положительный октант и неотрицательный октант , любой шар, как открытый , так и замкнутый , любая гиперплоскость (заданная некоторым уравнением вида , а также открытое и замкнутое полупространства, заданные, соответственно, условиями и .

Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.

Точка множества называется внутренней, если в некоторой ее окрестности содержатся точки только данного множества.

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

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

На рис. приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка N) и угловых (точки А, В, С, D, Е). Точка А - угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка АР, она не является внутренней; точка А - внутренняя для отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.

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

Функция f: называется выпуклой, если ее надграфик epi f= является выпуклым множеством. На рисунке изображена выпуклая функция, её график выделен синим и надграфик закрашен зеленым.

Функция f: называется замкнутой, если ее надграфик - замкнутое множество.

Геометрический смысл решений неравенств, уравнений и их систем

Рассмотрим решения неравенств.

Утверждение 1. Множество решений неравенства с двумя переменными a11x1+a12x2<=b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой a11x1+a12x2=b1, включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства a11x1+a12x2>=b1.

Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не лежащую на ее границе - построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется и во всех точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в случае невыполнения неравенства в контрольной точке, оно не выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости. В качестве контрольной точки удобно взять начало координат О (0; 0), не лежащее на построенной прямой.

Рассмотрим множество решений систем неравенств.

Утверждение 2. Множество решений совместной системы т линейных неравенств с двумя переменными является выпуклым многоугольником (или выпуклой многоугольной областью).

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

Координаты угловых точек - вершин многоугольника находят как координаты точек пересечения соответствующих прямых.

При построении областей решений систем неравенств могут встретиться и другие случаи: множество решений - выпуклая многоугольная область (рис. а); одна точка (рис. б); пустое множество, когда система неравенств несовместна (рис. в).

1.3 Определение понятия двойственности с помощью преобразования Лежандра

Пусть f:. Функция f*: определенная равенством f*(x*)==(x* ), называется сопряженной функцией к f, а функция f**: определенная по правилу f**(x*)==(x* ), называется второй сопряженной функцией к f.

Отображение f* (x*) =< x*, x> ? f(x) называется преобразованием Лежандра.

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

где X - линейное пространство, включается в класс подобных ей задач, зависящих от параметра:

где Y - некоторое другое линейное пространство, F (x, 0)=f(x) (функцию F называют возмущением f). Обычно F предполагается выпуклой. Двойственной к задаче по отношению к данному возмущению наз. задача

где F* - функция, двойственная (сопряженная) с F в смысле Лежандра - Юнга - Фенхеля. Такая двойственность позволяет связать с каждой выпуклой функцией f: X-> R двойственный объект - сопряженную функцию, заданную на сопряженном пространстве X* и определяемую формулой

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

где X - линейное пространство, выпуклые функции на X, В-выпуклое множество в X (частными случаями (3) являются задачи линейного программирования), обычно применяются следующие стандартные возмущения, зависящие от параметров y=(у 1,…, ym), m, Теоремы двойственности для общих классов задач выпуклого программирования утверждают, что при некоторых допущениях на возмущение F значения задач (2) и (2*) совпадают, и более того, решение одной из задач является множителем Лагранжа для другой.

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

Выпишем двойственную задачу к задаче линейного программирования.

Пусть с -матрица размера n х m и b. Задачу , называют общей задачей линейного программирования.

В терминах общей постановки здесь f(x)= и f(x)= в противном случае.

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

, y*,

где y (т.е. , y*, ).

Итак, применим преобразование Лежандра

F*(x*, y*)= =

=

= =

Далее преобразуем неравенство в уравнение, подставив новую переменную z. Получим , где z . Теперь произведем замену переменных, вместо y подставим формулу .

Раскрыв скобки, совершив преобразования, получим

Если 0 и хотя бы один |y*|x, z будет равен . Если y*=0, то максимум по будет равен . Если 0 и хотя бы один |y*| .

Поэтому

Теперь выделим конечные значения :

Упростим

И тогда получим

Таким образом, получаем двойственную задачу:

arg max , ,

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

F=c1x1+c2x2+…cnxn

при условиях

Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи задается на минимум, а целевая функция двойственной на максимум.

2. Матрица

составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица

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

3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.

5. Если переменная xj исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная xj может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i - соотношение в системе исходной задачи является неравенством, то i-я переменная двойственной задачи . В противном случае переменная уj может принимать как положительные, так и отрицательные значения.

Для задач канонической и нормальной (и другим) двойственными называются те, которые являются двойственными к общим задачам, эквивалентным первоначально поставленным.

Решение задач

Рассмотрим процесс построения двойственной задачи на конкретных примерах.

1.

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb})

Axb запишем в виде - Axb:

Итак, нам дано:

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

, y*,

где y (т.е. , y*, ).

Найти: arg max - F*(0, y*)

Решение:

Итак, применим преобразование Лежандра

F*(x*, y*)= =

=

Упростим выражение

{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим

= .

Итак, подставим значения в данное выражение.

Теперь раскроем скобки:

Вынесем за скобки x. Получим:

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

где

2.

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb})

Axb запишем в виде - Axb:

Итак, нам дано:

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

, y*,

где y (т.е. , y*, ).

Найти: arg max - F*(0, y*)

Решение:

Итак, применим преобразование Лежандра

F*(x*, y*)= =

=

Упростим выражение

{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим

= .

Итак, подставим значения в данное выражение.

Теперь раскроем скобки:

Вынесем за скобки x. Получим:

=

=

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

где

3.

Приведем задачу линейного программирования к общему виду

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb;

Дано:

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

, y*,

где y (т.е. , y*, ).

Найти: arg max - F*(0, y*)

Решение:

Итак, применим преобразование Лежандра

F*(x*, y*)= =

=

Упростим выражение

{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим

= .

Итак, подставим значения в данное выражение.

F*(x*)= [x1(x1*+3)+x2(x2* - 4)+x3(x3*+6)+

(y1(-2x1+3x2+x3+8)+y2(-3x1+x2-2x3-10)+y3(3x1-2x2+2x3+10)+y4(-5x1+4x2-x3+7) - x1y5-x2y6-x3y7)+<y*, z>]

Теперь раскроем скобки:

=

Вынесем за скобки x. Получим:

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

где

4.

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}).

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb;

Итак, нам дано:

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

, y*,

где y (т.е. , y*, ).

Найти: argmax - F (0, y)

Решение:

Итак, применим преобразование Лежандра

F*(x*, y*)= =

=

Упростим выражение

{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим

= .

Итак, подставим значения в данное выражение.

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

где

5.

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Дано: где

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

, y*,

где y (т.е. , y*, ).

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

->max

где

6. f(x)=3x1-2x2-5x4+x5->max

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

f(x)=-3x1+2x2+5x4-x5->min

Дано: f(x)=-3x1+2x2+5x4-x5 где

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

, y*,

где y (т.е. , y*, ).

F=-3x1+2x2+5x4-x5->min

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

F*(x*, y*)= [x1(x1*+3)+x2(x2* - 2)+x3(x3*+0)+x4(x4* - 5)+x5(x5*+5)+

(y1(2x1+x3+x4+x5-2)+y2(x1-x3+2x4+x5-3)+y3(x3-x4+2x5-6)+y4(-x1+x2-x4+5x5+8) - x1y5-x2y6-x3y7-x4y8-x5y9)+<y*, z>]=

[x1(x1*+3)+x2(x2* - 2)+x3(x3*+0)+x4(x4* - 5)+x5(x5*+5)+

(2x1 y1+x3 y1+x4 y1+x5 y1-2 y1+ x1 y2-x3 y2+2x4 y2+x5 y2-3 y2+ x3 y3-x4 y3+2x5 y3-6 y3-x1 y4+x2 y4-x4 y4+5x5 y4+8 y4 - x1y5-x2y6-x3y7-x4y8-x5y9)+<y*, z>]=

[x1(x1*+3)+x2(x2* - 2)+x3(x3*+0)+x4(x4* - 5)+x5(x5*+5)+

x1(2y1+y2-y4-y5)+x2(y4-y6) +x3(y1-y2+y3-y7)+x4(y1+2y2-y3-y4-y8)+x5(y1+y2+2y3+5y4-y9) - (-2y1-3y2-6y3+8y4)+<y*, z>]=

[x1(x1*+3+2y1+y2-y4-y5)+x2(x2* - 2+ y4-y6)+x3(x3*+0+ y1-y2+y3-y7)+x4(x4* - 5+ y1+2y2-y3-y4-y8)+x5(x5*+5+ y1+y2+2y3+5y4-y9) - (-2y1-3y2-6y3+8y4)+<y*, z>]

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

2y1+3y2+6y3-8y4->max

2y1+3y2+6y3-8y4 где

7. f(x)=-16x1-x2+x3+5x4+5x5->max

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb

f(x)=16x1+x2-x3-5x4-5x5->min

Дано: f(x)=16x1+x2-x3-5x4-5x5 где

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

, y*,

где y (т.е. , y*, ).

F (x, y)=16x1+x2-x3-5x4-5x5->min

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

F*(x*, y*)= [x1(x1* - 16)+x2(x2* - 1)+x3(x3*+1)+x4(x4*+5)+x5(x5*+5)+(y1(2x1+x2+x3-10)+y2(-2x1-x2-x3+10)+y3(-2x1+3x2+x4-6)+y4(2x1-3x2-x4+6)+y5(2x1+4x2-x5-8)+y6(-2x1-4x2+x5+8) - x1y7-x2y8-x3y9-x4y10-x5y11)+<y*, z>] [x1(x1* - 16)+x2(x2* - 1)+x3(x3*+1)+x4(x4*+5)+x5(x5*+5)+x1(2y1-2y2-2y3+2y4+2y5-2y6-y7)+x2(y1-y2+3y3-3y4+4y5-4y6-y8)+x3(y1-y2-y9)+x4(y3-y4-y10)+x5(-y5+y6-y11) - (-10y1+10y2-6y3+6y4-8y5+8y6)<y*, z>]= [x1(x1* - 16+2y1-2y2-2y3+2y4+2y5-2y6-y7)+x2(x2* - 1+ y1-y2+3y3-3y4+4y5-4y6-y8)+x3(x3*+1+ y1-y2-y9)+x4(x4*+5+ y3-y4-y10)+x5(x5*+5-y5+y6-y11) - (-10y1+10y2-6y3+6y4-8y5+8y6)+<y*, z>]

arg max , ,

Итак, двойственная задача имеет вид:

10y1-10y2+6y3-6y4+8y5-8y6->max

где

8. f(x)=-x1+4x2+2x4-x5->max

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb

f(x)=x1-4x2-2x4+x5 -> min

Дано: f(x)= x1-4x2-2x4+x5 где

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

, y*,

где y (т.е. , y*, ).

=x1-4x2-2x4+x5 -> min

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

F*(x*)= [x1(x1* - 1)+x2(x2*+4)+x3(x3*+0)+x4(x4*+2)+x5(x5* - 1)+(y1(x1-5x2+x3-5)+y2(-x1+5x2-x3+5)+y3(-x1+x2+x4-4)+y4(x1-x2-x4+4)+y5(x1+x2+x5-8)+y6(-x1-x2-x5+8) - x1y7-x2y8-x3y9-x4y10-x5y11)+<y*, z=sup[x1(x1* - 1+ y1-y2-y3+y4+y5-y6-y7)+x2(x2*+4-5y1+5y2+y3-y4+y5-y6-y8)+x3(x3*+0+ y1-y2-y9)+x4(x4*+2+ y3+y4-y10)+x5(x5* - 1+ y5-y6-y11) - (-5y1+5y2-4y3+4y4-8y5+8y6)]

arg max , ,

Итак, двойственная задача имеет вид:

5y1-5y2+4y3-4y4+8y5-8y6->max

где

9. f(x)=-5x1+x2-x3->max

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb

F (x, y)=5x1-x2+x3->min

Дано: f(x)= 5x1-x2+x3 где

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

, y*,

где y (т.е. , y*, ).

F (x, y)=5x1-x2+x3->min

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

F*(x*)= [x1(x1* - 5)+x2(x2*+1)+x3(x3* - 1)+(y1(3x1-x2-x3-4)+y2(-3x1+x2+x3+4)+y3(x1-x2+x3-x4-1)+y4(-x1+x2-x3+x4+1)+y5(2x1+x2+2x3+x5-7)+y6 (-2x1-x2-2x3-x5) - x1y7-x2y8-x3y9-x4y10-x5y11)+<y*, z>]= [x1(x1* - 5)+x2(x2*+1)+x3(x3* - 1)+x1(3y1-3y2+y3-y4+2y5-2y6-y7)+x2(-y1+y2-y3+y4+y5-y6-y8)+x3(-y1+y2+y3-y4+2y5-2y6-y9)+x4(-y3+y4-y10)+x5(y5-y6-y11) - (-4y1+4y2-y3+y4-7y5+7y6) +<y*, z>]= [x1(x1* - 5+3y1-3y2+y3-y4+2y5-2y6-y7)+x2(x2*+1-y1+y2-y3+y4+y5-y6-y8)+x3(x3* - 1-y1+y2+y3-y4+2y5-2y6-y9)+x4(-y3+y4-y10)+x5(y5-y6-y11) - (-4y1+4y2-y3+y4-7y5+7y6) +<y*, z>]

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

4y1-4y2+y3-y4+7y5-7y6->max

где

10. f(x)=28x1+24x2+20x3->max

Приведем задачу линейного программирования к общему виду

(arg , где {x|Axb}):

Целевую функцию <c, x>, которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);

Axb запишем в виде - Axb;

Axb запишем в виде Axb, - Axb

f(x)=-28x1-24x2-20x3->min

Дано: f(x)=-28x1-24x2-20x3 где

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

, y*,

где y (т.е. , y*, ).

F (x, y)=-28x1-24x2-20x3->min

Найти: arg max - F (0, y)

Решение:

F*(x*, y*)= .

F*(x*)= [x1(x1*+28)+x2(x2*+24)+x3(x3*+20)+ (y1(4x1+2x2+10x3-42)+y2(6x1+2x2+8x3-12)+y3(-6x1-2x2-8x3+12)+y4(-4x1-2x2-18x3+25) - x1y5-x2y6-x3y7)+<y*, z>]= [x1(x1*+28+4y1+6y2-6y3-4y4-y5)+x2(x2*+24+2y1+2y2-2y3-2y4-y6)+x3(x3*+20+10y1+8y2-8y3-18y4-y7) - (-42y1-12y2+12y3+25y4) +<y*, z>]

Таким образом, получаем двойственную задачу:

arg max , ,

Итак, двойственная задача имеет вид:

42y1+12y2-12y3-25y4->max

где

Размещено на Allbest.ru


Подобные документы

  • Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на Visual Basic for Application.

    курсовая работа [703,5 K], добавлен 14.10.2011

  • Знакомство с особенностями построения математических моделей задач линейного программирования. Характеристика проблем составления математической модели двойственной задачи, обзор дополнительных переменных. Рассмотрение основанных функций новых переменных.

    задача [656,1 K], добавлен 01.06.2016

  • Сущность понятия "симплекс-метод". Математические модели пары двойственных задач линейного программирования. Решение задачи симплексным методом: определение минимального значения целевой функции, построение первого опорного плана, матрица коэффициентов.

    курсовая работа [219,4 K], добавлен 17.04.2013

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

    задача [394,9 K], добавлен 21.08.2010

  • Определение производной функции, геометрический смысл ее приращения. Геометрический смысл заданного отношения. Физический смысл производной функции в данной точке. Число, к которому стремится заданное отношение. Анализ примеров вычисления производной.

    презентация [696,5 K], добавлен 18.12.2014

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

    курсовая работа [807,2 K], добавлен 03.04.2015

  • Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.

    контрольная работа [333,3 K], добавлен 27.11.2011

  • Основные понятия теории систем уравнений. Метод Гаусса — метод последовательного исключения переменных. Формулы Крамера. Решение систем линейных уравнений методом обратной матрицы. Теорема Кронекер–Капелли. Совместность систем однородных уравнений.

    лекция [24,2 K], добавлен 14.12.2010

  • Порядок и принципы составления дифференциального уравнения, методика нахождения неизвестных значений. Замена исходного дифференциального уравнения на систему n-линейных уравнений относительно n-неизвестных. Формирование и решение системы уравнений.

    задача [118,8 K], добавлен 20.09.2013

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

    курсовая работа [69,8 K], добавлен 09.12.2011

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.