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

Контрольная

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

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

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

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

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



Министерство общего и профессионального образования

Российской Федерации


Воронежский Государственный Архитектурно – Строительный

Университет


Кафедра Экономики и управления строительством











ЛАБОРАТОРНАЯ РАБОТА


На тему: «Решение задач линейного программирования»









Выполнил:

Студент 4 курса

ФЗО ЭУС

Сидоров В.В.


Руководитель:

Богданов Д. А.








Воронеж – 2002 г.



















































ЛАБОРАТОРНАЯ РАБОТА № 11


РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


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



ТЕОРЕТИЧЕСКИЕ ОСНОВЫ


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

целевой функции (на максимум или минимум) - формула (1.1), основных oграничений - формула (1.2), ограничений не отрицательности переменных (есть, нет) - формула (1.3)


(1.1)








i = 1,… m (1.2)




(1.3)


Алгоритм решения задач линейного программирования требует приведения их постановки в канонический вид, когда целевая функция стремится к максимуму (если стремилась к минимуму, то функцию надо умножить на -1, на станет стремиться к максимуму), основные ограничения имеют вид равенства (для приведения к равенствам в случае знака надо в правую часть каждогo такого k-го неравенства добавить искусственную переменную uk , а в случае знака , uk надо отнять ее из правой части основных ограничений), присутствуют ограничения не отрицательности переменных (если их нет для некоей переменной хk, то их можно ввести путем замены всех вхождений этой

переменной комбинацией x1k - х2k = хk, где х1k и х2k ). При этом для решения задачи линейного программирования необходимо иметь базис, т.е. набор переменных хi, в количестве, равным числу основных ограничений, причем чтобы каждая из этих переменных присутствовала лишь в одном основном oграничении и имела свой множитель аij = 1. Если таких переменных нет, то они искусственно добавляются в основные ограничения и получают индексы хm+1, xm+2 и т.д. Считается при этом, что они удовлетворяют условиям не отрицательности переменных. Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической рабо-ты по нахождению решения задачи линейного программирования (по варианту простого симплекс-метода) будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оце-нок, позволяющих делать переходы от одного шага к другому, а также показы-вающих, когда итерационный процесс остановится и результат будет найден.

Первая оценка - это дельта-оценка, для переменной хj она имеет вид:


(1.4)

Здесь выражение i

B означает, что в качестве коэффициентов целевой функ-ции, представленных в сумме выражения (1.4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Пере-менными аij являются множители матрицы коэффициентов А при основных ог-раничениях, рассчитанные на данном шаге итерационного процесса. Дельта-оценки рассчитываются по всем переменным хi, имеющимся в задаче. Следует отметить; что дельта-оценки базисных переменных равны нулю. После нахож-дения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка, переменная хk, ей соответствующая, будет вводиться в базис. Другой важной оценкой является тетта-оценка, имеющая вид:


(1.5)


Т.е. по номеру k, найденному по дельта-оценке, мы получаем выход на пере-менную хk и элементы столбца ХB делим на соответствующие (только положи

тельные) элементы столбца матрицы А, соответствующего переменой xk. Из полученных результатов выбираем минимальный, он и будет тетта-оценкой, аi-й элемент столбца B, лежащий в одной строке с тетта-оценкой, будет выво-диться из базиса, заменяясь элементом xk, полученным по дельта-оценке. Для осуществления такой замены нужно в i-ой строке k - гo столбца матрицы А сде-лать единицу, а в остальных элементах k-го столбца сделать нули. Такое преоб-разование и будет одним шагом итерационного процесса. Для осуществления такого преобразования используется метод Гаусса. В соответствии с ним i-я строка всей матрицы А, а также i-я координата ХB делятся на aik (получаем единицу в i-ой строке вводимого в базис элемента). Затем вся i-я строка (если i не единица), а также i-я координата ХB умножаются на элемент (-а1k). После этого производится поэлементное суммирование чисел в соответствующих столбцах 1-ой и i-ой строк, суммируются также ХB1, и (-а1k)*ХBi;. Аналогичные действия производятся для всех остальных строк кроме i-ой (базисной) строки. В результате получается, что в i-ой строке k-го элемента стоит 1, а во всех ос-тальных его строках находится 0. Таким образом осуществляется шаг итерационального алгоритма, Шаги алгоритма симплекс-метода продолжаются до тех пор, пока не будет получен один из следующих результатов.
• Все небазисные дельта-оценки больше нуля — найдено решение задачи ли-

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

кие компоненты стоят на базисных местах (скажем, если базис образуют пе-ременные х2, x4, х5, то ненулевые компоненты стоят в векторе решения зада-чи линейного программирования на 2-м, 4-м и 5-м местах).

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

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

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

записывать в виде Х* = (..., ..., ...) - вектора решения и значения целевой функ-ции в точке решения L*(Х*). В других случаях (решений много или они отсут-ствуют) следует словесно описать полученную ситуацию. Если решение задачи линейного программирования не будет получено в течение 10-12 итераций симплекс-метода, то следует написать, что решение отсутствует в связи с неог-рачниченностью функции цели.

Для практического решения задачи линейного программирования симплекс-методом удобно пользоваться таблицей вида (табл. 11.1):


Таблица 1.1


B

CB

XB

A1

An

Q

Базисные

Целевые

Правые





компоненты

Коэффиц.

Части






Базиса

ограничен





D



D1


Dn












Задание


Необходимо решить задачу линейного программирования.


L(x) = x1 – 2x2 + 3x3

x1 – 3x2 3

2x1 – x2 + x3 3

-x1 + 2x2 – 5x3 3

Все xi 0 i = 1, …3


  1. Для начала приведем задачу к каноническому виду:


L(x) = x1 – 2x2 + 3x3

x1 – 3x2 + x4 = 3

2x1 – x2 + x3 + x5 = 3

-x1 + 2x2 – 5x3 + x6 = 3

Все xi 0 i = 1, …6


  1. Составляем таблицу симплекс-метода (табл. 1.2). Видно, что базис образуют компаненты x4, x5, x6:


B

CB

XB

A1

A2

A3

A4

A5

A6

Q

A4

0

3

1

-3

0

1

0

0

-

A5

0

3

2

-1

1

0

1

0

3

A6

0

3

-1

2

-5

0

0

1

-

D



-1

2

-3

0

0

0


A4

0

3

1

-3

0

1

0

0


A3

3

3

2

-1

1

0

1

0


A6

0

3

-1

2

0

0

0

1


D


9

5

2

0

0

3

0



Таким образом, уже на втором шаге расчетов (вычислений дельта-оценок) получено, что все небазисные дельта оценки положительны, а это означает, что данная задача имеет единственное решение:


  1. Решение задачи запишем в виде:


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Экономико-математическое моделирование
91Экономическая теория

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

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

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

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


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