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

Обновлено: 04.07.2024

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

Содержание

Прикрепленные файлы: 1 файл

ГОТОВАЯ_КУРСОВАЯ_ИВАНОВ.docx

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

Двойственность в линейном программировании………………………….. 6
Несимметричные двойственные задачи……………………………………. 8
Двойственный симплексный метод………………………………………… 11

Задача №1…………………………………………………………………….. 13
Задача №2……………………………………………………………………. 17
Задача №3…………………………………………………………………….. 23
Задача №4…………………………………………………………………….. 23

Позвольте задать несколько философский вопрос: какое место в современном мире занимают математические методы?

Математика стала "языком" и методом соответствующей предметной науки. И этому не приходится удивляться, поскольку "область применения математического метода не ограничена: все виды движения материи могут изучаться математически" (А.Н. Колмогоров). И то, что общество материально поддерживает развитие такой абстрактной науки как математика, свидетельствует о понимании им роли математических методов в прогрессе наук и общества в целом.

Применение в работе математических методов позволяет существенно сократить время расчетов и принятия решений, а также стать профессионалом в короткие сроки.

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

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

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

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

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

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

Рубрика	Экономико-математическое моделирование
Вид	контрольная работа
Язык	русский
Дата добавления	03.07.2011
Размер файла	54,2 K

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

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ФАКУЛЬТЕТ НЕПРЕРЫВНОГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

1. Классификация переменных и ограничений по их роли в моделируемом процессе

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

2.1 Понятие двойственной задачи ЛП

2.2 Общая схема построения двойственной задачи

2.3 Пример построения двойственной задачи

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

Список использованной литературы

1. Классификация переменных и ограничений по их роли в моделируемом процессе

Переменные модели подразделяются на: Внешние (экзогенные, входные, как правило их значение известно), Внутренние (эндогенные, их значение требуется рассчитать по модели).

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

Задания по объему производства

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

Балансовые соотношения между переменными

Специальные условия для защиты интересов отдельных предприятий

Требование типизации и стандартизации технического оснащения технических процессов (условия связности)

Рисунок 1. Типы ограничений

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

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

2.1 Понятие двойственной задачи ЛП

Пусть задана каноническая задача ЛП

Если целевая функция f(x) = cx достигает максимального значения на множестве D, то обоснованным представляется вопрос о том, каким образом можно построить верхнюю оценку для нее. Очевидно, что если через и обозначить некоторый m-мерный вектор, то

cx = cx+u(-Ax+b) = (c-uA)x+bu

Предположим, что и можно выбрать таким образом, чтобы иА ? с. Тогда при любых х?0 справедливо неравенство

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

Если задана каноническая задача ЛП

называется двойственной по отношению к ней. Соответственно, задача (D, f) no отношению к (D*, f*) называется прямой (или исходной).

2.2 Общая схема построения двойственной задачи

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

Если задана общая задача ЛП

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

то двойственной по отношению к ней называется общая задача ЛП

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

Как следует из приведенной схемы при переходе от прямой задачи ЛП к двойственной:

1. Тип оптимума меняется на противоположный, т. е. максимум на минимум, и наоборот.

2. Вектор коэффициентов целевой функции c и столбец ограничений b меняются местами.

3. Матрица ограничений задачи А транспонируется.

4. Множество индексов переменных, на которые наложено условие неотрицательности в прямой задаче (например, х_j?0 или u_i?0), определяют номера ограничений, имеющих форму неравенств в двойственной задаче (а j и?с_j или a_ix?b_i).

5. Множество номеров ограничений, имеющих форму неравенств в прямой задаче (например, a_ix?b_i или а j и?с_j), определяют множество индексов переменных, на которые накладывается условие неотрицательности, в двойственной задаче (u_i?0 или х_j?0).

Из приведенного определения вытекает важное свойство -- симметричность отношения двойственности, т. е. задача, двойственная по отношению к двойственной, совпадает с прямой (исходной) задачей:

Тем самым имеет смысл говорить о паре взаимно двойственных задач.

В матричной форме пара двойственных общих задач линейного программирования может быть кратко записана как:

2.3 Пример построения двойственной задачи

Рассмотрим процесс построения двойственной задачи на конкретном примере. Пусть задана ОЗЛП

тогда двойственной к ней будет задача

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

1. Обработка деталей А и В может производиться на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль при реализации детали А - 10 руб, детали В - 16 руб. Определить производственную программу, максимизирующую прибыль при условии: деталей А произвести не менее 300 ед., а деталей В не более 200 ед.

Время работы станка, ч

x_{1 -} количество деталей А

x_{2 -} количество деталей В

Оптимальный план выпуска продукции

Время работы станка, ч

Вывод: При производстве деталей А не менее 300 ед., а В - не более 200 ед. прибыль будет равна 7200 руб.

2. Площадь пашни в сельскохозяйственной организации составляет 3000 га, сенокосов - 1000 га, пастбищ -700 га. В хозяйстве возделываются пшеница, озимая рожь, овес, турнепс и картофель, животноводческий подкомплекс включает коров, молодняк КРС и овец. Для содержания одной коровы требуется 1,9 га пашни, 0,5 га сенокосов и 0,1 га пастбищ, молодняка КРС - 1 га пашни, 0,5 га сенокосов, 0,1 га пастбищ, овец - 0,3 га пашни, 0,09 га сенокосов, 0,05 га пастбищ. При необходимости не более 700 га пастбищ может быть трансформировано в пашню. Площадь зерновых должна быть не менее, чем в 7 раз больше площади пропашных. Хозяйство располагает трудовыми ресурсами в размере 200 тыс. чел.-ч. Затраты труда составляют на 1 га посевов пшеницы - 3 чел.-ч., озимой ржи - 2, овса - 2,1, турнепса - 65, картофеля - 65 чел.-ч., а на одну голову молодняка КРС - 95, корову - 205, голову овец - 8 чел.-ч. Объем производства молока в хозяйстве должен быть не менее 5000 ц, мяса - не менее 500 ц, шерсти -5 ц. Продуктивность животных на одну голову: овцы - 0,3 ц мяса, 0,035 ц шерсти, коров - 23 ц молока, молодняка КРС - 1,5 ц мяса. Поголовье молодняка КРС в структуре стада КРС должно быть не менее 50%. Прибыль от реализации продукции составляет с 1 га пшеницы -- 3, озимой ржи -- 2,6, овса -- 2,6, турнепса -- 4,5, картофеля - 6 тыс. руб., с одной головы овец - 0,9, коров - 3, молодняка КРС - 2,5 тыс. руб. Требуется разработать экономико-математическую модель производственно-отраслевой структуры организации, математическую запись модели привести к табличному виду, решить модель в ЭТ Excel. Критерий оптимальности - максимум прибыли.

Системы переменных и ограничений:

I. Основные ограничения по использованию ресурсов организации:

1. по использованию пашней, га:

2. по использованию сенокосов, га:

3. по использованию пастбищ, га:

4. по использованию трудовых ресурсов, ч-часы:

II. Дополнительные ограничения:

5. по объему трансформации пастбищ в пашню:

III. Основные ограничения по предельным размерам в структуре и соотношению посевных площадей с/х культур:

6. по соотношению площади под пропашными культурами:

IV. Основные ограничения по численности поголовья животных, их структура и соотношение:

7. по структуре стада КРС, гол.:

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

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

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

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

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

Различают симметричные, несимметричные и смешанные двойственные задачи.

1. Виды двойственных задач и составление их математических моделей

Симметричные двойственные задачи

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn → max

a11x1 + a12x2 + … + a1nxn ≤ b1 │ y1 ,

a21x1 + a22x2 + … + a2nxn ≤ b2 │ y2 ,

am1x1 + am2x2 + … + amnxn ≤ bm │ ym ,

xj ≥0 , j = 1,n , i = 1,m.

Задача дана в неканоническом виде. Составим математическую модель двойственной задачи, для этого:

- каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную yi ;

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

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

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

Математическая модель двойственной задачи имеет вид

S(y) = b1y1 + b2y2 +…+ bmym → min

a11y1 + a12y2 + … + am1ym ≤ c1 ,

a12y1 + a21y2 + … + am2ym ≤ c2 ,

a1ny1 + a2ny2 + … + amnym ≤ cn ,

yj ≥0 , i = 1,m , j = 1,n.

Несимметричные двойственные задачи

Дана исходная задача

L (x) = c1x1 + c2x2 +…+ cnxn → max

a11x1 + a12x2 + … + a1nxn = b1 │ y1 ,

a21x1 + a22x2 + … + a2nxn = b2 │ y2 ,

am1x1 + am2x2 + … + amnxn = bm │ ym ,

Задача дана в каноническом виде. Составим математическую модель двойственной задачи.

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

- ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства ≥, если максимум, то ≤ ;

- переменные yi - произвольные по знаку.

Математическая модель двойственной задачи имеет вид

S(y) = b1y1 + b2y2 +…+ bmym → min

a11y1 + a21y2 + … + am1ym ≥ c1 ,

a12y1 + a22y2 + … + am2ym ≥ c2 ,

a1ny1 + a2ny2 + … + amnxn ≥ cn ,

yj ≥0 , i = 1,m , j = 1,n.

yi – произвольные по знаку, i = 1,m.

Смешанные двойственные задачи

Математическая модель исходной задачи имеет условия симметричных и несимметричных задач. При составлении двойственной задачи необходимо выполнять правила симметричных и несимметричных задач.

2. Основные теоремы двойственности

ТЕОРЕМА 1. Если одна из двойственных задач имеет оптимальное решение, то другая также имеет оптимальное решение, причем для любых оптимальных решений X и Y выполняется равенство

Если одна из двойственных задач неразрешима ввиду того, что

L(x)max → ∞ (или S(y)min → - ∞), то другая задача не имеет допустимых решений.

ТЕОРЕМА 2. Для оптимальности допустимых решений X и Y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений

Xопт j ( ∑aijyопт i - cj ) = 0,

yопт i ( ∑aijxопт j - bi ) = 0.

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

3. Решение двойственных задач

Решение симметричных задач

Рассмотрим решение задач с использованием теорем двойственности.

Исходная задача Двойственная задача

L (x) = x1 - x2 → max S(y) = 2y1 + 2y2 + 5y3 → min

при ограничениях: при ограничениях:

-2x1 + x2 ≤ 2 │ y1 -2y1 + y2 + y3 ≥ 1 │x1

x1 - 2x2 ≤ 2 │ y2 y1 – 2y2 + y3 ≥ -1 │x2

x1 + x2 ≤ 5 │ y3 yi ≥0, I = 1,3.

Решим исходную задачу графическим методом, получим Хопт = (4,1), при этом L(x)max = 3.

На основании 1-й теоремы двойственности

L(x)max = S(y)min = 3.

Так как x1, x2 > 0, то по 2-й теореме двойственности систему ограничений можно записать в виде равенств:

Подставим Хопт в систему ограничений исходной задачи:

-2*4 + 1 ≤ 2, 9 у1 = 0,

4 – 2*1 ≤ 2, 2 = 2 ═> у2 > 0,

4 + 1 ≤ 5, 5 = 5 ═> у3 > 0.

Тогда система ограничений двойственной задачи примет вид

Откуда Yопт = (0, 2/3, 1/3), при этом S(y)min = 3.

Пусть дано решение двойственной задачи Yопт = (0, 2/3, 1/3), S(y)min = 3, найдем решение исходной.

По 1-й теореме двойственности L(x)max = S(y)min = 3. Так как y2 , y3 > 0, то по 2-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

Откуда Хопт = (4,1), при этом L(x)max = 3.

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

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

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

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

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

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

Основные формы задачи ЛП.

Различают три основные формы задач линейного программирование в зависимости от наличия ограничений разного типа.

Стандартная задача ЛП.

или, в матричной записи,

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

Основные вычислительные схемы решения задач ЛП разработаны именно для канонической задачи.

Общая задача ЛП.

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

. Ясно, что стандартная задача получается как частный случай общей при , называется решением задачи, или оптимальным планом. Максимальное значение (1)

или, в матричной записи,

где задачи (1). Матрица ограничений в (3) — транспортированная матрица . Вектор правой части ограничений в (3) служит вектором коэффициентов максимизируемой линейной форме в (1), при этом знаки неравенств меняются на равенство. Наоборот, в качестве целевой функции в (3) выступает линейная форма, коэффициентами которой задаются вектором правой части ограничений задачи (1), при этом максимизация меняется на минимизацию. На двойственные переменные

Читайте также: