Контрольная: Теория двойственности в задачах линейного программирования - текст контрольной. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Контрольная

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

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Контрольная работа
Язык контрольной: Русский
Дата добавления:   
 
Скачать
Архив Zip, 84 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной работы

Узнайте стоимость написания уникальной работы

6 Лабораторная работа № 3 Телешовой Елизаветы , гр . 726, Теория двойств енности в задачах линейного программирования. Задача : Для изготовления определенного сплава из свинца , цинка и олова используется сырье из тех же металлов , отличающееся составом и стоимостью. Сырье Содержание в процентах Компоненты 1 2 3 4 5 Свинец 10 10 40 60 70 Цинк 10 30 50 30 20 Олово 80 60 10 10 10 Стоимость , у . е. 4 4,5 5,8 6 7,5 Определить , сколько нужно взять сырья каждого вида , чтобы изготовить с минимальной себестоимостью сплав , содержащий олова не более 30%, цинка не менее 10%, свинца не более 40%. Решение задачи : Пусть х i – доля сырья i -го вида в единице полученного сплава . Тогда функция цели (себестоимость единицы сплава в у.е .) запишется следующим образом : . Система ограничений будет иметь вид : (1). Запишем систему в каноническом виде : (2). Решим поставленную задачу методом искусственного базиса . Для этого составим расширенную задачу : (3). Составим вспомогательную целевую функцию : . Вырази м ее через переменные , не входящие в начальный базис . Выражая из первого ограничения , а из третьего получаем : ; ; Тогда : . Запишем начальную симплекс-таблицу : 4 4,5 5,8 6 7,5 0 0 0 M M С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 В M X 9 1 1 1 1 1 0 0 0 1 0 1 0 X 6 0,8 0,6 0,1 0,1 0,1 1 0 0 0 0 0,3 M X 10 0,1 0,3 0,5 0,3 0,2 0 -1 0 0 1 0,1 0 X 8 0,1 0,1 0,4 0,6 0,7 0 0 1 0 0 0,4 F -4 -4,5 -5,8 -6 -7,5 0 0 0 0 0 0 F M 1,1 1,3 1,5 1,3 1,2 0 -1 0 0 0 1,1 Оптимальная симплекс-таблица будет иметь вид : 4 4,5 5,8 6 7,5 0 0 0 M M С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 В 4,5 X 2 1,4 1 0 0 0 2 0 0 -0,2 0 0,4 0 X 8 0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12 5,8 X 3 -0,4 0 1 1 1 -2 0 0 1,2 0 0,6 0 X 7 0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32 F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28 F M 0 0 0 0 0 0 0 0 -1 -1 0 Полученное решение буд ет оптимальным , поскольку все оценки неположительные . Запишем оптимальное решение : и оптимальное значение целевой функции : . Экономически полученное решение интерпретируется следующим образом : для получения единицы сплава минимальной себестоимости необходимо взять 40% сырья № 2 и 60% сырья № 3. При этом сплав содержи т ровно 30% олова , более 20% (точнее , 42%) цинка и менее 40% (28%) свинца . Минимальная себестоимость единицы сплава составляет 5,28 у.е. Математическая модель и экономический смысл двойственной задачи. Задача , двойственная к исходной , строится следующим об разом : 1) Исходная задача – на минимум , следовательно , двойственная задача – на максимум. 2) Матрица коэффициентов системы ограничений будет представлять собой транспонированную матрицу соответствующих коэффициентов исходной задачи . При этом все ограничени я должны быть одного типа , например "больше или равно ". Поэтому преобразуем второе и четвертое ограничения к типу "больше или равно ", умножив их на – 1, затем транспонируем полученную матрицу : => . 3) Число переменных в двойственной задаче равно числу ограничений в исходной , т.е . 4, и наоборот , число ограничений в двойственной задаче равно числу переменных в исходной , т.е . 5. Переменная двойственной задачи соответствует первому ограничению исходной задачи , переменная – второму , – третьему , а – четвёртому. 4) Коэффициентами при переменных , , и в целевой функции двойственной задачи являются свободные члены ограничений исходной задачи (все ограничения одного типа ), т.е . вектор , а правыми частями ограничений дв ойственной задачи являются коэффициенты целевой функции исходной задачи , т.е . вектор . 5) Т.к . все переменные исходной задачи неотрицательны , то все ограничени я двойственной задачи будут неравенствами типа « » (поскольку двойственная задача на максимум ). Поскольку первое условие исходной задачи представляет собой равенство , а остальные три – неравенства , то может принимать любые значения , а , и – только положительные. Таким образом , математическая модель двойственной задачи следующая : . (4). Проанализируем теперь экономический смысл двойственной задачи . Для этого сначала рассмотрим экономический смысл переменных , , и . Из ограничений видно , что величина имеет размерность [у.е ./ед . сплава ], величина – [у.е ./ед . олова ], – [у.е ./ед . цинка ], а – [у.е ./ед . свинца ]. Указать экономический смысл переменной не представляется возможным в силу условия задачи . Что касается экономического смысла переменных и , то в системе (1) они соответствует второму и четвёртому ограничениям , отражающим относительную избыточность ресурсов "олово " и "свин ец ", т.е . они могут быть рассмотрены как условный убыток для держателя этого ресурса , или цену , выплачиваемую его приобретателю . Таким образом , олово и свинец выступают в данной задаче в качестве антиблага , что экономически также достаточно абсурдно . Экон о мический смысл переменной , отражающей ограниченность ресурса "цинк ", виден явно : она представляет собой двойственную оценку , или условную цену этого ресурса. Таким образом , экономический смысл ограничений заключается в следующем . Пусть , рассматриваемая фирма вместо того , чтобы производить сплав из указанных пяти видов сырья , решила , приобретя у некой другой фирмы цинк по цене и взяв у нее некоторое количество олова с доплатой и свинца с доплатой , производить свой сплав из этих компонентов с учетом некоего параметра . Стоимост ь получаемых компонент по каждому виду сырья в этом случае не должна превосходить стоимость единицы сырья. Целевая функция данной двойственной задачи экономически интерпретируется как максимальная прибыль фирмы-поставщика ресурсов. Решение двойственной за дачи. 1. Решение с помощью IBLP . Введя задачу в программу , получаем следующее оптимальное решение : 1 -0,3 0,1 -0,4 0 0 0 0 0 С в Б.П. Y 1 Y 2 Y 3 Y 4 Y 5 Y 6 Y 7 Y 8 Y 9 В 1 Y 1 1 0 0,54 -0,46 0 -0,2 1,2 0 0 6,06 -0,3 Y 2 0 1 0,4 -0,6 0 -2 2 0 0 2,6 0 Y 5 0 0 -0,12 -0,12 1 -1,4 0,4 0 0 0,02 0 Y 8 0 0 -0,2 -0,2 0 0 -1 1 0 0,2 0 Y 9 0 0 -0,3 -0,3 0 0 -1 0 1 1,7 T 0 0 0,32 0,12 0 0,4 0,6 0 0 5,28 . Значение целевой функции при этом равно 5,28. 2. Решение по второй теореме двойственности. Согласно второй теореме двойственности , планы и начальной и двойственной задачи соответственно являются оптимальными тогда и только тогда , когда выпол няются соотношения : (5) (6) Покомпонентно для наших задач э ти соотношения записываются следующим образом : (5). (6) Из системы (5) видно , что во втором и третьем уравнениях в скобках получается ноль , поскольку и положительны , . Из системы (6) получаем , что , поскольку в третьем и четвёртом уравнениях в скобках получаются положительные числа. Из первого и третьего уравнений системы (5) имеем : откуда Таким образом , . 3. Решение с помощью симплекс-таблицы исходной задачи. Запишем еще раз оптимальную симплекс-таблицу исходной задачи : 4 4,5 5,8 6 7,5 0 0 0 M M С в Б.П. X 1 X 2 X 3 X 4 X 5 X 6 X 7 X 8 X 9 X 10 В 4,5 X 2 1,4 1 0 0 0 2 0 0 -0,2 0 0,4 0 X 8 0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12 5,8 X 3 -0,4 0 1 1 1 -2 0 0 1,2 0 0,6 0 X 7 0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32 F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28 F M 0 0 0 0 0 0 0 0 -1 -1 0 Из теории известно , что справедливы следующие формулы : (7); (8). В системе ограничений (2) исходной задачи переменной соответствует первое ограничение , содержащее базисную переменную , пе ременной – второе , содержащее базисную переменную , переменн ой – третье , содержащее базисную переменную и – четвёртое с переменной . Запишем условие (7) для оценок , , и приведенной симплекс-таблицы : ; ; ; ; Теперь запишем условие (8) для нашего случая : , что покомпонентно записывается как : , , , , откуда , , , С учетом того , что мы решали симплекс-методом не исходную задачу (1), а задачу в канонической форме (2), т.е . по оптимальной симплекс-таблице мы можем найти решение двойственной задачи к канонической форме исходной задачи . Оч евидно , задача в симметричной и канонической форме – две разные задачи , отличающиеся знаком и количеством ограничений в двойственных задачах . Более того , так как все ограничения в канонической задаче – равенства , то в двойственной задаче все могут быть любого знака , поэтому наши не являются ошибкой . Но нам необход имо решить не двойственную к канонической задаче , а двойственную к симметричной . Если сделать замену , то двойственная задача к симметричной задаче примет форм у двойственной к канонической задаче . Следовательно , или . 4. Решение через матрицу , обратную к базисной. Оптимальное решение двойственной задачи можно найти по формуле . Как видно из оптимальной симплекс-таблицы , . Тогда . Соответственно, . Получим : , Откуда . Таким образом , мы видим , что всеми четырьмя способами было получено одно и то же решение : ; . Экономическая интерпретация трех теорем двойственности. Согласно первой теореме двойственности , если одна из пары двойственных задач имеет оптимальный план , то и другая имеет оптимальный план , причем значения функций цели при оптимальных планах равны между собой ; если же целевая функция одной из задач неограниченна , то другая совсем не имеет планов , и наоборот. В нашем случае пара задач имеет оптимальные планы , значения целевых функций при которых равны 5,2 8 . Экономический смысл этого состоит в том , что в оптимальном плане минимальные затраты фирмы на производство тонны сплава равны максимальной прибыли некой другой фирмы от продажи первой фирме необходимых для производст ва ресурсов по условным ценам , равным двойственным оценкам этих ресурсов. Как было указано выше , вторая теорема двойственности заключается в выполнении соотношений дополняющей нежесткости в случае оптимальности планов пары задач (соотношения (5) и (6)). Пр иведем сначала экономическую интерпретацию условия (6). Каждому из четырёх "ресурсов " исходной задачи соответствует его двойственная оценка , или условная цена ( , , и соответственно ). В случае положительности двойственной оценки (в нашем случае и ) справедливы равенства , т.е . первый и второй "ресурсы " используются полностью и являются дефи цитными . Следует оговориться , что первое равенство выполняется всегда , в противном случае задача не имеет решения . Это логически понятно , поскольку сумма частей всегда равна целому . Что касается третьего и четвёртого ресурсов , то они имеют нулевую двойств е нную оценку , т.е . эти ресурсы не является дефицитным . Рассмотрим теперь условие (5). Поскольку , то справедливы неравенства : . Экономически это значит , что затраты на сырье № 1, 4 и 5 превосходят возможные затраты в случае закупки отдельных ресурсов , поэтому эти виды сырья использоваться не будут . С другой стороны , , , следовательно , т.е . затраты на сырье первого и второго вида равны альтернативным затратам на произво дство , значит эти виды сырья будут использоваться. Третья теорема двойственности позволяет определить зависимость изменения целевой функции начальной задачи от изменения запасов "ресурсов ": , т.е . в нашем случае как изменяются минимальные издержки на производство единицы сплава в зависимости от изменения "ресурсов ". Так , пусть , например , максимальная доля олова увеличится на 0,1, т.е . до 40 %. Тогда , по третьей теореме двойственности , минимальные издержки на производство единицы сплава уменьшатся на [у.е .]. С другой стороны , изменение минимальной доли цинка или свинц а не приведет к изменению минимальных издержек , поскольку их двойственные оценки равны нулю . Но двойственные оценки позволяют о влиянии на целевую функцию не любых изменений ресурсов , а лишь таких , какие не приводят к недопустимости оптимального решения.
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- Дорогая, пиво будешь?
- А с чем?
- С солями.
- Буду. Где салями?
- Вот. Соль крупная, соль мелкая...
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

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

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru