рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

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

Работа сделанна в 2002 году

Решение задач линейного программирования - Лабораторная Работа, раздел Математика, - 2002 год - Министерство Общего И Профессионального Образования Российской Федерации Воро...

Министерство общего и профессионального образования Российской Федерации Воронежский Государственный Архитектурно Строительный Университет Кафедра Экономики и управления строительством ЛАБОРАТОРНАЯ РАБОТА На тему Решение задач линейного программирования Выполнил Студент 4 курса ФЗО ЭУС Сидоров В.В. Руководитель Богданов Д. А. Воронеж 2002 г. ЛАБОРАТОРНАЯ РАБОТА 11РЕШЕНИЕ ЗАДАЧЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы изучение принципов составленияоценочных характеристик для задач линейного программирования, получение навыковиспользования симплекс-метода для решения задач линейного программирования,усвоение различий получаемых результатов, изучение табличной формыприменения симплекс-метода.

ТЕОРЕТИЧЕСКИЕ ОСНОВЫ Стандартная задача линейногопрограммирования состоит из трех частей целевой функции на максимум илиминимум - формула 1.1 , основных oграничений - формула 1.2 , ограничений неотрицательности переменных есть, нет - формула 1.3 1.1 i 1, m 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 32x1 x2 x3 3-x1 2x2 5x3 3Все xi 0 i 1, 3 1. Для началаприведем задачу к каноническому виду L x x1 2x2 3x3 x1 3x2 x4 32x1 x2 x3 x5 3-x1 2x2 5x3 x6 3Все xi 0 i 1, 6 2. Составляемтаблицу симплекс-метода табл. 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 Таким образом, уже на второмшаге расчетов вычислений дельта-оценок получено, что все небазисные дельтаоценки положительны, а это означает, что данная задача имеет единственноерешение 3. Решениезадачи запишем в виде X 0, 0, 3, 3,0, 3 , L X 9.

– Конец работы –

Используемые теги: Решение, задач, ного, программирования0.069

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

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)
Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели.Предположим, что , тогда Запишем новый опорный план . Все оценки… Теперь базисными переменными являются , а свободными . Для анализа этого плана… Будем увеличивать . Пусть , тогда откуда получаем Все оценки опорного плана должны бытьнеотрицательны, а значит должны…

Постановка задачи линейного программирования и двойственная задача линейного программирования.
Всвязи с развитием техники, ростом промышленного производства и с появлением ЭВМвсе большую роль начали играть задачи отыскания оптимальных решений… Именно в силу этого процесс моделированиячасто носит итеративный характер. На… Здесь имеется полная аналогия с тем, как весьма важнаи зачастую исчерпывающая информация о поведении произвольной…

Закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования
На сайте allrefs.net читайте: - закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования;...

Задача линейного программирования и свойстваее решений
Многие задачи с которыми приходится иметь дело в повседнев ной практике являются многовариантными Среди множе ства возможных вариантов в условиях... Математическое программирование область мате матики разрабатывающая теорию... Функцию экстремальное значение которой нужно найти в условиях экономических возможностей называют целевой...

Решение оптимизационной задачи линейного программирования
Оптимизация - целенаправленная деятельность, заключающаяся в получении наилучших результатов при соответствующих условиях. Поиски оптимальных решений привели к созданию специальных математических… Постановка задачи оптимизации предполагает существование конкурирующих свойств процесса, например количество продукции…

Линейное программирование: постановка задач и графическое решение
Таким образом, задачи линейного программирования относятся к задачам на условный экстремум функции.Казалось бы, что для исследования линейной… Действительно, путь необходимо исследовать на экстремум линейную функцию Z = С… Для решения задач линейного программирования потребовалось создание специальных методов.Особенно широкое…

“Исследование задач нелинейного программирования”
На сайте allrefs.net читайте: “Исследование задач нелинейного программирования”...

Задачи линейного программирования
На сайте allrefs.net читайте: - закрепление теоретических знаний, получаемых студентами на лекционных и самостоятельных занятиях по решению задач линейного программирования;...

Расчетно-графическое задание состоит из четырех задач. Для задач 1,2,3 имеется два варианта, для задачи 4 – вариант для каждого студента.
На сайте allrefs.net читайте: Расчетно-графическое задание состоит из четырех задач. Для задач 1,2,3 имеется два варианта, для задачи 4 – вариант для каждого студента....

Методы линейного программирования, двойственность в линейном программировании
Методы линейного программирования двойственность в линейном... Задание Задание Задание...

0.038
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам