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

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

и линейная функция F = c₁x₁ + c₂x₂ +… + c_nx_n 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=(у ₁,…, y_m), 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=c₁x₁+c₂x₂+…c_nx_n

при условиях

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

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

2. Матрица

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



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

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

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

5. Если переменная x_j исходной задачи может принимать только лишь положительные значения, то j-е условие в системе двойственной задачи является неравенством вида «>». Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 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*)= [x₁(x₁*+3)+x₂(x₂* - 4)+x₃(x₃*+6)+

(y₁(-2x₁+3x₂+x₃+8)+y₂(-3x₁+x₂-2x₃-10)+y₃(3x₁-2x₂+2x₃+10)+y₄(-5x₁+4x₂-x₃+7) - x₁y₅-x₂y₆-x₃y₇)+<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)=3x₁-2x₂-5x₄+x₅->max

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

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

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

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

f(x)=-3x₁+2x₂+5x₄-x₅->min



Дано: f(x)=-3x₁+2x₂+5x₄-x₅ где

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

, y*,

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

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



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

Решение:

F*(x*, y*)= .

F*(x*, y*)= [x₁(x₁*+3)+x₂(x₂* - 2)+x₃(x₃*+0)+x₄(x₄* - 5)+x₅(x₅*+₅)+

(y₁(2x₁+x₃+x₄+x₅-2)+y₂(x₁-x₃+2x₄+x₅-3)+y₃(x₃-x₄+2x₅-6)+y₄(-x₁+x₂-x₄+5x₅+8) - x₁y₅-x₂y₆-x₃y₇-x₄y₈-x₅y₉)+<y*, z>]=

[x₁(x₁*+3)+x₂(x₂* - 2)+x₃(x₃*+0)+x₄(x₄* - 5)+x₅(x₅*+5)+

(2x₁ y₁+x₃ y₁+x₄ y₁+x₅ y₁-2 y₁+ x₁ y₂-x₃ y₂+2x₄ y₂+x₅ y₂-3 y₂+ x₃ y₃-x₄ y₃+2x₅ y₃-6 y₃-x₁ y₄+x₂ y₄-x₄ y₄+5x₅ y₄+8 y₄ - x₁y₅-x₂y₆-x₃y₇-x₄y₈-x₅y₉)+<y*, z>]=

[x₁(x₁*+3)+x₂(x₂* - 2)+x₃(x₃*+0)+x₄(x₄* - 5)+x₅(x₅*+5)+

x₁(2y₁+y₂-y₄-y₅)+x₂(y₄-y₆) +x₃(y₁-y₂+y₃-y₇)+x₄(y₁+2y₂-y₃-y₄-y₈)+x₅(y₁+y₂+2y₃+5y₄-y₉) - (-2y₁-3y₂-6y₃+8y₄)+<y*, z>]=

[x₁(x₁*+3+2y₁+y₂-y₄-y₅)+x₂(x₂* - 2+ y₄-y₆)+x₃(x₃*+0+ y₁-y₂+y₃-y₇)+x₄(x₄* - 5+ y₁+2y₂-y₃-y₄-y₈)+x₅(x₅*+5+ y₁+y₂+2y₃+5y₄-y₉) - (-2y₁-3y₂-6y₃+8y₄)+<y*, z>]

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

arg max , ,

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

2y₁+3y₂+6y₃-8y₄->max

2y₁+3y₂+6y₃-8y₄ где

7. f(x)=-16x₁-x₂+x₃+5x₄+5x₅->max

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

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

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

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

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

f(x)=16x₁+x2-x₃-5x₄-5x₅->min

Дано: f(x)=16x₁+x2-x₃-5x₄-5x₅ где

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

, y*,

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

F (x, y)=16x₁+x2-x₃-5x₄-5x₅->min

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

Решение:

F*(x*, y*)= .

F*(x*, y*)= [x₁(x₁* - 16)+x₂(x₂* - 1)+x₃(x₃*+1)+x₄(x₄*+5)+x₅(x₅*+5)+(y₁(2x₁+x₂+x₃-10)+y₂(-2x₁-x₂-x₃+10)+y₃(-2x₁+3x₂+x₄-6)+y₄(2x₁-3x₂-x₄+6)+y₅(2x₁+4x₂-x₅-8)+y₆(-2x₁-4x₂+x₅+8) - x₁y₇-x₂y₈-x₃y₉-x₄y₁₀-x₅y₁₁)+<y*, z>] [x₁(x₁* - 16)+x₂(x₂* - 1)+x₃(x₃*+1)+x₄(x₄*+5)+x₅(x₅*+5)+x₁(2y₁-2y₂-2y₃+2y₄+2y₅-2y₆-y₇)+x₂(y₁-y₂+3y₃-3y₄+4y₅-4y₆-y₈)+x₃(y₁-y₂-y₉)+x₄(y₃-y₄-y₁₀)+x₅(-y₅+y₆-y₁₁) - (-10y₁+10y₂-6y₃+6y₄-8y₅+8y₆)<y*, z>]= [x₁(x₁* - 16+2y₁-2y₂-2y₃+2y₄+2y₅-2y₆-y₇)+x₂(x₂* - 1+ y₁-y₂+3y₃-3y₄+4y₅-4y₆-y₈)+x₃(x₃*+1+ y₁-y2-y₉)+x₄(x₄*+5+ y₃-y₄-y₁₀)+x₅(x₅*+5-y₅+y₆-y₁₁) - (-10y₁+10y₂-6y₃+6y₄-8y₅+8y₆)+<y*, z>]

arg max , ,

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

10y₁-10y₂+6y₃-6y₄+8y₅-8y₆->max

где

8. f(x)=-x₁+4x₂+2x₄-x₅->max

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

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

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

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

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

f(x)=x₁-4x₂-2x₄+x₅ -> min

Дано: f(x)= x₁-4x₂-2x₄+x₅ где

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

, y*,

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

=x₁-4x₂-2x₄+x₅ -> min

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

Решение:

F*(x*, y*)= .

F*(x*)= [x₁(x₁* - 1)+x₂(x₂*+4)+x₃(x₃*+0)+x₄(x₄*+2)+x₅(x₅* - 1)+(y₁(x₁-5x₂+x₃-5)+y₂(-x₁+5x₂-x₃+5)+y₃(-x₁+x₂+x₄-4)+y₄(x₁-x₂-x₄+4)+y₅(x₁+x₂+x₅-8)+y₆(-x₁-x₂-x₅+8) - x₁y₇-x₂y₈-x₃y₉-x₄y₁₀-x₅y₁₁)+<y*, z=sup[x₁(x₁* - 1+ y₁-y₂-y₃+y₄+y₅-y₆-y₇)+x₂(x₂*+4-5y₁+5y₂+y₃-y₄+y₅-y₆-y₈)+x₃(x₃*+0+ y₁-y₂-y₉)+x₄(x₄*+2+ y₃+y₄-y₁₀)+x₅(x₅* - 1+ y₅-y₆-y₁₁) - (-5y₁+5y₂-4y₃+4y₄-8y₅+8y₆)]

arg max , ,

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

5y₁-5y₂+4y₃-4y₄+8y₅-8y₆->max

где

9. f(x)=-5x₁+x₂-x₃->max

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

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

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

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

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

F (x, y)=5x₁-x₂+x₃->min

Дано: f(x)= 5x₁-x₂+x₃ где

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

, y*,

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

F (x, y)=5x₁-x₂+x₃->min

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

Решение:

F*(x*, y*)= .

F*(x*)= [x₁(x₁* - 5)+x₂(x₂*+1)+x₃(x₃* - 1)+(y₁(3x₁-x₂-x₃-4)+y₂(-3x₁+x₂+x₃+4)+y₃(x₁-x₂+x₃-x₄-1)+y₄(-x₁+x₂-x₃+x₄+1)+y₅(2x₁+x₂+2x₃+x₅-7)+y6 (-2x₁-x₂-2x₃-x₅) - x₁y₇-x₂y₈-x₃y₉-x₄y₁₀-x₅y₁₁)+<y*, z>]= [x₁(x₁* - 5)+x₂(x₂*+1)+x₃(x₃* - 1)+x₁(3y₁-3y₂+y₃-y₄+2y₅-2y₆-y₇)+x₂(-y₁+y₂-y₃+y₄+y₅-y₆-y₈)+x₃(-y₁+y₂+y₃-y₄+2y₅-2y₆-y₉)+x₄(-y₃+y₄-y₁₀)+x₅(y₅-y₆-y₁₁) - (-4y₁+4y₂-y₃+y₄-7y₅+7y₆) +<y*, z>]= [x₁(x₁* - 5+3y₁-3y₂+y₃-y₄+2y₅-2y₆-y₇)+x₂(x₂*+1-y₁+y₂-y₃+y₄+y5-y₆-y₈)+x₃(x₃* - 1-y₁+y₂+y₃-y₄+2y₅-2y₆-y9)+x₄(-y₃+y₄-y₁₀)+x₅(y5-y₆-y₁₁) - (-4y₁+4y₂-y₃+y₄-7y₅+7y₆) +<y*, z>]

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

arg max , ,

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

4y₁-4y₂+y₃-y₄+7y₅-7y₆->max

где

10. f(x)=28x₁+24x₂+20x₃->max

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

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

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

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

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

f(x)=-28x₁-24x₂-20x₃->min

Дано: f(x)=-28x₁-24x₂-20x₃ где

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

, y*,

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

F (x, y)=-28x₁-24x₂-20x₃->min

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

Решение:

F*(x*, y*)= .

F*(x*)= [x₁(x₁*+28)+x₂(x₂*+24)+x₃(x₃*+20)+ (y₁(4x₁+2x₂+10x₃-42)+y₂(6x₁+2x₂+8x₃-12)+y₃(-6x₁-2x₂-8x₃+12)+y₄(-4x₁-2x₂-18x₃+25) - x₁y₅-x₂y₆-x₃y₇)+<y*, z>]= [x₁(x₁*+28+4y₁+6y₂-6y₃-4y₄-y₅)+x₂(x₂*+24+2y₁+2y₂-2y₃-2y₄-y₆)+x₃(x₃*+20+10y₁+8y₂-8y₃-18y₄-y₇) - (-42y₁-12y₂+12y₃+25y₄) +<y*, z>]

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

arg max , ,

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

42y₁+12y₂-12y₃-25y₄->max



где

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