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

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

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования) - Лабораторная Работа, раздел Программирование, Лабораторная Работа 2Телешовой Елизаветы, Гр. 726,цель Рабо...

Лабораторная работа 2Телешовой Елизаветы, гр. 726,Цель работы Решение задач линейного программированиясимплекс-методом.Варианты разрешимости задач линейного программирования. 1 вариант.1. Четыре студента Иванов, Петров,Сидоров и Васильев пошли на концерт группы Чайф , захватив пиво 2 сортов Русич и Премьер . Определить план распития напитков для получениямаксимального суммарного опьянения в . Исходные данные даны в таблице Студент Норма выпитого Запасы в литрах Русич Премьер Иванов 1.5 Петров 3,5 1 1,5 Сидоров 10 4 4,5 Васильев 1 0,7 Крепость напитка 2. Математическая модель.2.1Управляемые параметрыx1 л количество выпитого пива Русич . x2 л количество выпитого пива Премьер . решение.2.2Ограничения количество пива Русич , выпитого Ивановым. количество пива Премьер , выпитого Ивановым. общее количество пива, выпитого Ивановым.Общее количество пива, выпитого Ивановым, не превосходитимеющихся у него запасов пива, поэтому л .Аналогично строим другие ограничения л . л . л .3.Постановка задачи. Найти , где достигается максимальное значение функциицели 4. Решение. при Приведем задачу к каноническому виду Определим начальный опорный план .Это решение является опорным, т.к.вектора условий при положительных компонентах решения линейно независимы, также, где , но не все оценки положительны , где Опорный план является оптимальным, еслидля задачи максимизации все его оценки неотрицательны. не являетсяоптимальным, значит критерий можно улучшить, если увеличить одну их отрицательныхсвободных переменных.

Будем увеличивать , т.к. ее увеличение вызовет большее увеличение функции цели.Предположим, что , тогда Запишем новый опорный план . Все оценки опорного плана должны быть неотрицательны, азначит должны выполняться условия gt При увеличении , первой перестает выполнять условие неотрицательностипеременная , т.к. она первая обращается в ноль. Значит выведем из базиса.

Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новыепеременные.Из ограничения 2 имеем .Подставляя в функцию цели получаем Оформим данный этап задачи в видесимплекс-таблицы Начальная симплекс-таблица 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 0 X3 2 2 1 0 0 0 1,5 0 X4 3,5 1 0 1 0 0 1,5 0 X5 10 4 0 0 1 0 4,5 0 X6 0 1 0 0 0 1 0,7 F -16 -0 Пересчитаем элементы исходной таблицы поправилу четырехугольника 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 0 1,428 1 -0,572 0 0 0,642 16 X1 1 0,286 0 0,286 0 0 0,428 0 X5 0 1,14 0 -2,86 1 0 0,214 0 X6 0 1 0 0 0 1 0,7 F 0 -5,424 0 4,576 0 0 6,857 Пересчитав все оценки, видим, что , значит критерий можно улучшить.

Будем увеличивать . Пусть , тогда откуда получаем Все оценки опорного плана должны бытьнеотрицательны, а значит должны выполняться условия gt Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные , а из ограничений 2 и 3 . Тогда 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 0 0 1 3 -1,25 0 0,375 16 X1 1 0 0 1 -0,25 0 0,375 10 X2 0 1 0 -2,5 0,875 0 0,1875 0 X6 0 0 0 2,5 -0,875 1 0,5125 F 0 0 0 -9 4,75 0 7,875 Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда откуда получаем Все оценки опорного плана должны бытьнеотрицательны, а значит должны выполняться условия gt Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные , а из ограничений 1 и 2 . Тогда 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 0 X4 0 0 0,333 1 -0,416 0 0,125 16 X1 1 0 -0,333 0 0,166 0 0,25 10 X2 0 1 1,833 0 -0,166 0 0,5 0 X6 0 0 -0,833 0 0,166 1 0,2 F 9 Видим, что все оценки положительны, значит любоеувеличение какой-либо свободной переменной уменьшит критерий.

Данное решениеявляется оптимальным.

Изобразим это решение на графике Видим, что единственное идостигается в угловой точке области допустимых решений.2 вариант.Отмечая успешно сданную сессию, вышеупомянутыестуденты взяли столько же пива и в таких же пропорциях, за исключением того,что вместо пива Премьер было куплено пиво Окское , крепость которого 6,4 дешевое и разбавленное . Определить план распития напитков для получениямаксимального суммарного опьянения в .Функция цели .Приводим ограничения к каноническому виду gt Решаем симплекс-методом 16 6,4 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 2 2 1 0 0 0 1,5 0 X4 3,5 1 0 1 0 0 1,5 0 X5 10 4 0 0 1 0 4,5 0 X6 0 1 0 0 0 1 0,7 F -16 -10 0 0 0 0 0 , 16 6,4 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 0 1,428 1 -0,571 0 0 0,642 16 X1 1 1,286 0 0,286 0 0 0,428 0 X5 0 1,142 0 -2,85 1 0 0,214 0 X6 0 1 0 0 0 1 0,7 F 0 -1,82 0 4,571 0 0 6,857 16 6,4 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 0 0 1 3 -1,25 0 0,375 16 X1 1 0 0 1 -0,25 0 0,375 6,4 X2 0 1 0 -2,5 0,875 0 0,1875 0 X6 0 0 0 2,5 -0,875 1 0,5125 F 0 0 0 0 1,6 0 7,2 Видим, что все оценки положительны, значитоптимальное решение достигнуто. Но одна из свободных переменных обратилась в ноль, и если мы ее будем увеличивать, тофункция цели не изменится, а решение будет другим, т.е. получим еще однооптимальное решение, которое будет называться альтернативным. 16 10 0 0 0 0 Св Б. П. X1 X2 X3 X4 X5 X6 в 0 X4 0 0 0,333 1 -0,416 0 0,125 16 X1 1 0 -0,333 0 0,166 0 0,25 10 X2 0 1 1,833 0 -0,166 0 0,5 0 X6 0 0 -0,833 0 0,166 1 0,2 F 0 0 0 0 1 0 7,2 Если оптимальное решение достигнуто в 2-х точках,то оно достигается и на отрезке между ними. Можно составить уравнение данногоотрезка по формуле На графике видно, что оптимальное решениедостигается на отрезке, значит является альтернативным. Вектор градиентацелевой функции F параллеленрадиус-вектору ограничения 3 .Это ограничение образует все множество оптимальных решений.Можно сделать вывод, что альтернативные решенияимеются, когда все оценки свободных переменных больше 0, а среди коэффициентовцелевой функции оценка одной из свободных переменных равна 0.3 вариант.Студент Петров, решив догнать по количествувыпитого студента Сидорова, выпил 4 доли пива Русич вместо запланированных3,5. Решим задачу с учетом изменившихся данных.Функция цели .Приводим ограничения к каноническому виду gt Решим задачу симплекс-методом. 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 0 X3 2 2 1 0 0 0 1,5 0 X4 4 1 0 1 0 0 1,5 0 X5 10 4 0 0 1 0 4,5 0 X6 0 1 0 0 0 1 0,7 F -16 -10 0 0 0 0 0 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 В 0 X3 0 1,5 1 -0,5 0 0 0,75 16 X1 1 0,25 0 0,25 0 0 0,375 0 X5 0 1,5 0 -2,5 1 0 0,75 0 X6 0 1 0 0 0 1 0,7 F 0 -6 0 4 0 0 6 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 10 X2 0 1 1,666 -0,333 0 0 0,5 16 X1 1 0 -0,166 0,333 0 0 0,25 0 X5 0 0 -1 -2 1 0 0 0 X6 0 0 -0,666 0,333 0 1 0,2 F 0 0 4 2 0 0 9 , Данное оптимальное решение является вырожденным,т.к. положительных компонентов меньше числа ограничений.

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

Существует 2 способа предупреждения зацикливания а изменение ходаограничения на некоторые величины . Они должны быть малы, чтобы изменения были несущественны.б Если минимальное отношение свободныхкоэффициентов к положительным членам разрешающего столбца определяетсянеоднозначно, то выбирается отношение любого другого столбца к положительнымкоэффициентам данного столбца, пока строка не определится однозначно. 4 вариант.В связи с неожиданно полученной стипендией, запасыпива резко увеличились.Функция цели .Приводим ограничения к каноническому виду gt В матрице условий нет единичной подматрицы, поэтомуиспользуем метод искусственного базиса.

Построим вспомогательную задачу. , при этом .Решаем вспомогательную задачу симплекс-методом 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 1 X7 2 2 -1 0 0 0 1 0 0 0 1,5 1 X8 3.5 1 0 -1 0 0 0 1 0 0 1,5 1 X9 10 4 0 0 -1 0 0 0 1 0 4,5 1 X10 0 1 0 0 0 -1 0 0 0 1 0,7 F 15,5 8 -1 -1 -1 -1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 1 X7 0 1,428 -1 0,571 0 0 1 -0,571 0 0 0,642 0 X1 1 0,285 0 -0,285 0 0 0 0,285 0 0 0,428 1 X9 0 1,142 0 2,857 -1 0 0 -2,85 1 0 0,214 1 X10 0 1 0 0 0 -1 0 0 0 1 0,7 F 0 3.571 -1 3,428 -1 -1 0 -4,42 0 0 1,557 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 1 X7 0 0 -1 -3 1,25 0 1 3 -1,25 0 0,375 0 X1 1 0 0 -1 0,25 0 0 1 -0,25 0 0,375 0 X2 0 1 0 2,5 -0,875 0 0 -2,5 0,875 0 0,187 1 X10 0 0 0 -2,5 0,875 -1 0 2,5 -0,875 1 0,512 F 0 0 -1 -5,5 2,125 -1 0 4,5 -3,12 0 0,887 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 1 X8 0 0 -0,333 -1 0,416 0 0,333 1 -0,416 0 0,125 0 X1 1 0 0,333 0 -0,166 0 333 0 0,166 0 0,25 0 X2 0 1 -0,833 0 0,166 0 0,833 0 -0,166 0 0,5 1 X10 0 0 0,833 0 -0,166 -1 -0,833 0 0,166 1 0,2 F 0 0 0,5 -1 0,25 -1 -1,5 0 -1,25 0 0,325 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 1 X8 0 0 0 -1 0,35 -0,4 0 1 -0,35 0,4 0,205 0 X1 1 0 0 0 -0,1 0,4 0 0 0,1 -0,4 0,17 0 X2 0 1 0 0 0 -1 0 0 0 1 0,7 0 X3 0 0 1 0 -0,2 -1,2 -1 0 0,2 1,2 0,24 F 0 0 0 -1 0,35 -0,4 -1 0 -1,35 -0,6 0,205 0 0 0 0 0 0 1 1 1 1 Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 в 0 X5 0 0 0 -2,85 1 -1,14 0 2,857 -1 -1,142 0,585 0 X1 1 0 0 -0,285 0 0,285 0 0,285 0 -0,285 0,228 0 X2 0 1 0 0 0 -1 0 0 0 1 0,7 0 X3 0 0 1 -0,571 0 -1,42 -1 -1,571 0 1,428 0,357 F 0 0 0 0 0 0 -1 -1 -1 -1 0 оптимальное решение вспомогательной задачи.Искусственные переменные являются свободными и равны нулю. Т.о. это решениеявляется опорным планом исходной задачи.Решим исходную задачу 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 0 X5 0 0 0 -2,85 1 -1,14 0,585 16 X1 1 0 0 -0,285 0 0,285 0,228 10 X2 0 1 0 0 0 -1 0,7 0 X3 0 0 1 -0,571 0 -1,42 0,357 F 0 0 0 -4,576 0 -5,424 3,648 Критерийможно улучшить, т.к но нельзя найти такое , при котором базисные переменные обращаются в 0. Значитзадача неразрешима из-за неограниченности критерия.5 вариант.После отмеченного таким образом праздникаобязательно наступает похмелье.

Решим задачу из предыдущего варианта,минимизируя этот неприятный фактор, т.е. функция цели .Приводим ограничения к каноническому виду gt Эта задача решается методом искусственного базиса,т.к. в ней нет единичной подматрицы.

Вспомогательная задача получается точнотакой же, как и в предыдущем варианте, поэтому просто возьмем опорный план изпредыдущей задачи. 16 10 0 0 0 0 Св Б.П. X1 X2 X3 X4 X5 X6 в 0 X5 0 0 0 -2,85 1 -1,14 0,585 16 X1 1 0 0 -0,285 0 0,285 0,228 10 X2 0 1 0 0 0 -1 0,7 0 X3 0 0 1 -0,571 0 -1,42 0,357 F 0 0 0 -4,576 0 -5,424 3,648 Видим, что оценки свободных переменных меньше нуля,значит решение оптимальное.

F 3,648.Делаемвывод оптимальноерешение может существовать и при неограниченности области.Область не ограничена, но существует оптимальноерешение , причем единственное, которое достигается в угловой точке.

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

Используемые теги: Лабораторная, работа, основам, Теории, систем, Решение, задач, ного, программирования, симплекс-методом, Варианты, разрешимости, задач, ного, программирования0.178

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Лабораторная работа №2 по "Основам теории систем" (Решение задач линейного программирования симплекс-методом. Варианты разрешимости задач линейного программирования)

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

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

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

Лабораторная работа №5 по "Основам теории систем" (Транспортные задачи линейного программирования)
В амбаре было 4 мышиных норы в первой проживало 15 мышей, во второй 20, в третьей 10 мышей, а в четвертой 25 мышей, а также 5 источников пищи, от… Считая что количество мышей из -той норы, питающихся у -того источника пищи,… Для этого мыши оценили так называемые потенциалы нор и источников пищи . Так как их цель минимизировать потери, то…

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

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

Понятие воспитательной работы. Роль и место воспитательной работы в системе работы с кадрами
Это, в свою очередь, требует повышения уровня воспитательной работы с личным составом, выделения приоритетов в системе воспитания личного состава,… Вместе с тем в современных условиях принимаемые меры воспитательного… Коллегия МВД России на заседании 23 декабря 1998 г рассмотрев состояние работы с кадрами в системе кадровой политики…

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

Лекция 1. Тема: Операционная система. Определение. Уровни операционной системы. Функции операционных систем. 1. Понятие операционной системы
Понятие операционной системы... Причиной появления операционных систем была необходимость создания удобных в... Операционная система ОС это программное обеспечение которое реализует связь между прикладными программами и...

Задания для выполнения контрольной работы и лабораторной работы для самостоятельной работы студентов Менеджмент и маркетинг
На сайте allrefs.net читайте: "Задания для выполнения контрольной работы и лабораторной работы для самостоятельной работы студентов Менеджмент и маркетинг"

СД.09.04 ТЕХНОЛОГИЯ И ОРГАНИЗАЦИЯ СТРОИТЕЛЬНЫХ РАБОТ Курсовая работа. Составление календарных графиков (линейного и сетевого) и стройгенплана строительства гидромелиоративной системы
Кафедра... Природообустройства строительства и гидравлики...

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

Решение задач линейного программирования
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ Стандартная задача линейногопрограммирования состоит из трех частей целевой функции на максимум илиминимум - формула 1.1 ,… Заметим, что еслибазисные переменные все образуются в результате приведения… Для практической рабо-ты по нахождению решения задачи линейного программирования по варианту простого симплекс-метода…

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