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

Контрольная

Решение задач линейного программирования

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

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

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

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

ЛАБОРАТОРНАЯ РАБОТ А № 11 РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель р аботы : изучен ие принципов составления оценочных характеристик для з адач линейного программирования , получение навыков использования симплекс-метода для решения задач линейного программирования , усвоение различий получаемых результатов , изуч ение табличной формы применения симплекс-метода . ТЕОРЕТИЧЕСК ИЕ ОСНОВЫ Стандарт ная задача линейного программирования сос тоит из трех частей : целевой фу нкции (на максимум или минимум ) - формула (1.1), основных oграничений - формула (1.2), ограничений не отри цательности переменных (есть , нет ) - формула (1.3) (1.1) i = 1,… m (1.2) (1.3) Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид , когда целевая функция стремится к максимуму (если стремилась к минимуму , то функцию надо умножить на -1, на станет стремиться к максимуму ), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждог o такого k-го неравенства добавить искусственную переменную u k , а в случае знака , u k надо отнять ее из правой части основных ограничений ), присутствуют огр аничения не отрицательности переменных (если их нет для некоей переменной х k , то их можно ввести путем замены всех вхождений этой переменной комбинацией x 1 k - х 2 k = х k , где х 1 k и х 2 k ). П ри этом для решения задачи линейного программирования необходимо иметь базис , т.е . набор переменных х i , в количест ве , равным числу основных ограничений , причем чтобы каждая из этих переменных присутст вовала лишь в одном основном oграничении и имела свой мн ожитель а ij = 1 . Если таких переменны х нет , то они искусственно добавляются в основные ограничения и получают индексы х m +1 , x m +2 и т.д . Считается при этом , чт о они удовлетворяют условиям не отрицательнос ти переменных . Заметим , что если базисные переменные (все ) образуются в результате приведения задачи к каноническому виду , то целевая функция задачи остается без измене ний , а если переменные добавляются искусствен но к основн ым ограничениям , имеющим вид равенств , то из целевой функ ции вы читается их сумма , ум ноженная на М , т.е . (так называем ый модифицированный симпле кс-метод ) . Мы не будем р ассматривать задачи , относящиеся к модифицированн ому симплекс-методу . Для практической рабо - ты по нахождению решения задачи линейного программ ирования (по варианту простого симплекс-метода ) будут использоваться алгоритм итерационного (многошагового ) процесса нахождения решения и два типа оперативных оце - нок , позволяющ их делать п ереходы от одного шага к другому , а также показы - вающих , когда итерационный процесс остановится и результат будет найден . Первая оценка - это дельта-оц енка , для переменной х j она имеет вид : (1.4) Здесь выражение i B означа ет , что в качестве коэффициентов целевой ф унк - ции , представленных в сумме выражения (1.4), используютс я коэффициенты переменных , входящих в базис на данном шаге итерационного процесса . Пере - ме нными а ij являю тся множители матрицы коэффициентов А при основных ог - раничениях , рассчитанные на дан ном шаге итерационного процесса . Дельта-оценки рассчитываются по всем переменным х i , име ющимся в задаче . Следует отметить ; что дел ьта-оценки базисных переме нных равны нулю . После нахож - дения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка , переменная х k , ей соответствующая , будет вводиться в базис . Другой важной оценкой является тетта-оценка , име ющая вид : (1.5) Т.е . по номеру k, найденному по дельта-оценке , мы получаем выход на пере - менную х k и элементы столбца Х B делим на соответствующие (только положи тельны е ) элементы столбца матрицы А , соотве тствующего переменой x k . Из полученных результатов выбираем минимальный , он и будет тетта-оценкой , а i - й элемент столбца B , лежащий в одной строке с тетта-оценкой , будет вы во - дит ься из базиса , заменяясь элементом x k , полученным по дельта-оценке . Для осуществления такой замены нужно в i-ой строке k - г o столбца матрицы А сде - лать единицу , а в осталь ных элементах k- го столбца сделать нули . Такое преоб - разование и будет одним шагом и терационного процесса . Для осуществления такого преобразования используется метод Гаусса . В соответствии с ним i-я стр ока всей матрицы А , а также i-я коо рдината Х B делят ся на a ik (получ аем единицу в i-ой строке вводимого в б азис элемента ). Затем вся i-я ст рока (если i не единица ), а также i-я коо рдината Х B умножаются на элемент ( -а 1k ). После этого производит ся поэлементное суммирование чисел в соответс твующих столбцах 1-ой и i-ой строк , суммируют ся также Х B 1 , и ( -а 1k ) *Х B i ;. Аналогичные действия производятся для всех остальных строк кроме i-ой (базисной ) строк и . В результате получается , что в i-ой ст роке k-го элемента стоит 1, а во всех ос - т альных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма , Шаги алгоритма симплекс-мет ода продолжаются до тех пор , пока не будет получен о дин из следующих результатов . • Все небазисные дельта-оценки больше нуля — найдено решение задачи ли- нейног о программирования , оно представляет из себя вектор компонент х ;, значения которых либ о равны н улю , либо равны элементам столбца Х , та - в кие компоненты стоят на базисных местах (скажем , если базис образуют пе - ременные х 2 , x 4 , х 5 , то ненулевые к омпоненты стоят в векторе решения зада - чи линейно го программирования на 2-м , 4-м и 5-м мест ах ). • Имеются небазисные дельта-оценки , равные нулю , тогда делается вывод о том , что задача линейного программирования имеет бесчис ленное множество решений (представляемое лучом или отрезком ). Подробно рассматривать случаи такого типа , а также отличия между реше ниями в виде луча и отрезка мы н е будем . • Возможен вариант получени я столбца отрицательных элементов на отрица - тельной рассчитанной дельта-оценке , в такой ситуации нельзя вычислить тетта-оценки . В этом слу чае делается вывод , что система ограничений задачи линей ного программирования несовмес тна ; следовательно , задача линейного программирова ния не имеет решения . Решени е задачи линейного программирования , если оно единственное , следует записы вать в виде Х * = (..., ..., ...) - вектора решения и значения целевой фун к - ции в точке решения L *(Х *). В других с лучаях (решений много или они отсут - ствуют ) следуе т словесно описать полученную ситуацию . Если решение задачи линейного программирования не будет получено в течение 10-12 итераций симп лекс-метода , то следует написать , что реш ение отсутствует в связи с неог - рачниченностью функции цели . Для практического решения задачи линейного програм мирования сим пл екс-методом удобно пользоваться таблицей вида (табл . 11.1): Таблица 1.1 B C B X B A 1 … A n Q Базисные Целевые Правые компоненты Коэффиц. Части Базиса ограничен D D1 D n Задание Необходимо решить задачу лин ейного программирования . L ( x ) = x 1 – 2 x 2 + 3 x 3 x 1 – 3 x 2 3 2 x 1 – x 2 + x 3 3 - x 1 + 2 x 2 – 5 x 3 3 Все x i 0 i = 1, … 3 1. Для начала прив едем задачу к каноническому виду : L ( x ) = x 1 – 2 x 2 + 3 x 3 x 1 – 3 x 2 + x 4 = 3 2 x 1 – x 2 + x 3 + x 5 = 3 - x 1 + 2 x 2 – 5 x 3 + x 6 = 3 Все x i 0 i = 1, … 6 2. Составляем та блицу симплекс-метода (табл . 1.2). В идно , что базис образуют компаненты x 4 , x 5 , x 6 : B C B X B A 1 A 2 A 3 A 4 A 5 A 6 Q A 4 0 3 1 -3 0 1 0 0 - A 5 0 3 2 -1 1 0 1 0 3 A 6 0 3 -1 2 -5 0 0 1 - D -1 2 -3 0 0 0 A 4 0 3 1 -3 0 1 0 0 A 3 3 3 2 -1 1 0 1 0 A 6 0 3 -1 2 0 0 0 1 D 9 5 2 0 0 3 0 Таким образом , уже на втором шаге расчетов (вычислений дельта-оценок ) получено , что все небазисные дельта оценки положительны , а это означает , что данная задача имеет единственное решение : 3. Решение задачи запишем в виде : X * = (0, 0, 3, 3 ,0, 3), L *( X *) = 9.
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Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Око за око, зуб за зуб: школьники из Костромы сдали ЕГЭ по чеченскому языку на 100 баллов.
Anekdot.ru

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

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

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


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