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

Главная

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

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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


Информатизация общества - это глобальный социальный процесс, особенность которого состоит в том, что доминирующим видом деятельности в сфере общественного производства является сбор, накопление, продуцирование, обработка, хранение, передача и использование информации, осуществляемые на основе современных средств микропроцессорной и вычислительной техники, а также на базе разнообразных средств информационного обмена.
Одним из приоритетных направлений процесса информатизации современного общества является информатизация образования - внедрение средств новых информационных технологий в систему образования. Это сделает возможным:
- совершенствование механизмов у правления системой образования на основе использования автоматизированных банков данных научно-педагогической информации, информационно-методических материалов, а также коммуникационных сетей;
- совершенствование методологии и стратегии отбора содержания, методов и организационных форм обучения, соответствующих задачам развития личности обучаемого в современных условиях информатизации общества;
- создание методических систем обучения, ориентированных на развитие интеллектуального потенциала обучаемого, на формирование умений самостоятельно приобретать знания, осуществлять информационно-учебную, экспериментально - исследовательскую деятельность, разнообразные виды самостоятельной деятельности по обработке информации;
- создание и использование компьютерных тестирующих, диагностирующих, контролирующих и оценивающих систем.
Так как электронное пособие является литературой нового поколения, которая объединила в себе достоинства традиционных учебников и возможности компьютерных технологий, в настоящее время это актуально.
В работе рассмотрена одна из сторон процесса информатизации общества и образования - создание одной из форм обучения с использованием средств новых информационных технологий - электронно-методическое пособие «Двойственные задачи линейного программирования».
ЛП-область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. равенств или неравенств, связывающих эти переменные.
Центральным результатом теории линейного программирования является теория двойственности. Под двойственной задачей понимается вспомогательная задача линейного программирования, формулируемая с помощью определённых правил непосредственно из условий прямой задачи. Заинтересованность в определении оптимального решения прямой задачи путём решения двойственной к ней задачи обусловлена тем, что вычисления при решении двойственной задачи могут оказаться менее сложными. В дипломной работе для вывода двойственных задач применено преобразование Лежандра , а также приведены некоторые теоремы и их доказательства .
Вышеуказанные аспекты определили актуальность исследования и явились причиной разработки и создания электронного учебного пособия на тему «Двойственные задачи линейного программирования».
Объектом данного исследования является использование и создание компьютерных средств обучения.
В качестве предмета исследования рассматривается содержание и реализация электронного пособия.
Целью дипломной работы является разработка электронного пособия для формирования знаний, умений и навыков студентов в построении двойственных задач линейного программирования.
Для достижения поставленной цели необходимо решить следующие задачи:
- Изучить необходимую методическую литературу по линейному программированию; выполнить анализ предметной области, на основании которого будет подобран материал для электронного учебного пособия;
- определить требования к электронным образовательным ресурсам;
- выбрать наиболее подходящие средства реализации;
- спроектировать структуру и создать дизайн электронного пособия;
- систематизировать, оцифровать, и структурировать собранный материал;
- наполнить содержанием структуру электронного образовательного ресурса;
Итогом работы должно стать электронное учебное пособие «Двойственные задачи линейного программирования», которое поможет преподавателю в организации образовательной деятельности, а также студентам высших учебных заведений в самостоятельном изучении материала по данной теме.
целевая функция линейное программирование
Задача линейного программирования - это нахождение минимума линейной функции f : n > 1 , заданной на некотором замкнутом выпуклом множестве, выделенном линейными неравенствами.
Общая задача линейного программирования имеет вид:
Дана система m линейных уравнений и неравенств с n переменными
и линейная функция F = c 1 x 1 + c 2 x 2 +… + c n x n min (max)
Система (1) называется системой ограничений, а функция F - линейной функцией, линейной формой, целевой функцией или функцией цели.
Более кратко общую задачу линейного программирования можно представить в виде:
Задачу линейного программирования записывают и в других формах - канонической и нормальной. Канонической задачей - обозначение Зк, назовем такую:
Нормальной задачей - обозначение Зн, назовем такую
Определение выпуклого множества: множество - - выпуклое, если вместе с любыми двумя точками множеству принадлежат все точки отрезка, соединяющего в пространстве точку с точкой .
На следующем рисунке изображены два множества на плоскости : одно выпуклое, а другое нет.
Выпуклыми в пространстве являются, например, такие множества: всё пространство , его положительный октант и неотрицательный октант , любой шар, как открытый , так и замкнутый , любая гиперплоскость (заданная некоторым уравнением вида , а также открытое и замкнутое полупространства, заданные, соответственно, условиями и .
Среди точек выпуклого множества можно выделить внутренние, граничные и угловые точки.
Точка множества называется внутренней , если в некоторой ее окрестности содержатся точки только данного множества.
Точка множества называется граничной , если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему.
Особый интерес в задачах линейного программирования представляют угловые точки. Точка множества называется угловой (или крайней), если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
На рис. приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка 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 ,…, y m ), m, Теоремы двойственности для общих классов задач выпуклого программирования утверждают, что при некоторых допущениях на возмущение F значения задач (2) и (2*) совпадают, и более того, решение одной из задач является множителем Лагранжа для другой.
2. Двойственная з адача линейного программирования
Выпишем двойственную задачу к задаче линейного программирования.
Пусть с -матрица размера n х m и b. Задачу , называют общей задачей линейного программирования.
В терминах общей постановки здесь f(x)= и f(x)= в противном случае.
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Итак, применим преобразование Лежандра
Далее преобразуем неравенство в уравнение, подставив новую переменную z. Получим , где z . Теперь произведем замену переменных, вместо y подставим формулу .
Раскрыв скобки, совершив преобразования, получим
Если 0 и хотя бы один |y*|x, z будет равен . Если y*=0, то максимум по будет равен . Если 0 и хотя бы один |y*| .
Таким образом, получаем двойственную задачу:
Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении минимального значения функции:
Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:
1. Целевая функция исходной задачи задается на минимум, а целевая функция двойственной на максимум.
составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица
в двойственной задаче получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).
3. Число переменных в двойственной задаче равно числу ограничений в системе исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной задаче.
4. Коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе исходной задачи, а правыми частями в соотношениях системы двойственной задачи - коэффициенты при неизвестных в целевой функции исходной задачи.
5. Если переменная x j исходной задачи может принимать только лишь положительные значения, то j -е условие в системе двойственной задачи является неравенством вида «>». Если же переменная x j может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями исходной задачи и переменными двойственной задачи. Если i - соотношение в системе исходной задачи является неравенством, то i -я переменная двойственной задачи . В противном случае переменная у j может принимать как положительные, так и отрицательные значения.
Для задач канонической и нормальной (и другим) двойственными называются те, которые являются двойственными к общим задачам, эквивалентным первоначально поставленным.
Рассмотрим процесс построения двойственной задачи на конкретных примерах.
Приведем задачу линейного программирования к общему виду
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Итак, применим преобразование Лежандра
{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим
Итак, подставим значения в данное выражение.
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
Приведем задачу линейного программирования к общему виду
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Итак, применим преобразование Лежандра
{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим
Итак, подставим значения в данное выражение.
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
Приведем задачу линейного программирования к общему виду
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Итак, применим преобразование Лежандра
{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим
Итак, подставим значения в данное выражение.
F*(x *)= [x 1 (x 1 *+3)+x 2 (x 2 * - 4)+x 3 (x 3 *+6)+
(y 1 (-2x 1 +3x 2 +x 3 +8)+y 2 (-3x 1 +x 2 -2x 3 -10)+y 3 (3x 1 -2x 2 +2x 3 +10)+y 4 (-5x 1 +4x 2 -x 3 +7) - x 1 y 5 -x 2 y 6 -x 3 y 7 )+]
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Итак, применим преобразование Лежандра
{Ax-b?y}, значит, подставив новую переменную, можно составить уравнение y=Ax-b+z. Произведем замену переменных, вместо y подставим формулу Получим
Итак, подставим значения в данное выражение.
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
6 . f(x) =3 x 1 -2x 2 -5 x 4 +x 5 -> max
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
f(x) =-3 x 1 +2 x 2 +5 x 4 - x 5 -> min
Дано: f ( x )=-3 x 1 +2 x 2 +5 x 4 - x 5 где
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
F *( x *, y*)= [x 1 (x 1 *+3)+x 2 (x 2 * - 2)+x 3 (x 3 *+0)+x 4 (x 4 * - 5)+x 5 (x 5 *+ 5 )+
(y 1 (2x 1 +x 3 +x 4 +x 5 -2)+y 2 (x 1 -x 3 +2x 4 +x 5 -3)+y 3 (x 3 -x 4 +2x 5 -6)+y 4 (-x 1 +x 2 -x 4 +5x 5 +8) - x 1 y 5 -x 2 y 6 -x 3 y 7 -x 4 y 8 -x 5 y 9 )+]=
[x 1 (x 1 *+3)+x 2 (x 2 * - 2)+x 3 (x 3 *+0)+x 4 (x 4 * - 5)+x 5 (x 5 *+5)+
(2x 1 y 1 +x 3 y 1 +x 4 y 1 +x 5 y 1 -2 y 1 + x 1 y 2 -x 3 y 2 +2x 4 y 2 +x 5 y 2 -3 y 2 + x 3 y 3 -x 4 y 3 +2x 5 y 3 -6 y 3 -x 1 y 4 +x 2 y 4 -x 4 y 4 +5x 5 y 4 +8 y 4 - x 1 y 5 -x 2 y 6 -x 3 y 7 -x 4 y 8 -x 5 y 9 )+]=
[x 1 (x 1 *+3)+x 2 (x 2 * - 2)+x 3 (x 3 *+0)+x 4 (x 4 * - 5)+x 5 (x 5 *+5)+
x 1 (2y 1 +y 2 -y 4 -y 5 )+x 2 (y 4 -y 6 ) +x 3 (y 1 -y 2 +y 3 -y 7 )+x 4 (y 1 +2y 2 -y 3 -y 4 -y 8 )+x 5 (y 1 +y 2 +2y 3 +5y 4 -y 9 ) - (-2y 1 -3y 2 -6y 3 +8y 4 )+]=
[x 1 (x 1 *+3+2y 1 +y 2 -y 4 -y 5 )+x 2 (x 2 * - 2+ y 4 -y 6 )+x 3 (x 3 *+0+ y 1 -y 2 +y 3 -y 7 )+x 4 (x 4 * - 5+ y 1 +2y 2 -y 3 -y 4 -y 8 )+x 5 (x 5 *+5+ y 1 +y 2 +2y 3 +5y 4 -y 9 ) - (-2y 1 -3y 2 -6y 3 +8y 4 )+]
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
7. f(x) =-16x 1 -x 2 +x 3 +5x 4 +5x 5 ->max
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
f(x) =16x 1 +x2 - x 3 -5x 4 -5x 5 ->m in
Дано: f ( x )=16 x 1 + x 2 - x 3 -5 x 4 -5 x 5 где
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
F (x, y )=16x 1 +x2 - x 3 -5x 4 -5x 5 ->m in
F *( x *, y*)= [x 1 (x 1 * - 16)+x 2 (x 2 * - 1)+x 3 (x 3 *+1)+x 4 (x 4 *+5)+x 5 (x 5 *+5)+(y 1 (2x 1 +x 2 +x 3 -10)+y 2 (-2x 1 -x 2 -x 3 +10)+y 3 (-2x 1 +3x 2 +x 4 -6)+y 4 (2x 1 -3x 2 -x 4 +6)+y 5 (2x 1 +4x 2 -x 5 -8)+y 6 (-2x 1 -4x 2 +x 5 +8) - x 1 y 7 -x 2 y 8 -x 3 y 9 -x 4 y 10 -x 5 y 11 )+] [x 1 (x 1 * - 16)+x 2 (x 2 * - 1)+x 3 (x 3 *+1)+x 4 (x 4 *+5)+x 5 (x 5 *+5)+x 1 (2y 1 -2y 2 -2y 3 +2y 4 +2y 5 -2y 6 -y 7 )+x 2 (y 1 -y 2 +3y 3 -3y 4 +4y 5 -4y 6 -y 8 )+x 3 (y 1 -y 2 -y 9 )+x 4 (y 3 -y 4 -y 10 )+x 5 (-y 5 +y 6 -y 11 ) - (-10y 1 +10y 2 -6y 3 +6y 4 -8y 5 +8y 6 )]= [x 1 (x 1 * - 16+2y 1 -2y 2 -2y 3 +2y 4 +2y 5 -2y 6 -y 7 )+x 2 (x 2 * - 1+ y 1 -y 2 +3y 3 -3y 4 +4y 5 -4y 6 -y 8 )+x 3 (x 3 *+1+ y 1 -y2-y 9 )+x 4 (x 4 *+5+ y 3 -y 4 -y 10 )+x 5 (x 5 *+5-y 5 +y 6 -y 11 ) - (-10y 1 +10y 2 -6y 3 +6y 4 -8y 5 +8y 6 )+]
Итак, двойственная задача имеет вид:
10y 1 -10y 2 +6y 3 -6y 4 +8y 5 -8y 6 ->max
8. f(x) =-x 1 +4x 2 +2x 4 -x 5 ->max
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
Дано: f ( x )= x 1 -4 x 2 -2 x 4 + x 5 где
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
F *( x *)= [x 1 (x 1 * - 1)+x 2 (x 2 *+4)+x 3 (x 3 *+0)+x 4 (x 4 *+2)+x 5 (x 5 * - 1)+(y 1 (x 1 -5x 2 +x 3 -5)+y 2 (-x 1 +5x 2 -x 3 +5)+y 3 (-x 1 +x 2 +x 4 -4)+y 4 (x 1 -x 2 -x 4 +4)+y 5 (x 1 +x 2 +x 5 -8)+y 6 (-x 1 -x 2 -x 5 +8) - x 1 y 7 -x 2 y 8 -x 3 y 9 -x 4 y 10 -x 5 y 11 )+max
9. f(x) =-5 x 1 + x 2 - x 3 -> max
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
F (x, y ) =5 x 1 - x 2 + x 3 -> min
Дано: f ( x )= 5 x 1 - x 2 + x 3 где
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
F ( x, y ) =5 x 1 - x 2 + x 3 -> min
F *( x *)= [x 1 (x 1 * - 5)+x 2 (x 2 *+1)+x 3 (x 3 * - 1)+(y 1 (3x 1 -x 2 -x 3 -4)+y 2 (-3x 1 +x 2 +x 3 +4)+y 3 (x 1 -x 2 +x 3 -x 4 -1)+y 4 (-x 1 +x 2 -x 3 +x 4 +1)+y 5 (2x 1 +x 2 +2x 3 +x 5 -7)+y6 (-2x 1 -x 2 -2x 3 -x 5 ) - x 1 y 7 -x 2 y 8 -x 3 y 9 -x 4 y 10 -x 5 y 11 )+]= [x 1 (x 1 * - 5)+x 2 (x 2 *+1)+x 3 (x 3 * - 1)+x 1 (3y 1 -3y 2 +y 3 -y 4 +2y 5 -2y 6 -y 7 )+x 2 (-y 1 +y 2 -y 3 +y 4 +y 5 -y 6 -y 8 )+x 3 (-y 1 +y 2 +y 3 -y 4 +2y 5 -2y 6 -y 9 )+x 4 (-y 3 +y 4 -y 10 )+x 5 (y 5 -y 6 -y 11 ) - (-4y 1 +4y 2 -y 3 +y 4 -7y 5 +7y 6 ) +]= [x 1 (x 1 * - 5+3y 1 -3y 2 +y 3 -y 4 +2y 5 -2y 6 -y 7 )+x 2 (x 2 *+1-y 1 +y 2 -y 3 +y 4 +y5-y 6 -y 8 )+x 3 (x 3 * - 1-y 1 +y 2 +y 3 -y 4 +2y 5 -2y 6 -y9)+x 4 (-y 3 +y 4 -y 10 )+x 5 (y5-y 6 -y 11 ) - (-4y 1 +4y 2 -y 3 +y 4 -7y 5 +7y 6 ) +]
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
4y 1 -4y 2 +y 3 -y 4 +7y 5 -7y 6 -> max
10. f(x) =28 x 1 +24 x 2 +20 x 3 -> max
Приведем задачу линейного программирования к общему виду
Целевую функцию , которая стремится к максимуму, поменяем на минимум, умножив функцию на (-1);
f(x) =-28 x 1 -24 x 2 -20 x 3 -> m in
Дано: f ( x )=-28 x 1 -24 x 2 -20 x 3 где
Выпишем двойственную задачу к общей задаче линейного программирования относительно стандартного возмущения
F ( x, y ) =-28 x 1 -24 x 2 -20 x 3 -> m in
F *( x *)= [x 1 (x 1 *+28)+x 2 (x 2 *+24)+x 3 (x 3 *+20)+ (y 1 (4x 1 +2x 2 +10x 3 -42)+y 2 (6x 1 +2x 2 +8x 3 -12)+y 3 (-6x 1 -2x 2 -8x 3 +12)+y 4 (-4x 1 -2x 2 -18x 3 +25) - x 1 y 5 -x 2 y 6 -x 3 y 7 )+]= [x 1 (x 1 *+28+4y 1 +6y 2 -6y 3 -4y 4 -y 5 )+x 2 (x 2 *+24+2y 1 +2y 2 -2y 3 -2y 4 -y 6 )+x 3 (x 3 *+20+10y 1 +8y 2 -8y 3 -18y 4 -y 7 ) - (-42y 1 -12y 2 +12y 3 +25y 4 ) +]
Таким образом, получаем двойственную задачу:
Итак, двойственная задача имеет вид:
Двойственные задачи в линейном программировании. Симметричные и несимметричные двойственные задачи. Связь исходной и двойственной задач. Анализ моделируемой ситуации (моделируемого объекта). Реализация двойственности на 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
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Двойственные задачи линейного программирования дипломная работа. Математика.
Учебное Пособие На Тему Бесіди З Техніки Безпеки
Дипломная работа по теме Проблемы перевода единиц просторечия английского языка
Реферат: Othello Essay Research Paper In his play
Реферат: Экономическое обоснование эффективности внедрения системы автоматизации на промышленном предпр
Курсовая Работа Коленчатый Вал
Эссе Для Чего Нужна Наука
Реферат: Кроткая
Итоговая Контрольная Работа По Английскому
Реферат: Теория и практика нацизма в 30-е годы в Германии
Курсовая работа по теме Холодильник
Реферат Гост Введение
Эссе О Правах Человека
Реферат по теме Влияние анестезии на функцию печени
Курс Лекций На Тему Зарубежная Литература 18 Века
Физическая Культура И Долголетие Реферат Кратко
Тетрадь Для Практических И Самостоятельных Работ
Сочинение Егэ По Русскому Сколько Баллов
Реферат по теме О возможностях психологических исследований в сети Интернет
Эссе 4 Сынып
Курсовая Работа Функция Управления
Бухгалтерский учет основного капитала предприятия - Бухгалтерский учет и аудит курсовая работа
Светить всегда, светить везде! Владимир Маяковский - Литература презентация
Правовые системы современности - Государство и право курсовая работа