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

Контрольная

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

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

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

закрыть
Категория: Контрольная работа
Язык контрольной: Русский
Дата добавления:   
 
Скачать
Архив Zip, 84 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникальной работы

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

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 - 2017
Рейтинг@Mail.ru