Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Реферат: Двойственность линейного программирования

Название: Двойственность линейного программирования
Раздел: Рефераты по математике
Тип: реферат Добавлен 00:30:33 08 июня 2011 Похожие работы
Просмотров: 1968 Комментариев: 22 Оценило: 4 человек Средний балл: 4.5 Оценка: неизвестно     Скачать

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

ОРЕНБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ МЕНЕДЖМЕНТА

Реферат

по дисциплине «Математические методы принятия управленческих решений»

на тему: «Двойственность линейного программирования»

Выполнила студентка

очной формы обучения

специальности «Менеджмент организации»

третьего курса 32 группы

Шумакова Ю. А.

Проверила

Кочетова Л.А.

Оренбург

2009


Содержание

Введение………………………………………………………………..…….3

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

моделей……………………………………………………………………….4

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

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

4.Экономический анализ задач с использованием теории двойственности……………………………………………………………….….12

5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов…………………………………………………………………………..14

Заключение…………………………………………………...……………..18

Библиографический список……………………………………………......19


Введение

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

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

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


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

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

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 ,

xj ≥0 , j = 1,n.

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

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

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

- переменные 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.

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

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.

x1 ≥0 , x2 ≥0.

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

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

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

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

-2y1 + y2 + y3 = 1,

y1 – 2y2 + y3 = -1.

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

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

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

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

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

y2 + y3 = 1,

– 2y2 + y3 = -1.

Откуда 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-й теореме двойственности второе и третье неравенства исходной задачи обращаются в равенства:

x1 - 2x2 = 2 ,

x1 + x2 = 5.

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

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

S(y) = 2y1 + 2y2 + 5y3 → mах

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

-2y1 + y2 + y3 – у4 = 1,

y1 – 2y2 + y3 – у5 = 1,

bi БП У1 У2 У3 У4 У5 cj
-2 1 1 -1 0 1
У5 1 2 -1 0 1 1
5 У3 -2 1 1 -1 0 1
0 У5 -3 3 0 -1 1 2
∆j -12 3 0 -5 0 5
5 У3 -1 0 1 -2/3 -1/3 1/3
2 У2 -1 1 0 -1/3 1/3 2/3
∆j 9 0 0 -4 -1 3

yj ≥ 0, i = 1,5.

Из таблицы следует, что Yопт = (0, 2/3, 1/3), S(y)min = 3.

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

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

Решение другой задачи найдем по соответствию между переменными:

Основные

переменные

Балансовые

переменные

Исходная задача Х1 Х2 Х3 Х4 Х5
двойственная У4 У5 у1 У2 У3
Балансовые переменные Основные переменные

Значение хj определяем по последней симплексной таблице в строке ∆iв соответствующем столбце, причем значения хj берем по модулю:

Х1 → У4, Х1 = │∆4│= │-4│=4,

Х2 → У5, Х2 = │∆5│= │-1│=1.

Таким образом, решение исходной задачи:

Хопт = (4,1), при этом L(x)max = 3.

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

Уопт = С*А ,

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

Решим симплексным методом исходную задачу вида

L (x) = x1 - x2 → max

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

-2x1 + x2 + x3 = 2,

x1 - 2x2 + x4 =2,

x1 + x2 + x5 = 5,

x1 ≥0 , j = 1,5.

Из таблицы (см. ниже) следует, что Хопт = (4,1), L(x)max = 3. матрицы записываются в виде

С = (1 -1 0)1×3 , -2 1 1

А = 1 -2 0 ,

1 1 0 3×3

тогда

0 1/3 2/3

А = 0 -1/3 1/3 ,

1 1 1

0 1/3 2/3

Уопт = С*А = (1 -1 0) × 0 -1/3 1/3 = (0 2/3 1/3).

1 1 1

ci БП 1 -1 0 0 0 L (x)
х1 х2 х3 х4 х5 bi
0 х3 -2 1 1 0 0 2
0 Х4 1 -2 0 1 0 2
0 Х5 1 1 0 0 1 5
∆j -1 1 0 0 0 0
0 х3 0 -3 1 2 0 6
1 Х1 1 -2 0 1 0 2
0 Х5 0 3 0 -1 1 3
∆j 0 -1 0 1 0 2
0 х3 0 0 1 1 1 9
1 Х1 1 0 0 1/3 2/3 4
-1 Х2 0 1 0 -1/3 1/3 1
∆j 0 0 0 2/3 1/3 3

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

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

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

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

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

L (x) = 3x1 + x2 + 3x3 + x4 → min S(y) = 9y1 + 6y2 → mах

x1 - 2x2 + 3x3 - x4 = 9│ y1 2y1 + y2 ≤ 3 │x1

x1 + x2 - 6x3 - x4 = 6 │ y2 -2y1 + y2 ≤ 1 │x2

xj ≥0 , j = 1,4. 3y1 - 6y2 ≤ 3 │x3

-2y1 - y2 ≤ 1 │x4

y1, y2 - произвольные по знаку.

Решив двойственную задачу графическим методом, получим

Yопт = (1/2, 2), при этом S(y)max = 33/2.

По 1-й теореме двойственности L(x)min = S(y)mах = 33/2.

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

2*1/2 +2 ≤ 3, 3 = 3,

-2 *1/2 + 2 ≤ 1, 1 = 1,

3*1/2 – 6*2 ≤ 3, -21/2 < 3 → х3 = 0,

-2*1/2 – 2 ≤ 1,-3 < 1 → х4 = 0.

Так как х3 = х4 = 0 , то система ограничений исходной задачи примет вид

2x1 - 2x2 = 9,

x1 +x2 =6.

Решая данную систему, получим

Хопт = (21/4, 3/4, 0,0), при этом L(x)min = 33/2.

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

Пусть решение исходной задачи

Xопт = (21/4,3/4,0,0), при этом L(x)min = 33/2.

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

Уопт = С*А ,

где

С = (3,1), А = 2 -2 , А = 1/4 1/2 ,

1 1 -1/4 1/2

Yопт = (3 1) * 1/4 1/2 = (1/2 2).

-1/4 1/2

Таким образом, Yопт = (1/2, 2), при этом S(y)mах = 33/2.

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

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

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

L (x) = x1 - 6x2 - x3 → mах S(y) = 3y1 + 4y2 → min

x1 + 3x2 + 3x3 = 3│ y1 y1 + 2y2 ≥ 1 │x1

2x1 + 3x3 ≤4 │ y2 3y1 ≥ -6 │x2

xj ≥0 , j = 1,3. 3y1 + 3y2 ≥ -1 │x3

y1 – произвольная по знаку, y2 ≥0.

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

Хопт = (1,0,2/3), при этом L(x)max = 1/3.

По 1-й теореме двойственности

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

Так как х1 > 0, х3 > 0, то по 2-й теореме двойственности первое и третье ограничения двойственной задачи выполняются в виде равенств:

y1 + 2y2 = 1,

3y1 + 3y2 = -1,

Откуда y1 = -5/3, y2 = 4/3, т.е. Yопт = (-5/3, 4/3).

4. Экономический анализ задач с использованием теории двойственности

Рассмотрим задачу оптимального использования ресурсов, запишем ее математическую модель

L(x) = ∑ сjxj→ mах

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

∑ aijxj ≤ bi │y,

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

Двойственная задача имеет вид

S(y) = ∑ biyi→ min

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

∑ aijуj ≥ cj, уi≥ 0, i = 1,m.

ТЕОРЕМА 3. Значения переменных уi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов системы ограничений исходной задачи на оптимальное значение ее целевой функции, т.е. уi= ðLi/ ðbi/

Примем ðLi ≈ ∆ Li, ðbi≈ ∆bi, тогда ∆ Li≈ уi * ∆bi.

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

Если уi мало, то значительному увеличению i –го ресурса будет соответствовать небольшое увеличение оптимального дохода и ценность ресурса невелика.

Если уi = 0, то при увеличении i –го ресурса оптимальный доход остается неизменным и ценность этого ресурса равна нулю. В самом деле, сырье, запасы которого превышают потребности в нем, не представляют ценности для производства и его оценку можно принять за нуль.

Если уi велико, то незначительному увеличению i –го ресурса будет соответствовать существенное увеличение оптимального дохода и ценность ресурса высока. Уменьшение ресурса ведет к существенному сокращению выпуска продукции.

Переменную уi считают некоторой характеристикой ценности i –го ресурса. В частности, при увеличении i –го ресурса на единицу оптимальный доход возрастает на уi, что позволяет рассматривать уi как «условную цену», оценку единицы i –го ресурса , объективно обусловленную оценку.

Так как уi представляет частную производную от оптимального дохода по i – му ресурсу, то уi характеризует скорость изменения оптимального дохода при изменении i –го ресурса.

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

bi = min (xj / dij ) , bi = max (xj / dij ) ,

где xj – значение переменной в оптимальном решении; dij– элементы матрицы ( dij ) = А , обратной к матрице базиса оптимального решения, для которой А = ( аij )m×n .

5. Стратегическое планирование выпуска изделий с учетом имеющихся ресурсов

Фирма выпускает три вида изделий, располагая при этом сырьем 4 типов : А, Б, В, Г соответственно в количествах 18, 16, 8 и 6 т. Нормы затрат каждого типа сырья на единицу изделия первого вида составляют соответственно 1, 2, 1, 0, второго вида – 2, 1, 1, 1 и третьего вида 1, 1, 0, 1. Прибыль от реализации единицы изделия первого вида = 3 усл. ед., второго =4 усл. ед., третьего = 2 усл. ед.

Требуется:

1) составить план производства трех видов, максимизирующих прибыль;

2) определить дефицитность сырья;

3) установить размеры максимальной прибыли при изменении сырья А на 6 т, Б – на 3 т, В – на 2 т, Г – на 2 т. Оценить раздельное влияние этих изменений и суммарное их влияние на прибыль;

4) оценить целесообразность введения в план производства фирмы нового вида изделий (четвертого), нормы затрат на единицу которого соответственно равны 1, 2, 2, 0, а прибыль составляет 15 усл. ед.

Решение. 1. Обозначим через Х = ( х1, х2, х3) план производства изделий трех видов, тогда математическая модель задачи примет вид

L (x) = 3x1 + 4x2 + 2x3 → max

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

x1 + 2x2 + x3 ≤ 18,

2x1 + x2 + x3 ≤ 16 ,

x1 + x2 ≤ 8,

x2 + x3 ≤ 6,

xj ≥0 , j = 1,3.

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

сi БП х1 х2 х3 х4 х5 Х6 Х7 bi
0 х4 0 0 0 1 0 -1 -1 4
2 х3 0 0 1 0 1/2 -1 ½ 3
3 х1 1 0 0 0 ½ 0 -1/2 5
4 х2 0 1 0 0 -1/2 1 ½ 3
∆j 0 0 0 0 1/2 2 3/2 33

Из таблицы следует

Хопт = (5,3,3,4,0,0,0), при этом L(x)max = 33 усл. ед.

Согласно теоремам двойственности

Уопт = (0,1/2,2,3/2,0,0,0), при этом S(y)min = 33 усл. ед.

2. Наиболее дефицитным является сырье типа В, для которого двойственная оценка у3 = 2. Менее дефицитным является сырье вида Б, для которого у2 = ½. Совсем не дефицитным является сырье А (у1 =0).

Для определения интервала устойчивости оценок найдем обратную матрицу для матрицы коэффициентов при базисных переменных в оптимальном решении системы ограничений. Базисными переменными в оптимальном решении являются х1, х2, х3, х4. Матрица коэффициентов при этих переменных в системе ограничений примет вид

1 2 1 1

А = (аij) = 2 1 1 0 .

1 1 0 0

0 1 1 0

Тогда обратная матрица для матрицы А следующая:

0 1/2 0 -1/2

А = 0 -1/2 1 1/2 .

0 1/2 -1 1/2

1 0 -1 -1

Найдем интервал устойчивости оценок по видам сырья:

∆b1 = min (xоптj/ d1j ) = 3 / (1/2) = 6,

∆b1 = min (xоптj/ d1j ) = 4 / (-1/2) = 8.

Интервал устойчивости оценок по отношению к первому ограничению:

(b1 - b1; b1+ b1) = (18 – 6; 18 + 8) = (12; 26).

Аналогично определим интервалы устойчивости оценок по отношению к ограничениям остальных видов сырья:

∆b2 = min ( 3/1; 4/(1/2) ) = 3, ∆b2 = │3/ (-1/2) │=6,

∆b3 = min ( 3/(1/2); 4/(1/2) ) = 6, ∆b3 = │3/ (-1) │=3,

∆b4 =5/1 = 5, ∆b4 = max│3/ (-1); 4/(-1) │=3.

Интервалы устойчивости оценок по отношению ко второму ограничению:

(16 – 3; 16 + 6) = (13;22),

к третьему ограничению:

(8 – 6; 8 + 3) = (2;11),

к четвертому ограничению:

(6 – 5; 6 + 3) = (1;9).

3. Изменения сырья согласно условиям задачи на +6, -3, +2, +2 т приводят к ограничению запаса сырья до 24, 13, 10, 8 т соответственно. Поскольку эти изменения находятся в пределах устойчивости оценок, на что указывают интервалы, то раздельное их влияние на прибыль определяется по формуле

Li = yоптi* bi,

тогда

L1 max = yопт1 * b1 = 0*6 = 0,

L2 max = yопт2 * b2 = 1/2*(-3) = -3/2,

L3max = yопт3 * b3 = 2*2 = 4 ,

L 4max = yопт4 * b4 = 3/2*2 = 3.

Суммарное влияние на прибыль:

L max = L1 max + L2 max + L3 max + L4 max = 0 – 3/2 +4 +3 = 11/2 усл. ед.

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

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

∆4 = ∑ aijyоптi – c4 = 1*0 + 2*1/2 +2*2 + 0*3/2 -15 = -10 < 0.

Так как прибыль превышает затраты, то введение в план производства четвертого вида изделий целесообразно.

Заключение

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

Правила получения двойственной задачи из задачи исходной.

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

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

3. В исходной ЗЛП все функциональные ограничения - неравенства вида «≤», а в задаче, двойственной ей, - неравенства вида «≥».

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

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

6. Условие неотрицательности переменных сохраняется в обеих задачах.

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


Библиографический список

1. Белолипецкий В. М. Математическое моделирование в задачах. / В.М. Белолипецкий, Ю.И. Шокин. – М. : Финансы и статистика, 2002.- 774 с.

2. Красс М. С. Основы математики и ее приложения в экономическом образовании: Учебник. - 5-е изд., испр. и доп. / М.С. Красс, Б.П. Чупрынов. – М. : Дело, 2006. – 720 с.

3. Солодовников А. С. Математика в экономике. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – М. : Изд–во МГУ, 1999. – 591 с.

4. Черемных Ю. Н. Математические методы в экономике. 2 - изд. / Ю.Н. Черемных. – М. : Дело и сервис, 2001. – 657 с.

5. http://lib.mexmat.ru

6. http://slovari.yandex.ru

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита14:19:44 04 ноября 2021
.
.14:19:43 04 ноября 2021
.
.14:19:41 04 ноября 2021
.
.14:19:40 04 ноября 2021
.
.14:19:39 04 ноября 2021

Смотреть все комментарии (22)
Работы, похожие на Реферат: Двойственность линейного программирования

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(287530)
Комментарии (4159)
Copyright © 2005-2021 HEKIMA.RU [email protected] реклама на сайте