Решение задач линейного программирования
Геометрическая интерпретация линейного программирования при заданных показателях целевой функции и ограничениях в виде равенств и неравенств аналитическим и геометрическим способами. Оптимальный расчет максимизации критериев, особенности симплекс-метода.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | лабораторная работа |
| Язык | русский |
| Дата добавления | 15.05.2014 |
| Размер файла | 77,1 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Министерство образования и науки РТ
Альметьевский государственный нефтяной институт
Кафедра «Автоматизации и информационных технологий»
Отчет по лабораторной работе
по дисциплине:
«Моделирование систем»
«Решение задач линейного программирования»
Миннахметова А.А., Мухаметзянов Р.
Альметьевск 2014 г.
Цель работы
Цель данной работы - решение задач линейного программирования при заданных целевой функции и ограничениях в виде равенств и неравенств аналитическим и геометрическим способами.
Основные сведения из теории
Среди известных разделов математического программирования наиболее развитым является линейное программирование (ЛП). Несмотря на требование линейности целевой функции, и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, конструкций и технологических процессов производства аппаратуры и т.д.
Постановка задач линейного программирования и их геометрическая интерпретация
В задачах линейного программирования критерий оптимальности представляется в виде:
(1)
где - заданные постоянные коэффициенты, положительные или отрицательные, среди которых могут быть также равные нулю.
(2)
Коэффициенты в соотношение (2) принимаются действительными числами, положительными или отрицательными, среди которых могут быть равные нулю.
Оптимальным решением задачи линейного программирования или, как его еще называют, оптимальным планом является такая совокупность неотрицательных значений независимых переменных которая удовлетворяет условиям (2) и обеспечивает в зависимости от постановки задачи максимальное или минимальное значение линейной формы (1). В дальнейшем предполагаем, что оптимум достигается при максимальном значении формы (1). Случай, когда требуется найти минимальное значение линейной формы, может быть сведен к задаче максимизации простым изменением знаков у всех коэффициентов
, (3)
Сведение задачи с ограничениями типа неравенств к задаче с ограничениями типа равенств. Покажем, что все ограничения типа неравенств могут быть представлены в виде равенств введением m новых переменных, называемых дополнительными. Для этого в каждом соотношении (2) прибавим к левой части дополнительную переменную , которая превращает неравенство в равенство:
(4)
Для решения задач линейного программирования используется геометрический метод, а так же была разработана специальная вычислительная процедура, называемая симплекс-методом и основанная на ряде теоретических утверждений линейного программирования.
9 задача
Решить задачу максимизации критерия оптимальности, имеющего вид:
При наличии ограничений на и типа неравенств:
Решить аналитически и графически.
Решение:
I. 1) Перепишем систему ограничений в виде равенств:
2) Составим матрицу системы и расширенную матрицу и найдем их ранги:
ранг = 2;
; ранг = 2;
3) За базисные переменные примем , , следовательно, свободные переменные - ,.
; ; ;
; ; ;
4) Следовательно, целевая функция
Допустимое решение получится при и , тогда и . Вычисляем, что при этих значениях . Так как в линейной форме свободные переменные , с отрицательными коэффициентами, то дальнейшее увеличение функции невозможно.
Таким образом, оптимальное решение
II. 1) В первую очередь, найдем область допустимых значений, т.е. точки и, которые удовлетворяют системе ограничений. По условию задачи, т.е. рассматриваем только те точки, которые принадлежат первой четверти.
2) Рассмотрим первое неравенство системы ограничений .
Построим прямую. Заменим знак неравенства на знак равенства. . Преобразуем уравнение следующим образом. . Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси рисуем точку с координатой 1/2 . На оси рисуем точку с координатой 1 .Соединяем полученные точки и получаем необходимую прямую.
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Область допустимых значений выделена штриховкой.
3) Рассмотрим второе неравенство системы ограничений .
Построим прямую. Заменим знак неравенства на знак равенства. . Преобразуем уравнение следующим образом. . Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси рисуем точку с координатой 1. На оси рисуем точку с координатой 1/2 .Соединяем полученные точки и получаем необходимую прямую.
Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. Область допустимых значений выделена штриховкой.
4) Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений (рис.1).
Рис.1.
5) Рассмотрим целевую функцию задачи > max. Из начала координат проводим вектор . Из начала координат перпендикулярно вектору перемещаем прямую по всей области. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.
Рис.2
линейное программирование аналитика геометрия
Область допустимых решений представляет собой многоугольник.
Прямая пересекает область в точке C. Так как точка C получена в результате пересечения прямых, то ее координаты удовлетворяют уравнениям этих прямых. Решив систему уравнений, получим: , (рис.2).
Откуда найдем максимальное значение целевой функции:
Видим, что решение, полученное графическим путем, совпадает с решением, полученным аналитическим методом.
Размещено на Allbest.ru
...Подобные документы
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции.
курсовая работа [1,1 M], добавлен 21.03.2012Оптимизационные исследования задач линейного и нелинейного программирования при заданных математических моделях. Решение задач линейного программирования и использование геометрической интерпретации и табличного симплекс-метода, транспортная задача.
курсовая работа [408,7 K], добавлен 13.06.2019Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами.
методичка [366,8 K], добавлен 16.01.2010Сущность линейного программирования. Математическая формулировка задачи ЛП и алгоритм ее решения с помощью симплекс-метода. Разработка программы для планирования производства с целью обеспечения максимальной прибыли: блок-схема, листинг, результаты.
курсовая работа [88,9 K], добавлен 11.02.2011Широкое применение вычислительной техники как в общей математике, так и в одном из её разделов – математических методах. Ознакомление с решением задач линейного программирования симплекс-методом и графически. Составлена программа на языке Delphi.
курсовая работа [57,1 K], добавлен 04.05.2010Описание симплекс метода решения задачи линейного программирования. Решение задачи методом Литла на нахождение кратчайшего пути в графе, заданном графически в виде чертежа. Из чертежа записываем матрицу расстояний и поэтапно находим кратчайший путь.
задача [390,4 K], добавлен 10.11.2010Анализ решения задачи линейного программирования. Симплексный метод с использованием симплекс-таблиц. Моделирование и решение задач ЛП на ЭВМ. Экономическая интерпретация оптимального решения задачи. Математическая формулировка транспортной задачи.
контрольная работа [196,1 K], добавлен 15.01.2009Постановка задачи линейного программирования. Решение системы уравнений симплекс-методом. Разработка программы для использования симплекс-метода. Блок-схемы основных алгоритмов. Создание интерфейса, инструкция пользователя по применению программы.
курсовая работа [1,7 M], добавлен 05.01.2015Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения.
курсовая работа [132,0 K], добавлен 09.12.2008Построение математической модели. Выбор, обоснование и описание метода решений прямой задачи линейного программирования симплекс-методом, с использованием симплексной таблицы. Составление и решение двойственной задачи. Анализ модели на чувствительность.
курсовая работа [100,0 K], добавлен 31.10.2014Разработка программы, решающей базовую задачу линейного программирования симплекс-методом с помощью симплекс-таблиц. Выбор языка программирования и среды разработки, программные модули и их взаимодействие между собой. Листинг разработанной программы.
курсовая работа [415,8 K], добавлен 08.09.2013Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2.
контрольная работа [199,8 K], добавлен 15.06.2009Нахождение минимума целевой функции для системы ограничений, заданной многоугольником. Графическое решение задачи линейного программирования. Решение задачи линейного программирования с использованием таблицы и методом отыскания допустимого решения.
курсовая работа [511,9 K], добавлен 20.07.2012Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения.
контрольная работа [191,1 K], добавлен 05.04.2016Строение системы уравнений-ограничений и ее переменных, графический способ решения задач линейного программирования на плоскости. Выражение неизвестных через две независимые переменные, являющиеся координатными осями графика. Значение целевой функции.
лабораторная работа [61,4 K], добавлен 07.01.2011Изучение и укрепление на практике всех моментов графического метода решения задач линейного программирования о производстве журналов "Автомеханик" и "Инструмент". Построение математической модели. Решение задачи с помощью электронной таблицы Excel.
курсовая работа [663,9 K], добавлен 10.06.2014Классификация задач математического программирования. Сущность графического метода решения задач линейного программирования, алгоритм табличного симплекс-метода. Описание логической структуры и текст программы по решению задачи графическим методом.
курсовая работа [263,5 K], добавлен 27.03.2011Оптимизационная задача линейного программирования. Виды задач линейного программирования. Принятие решений на основе количественной информации об относительной важности критериев. Выбор средств разработки. Программный комплекс векторной оптимизации.
дипломная работа [1,3 M], добавлен 27.03.2013Математическая модель задачи. Симплекс-таблица. Решение задачи линейного программирования. коэффициенты при переменных в целевой функции. Метод северо-западного угла. Система неравенств в соответствии с теоремой Куна-Таккера. Функция Лагранжа.
контрольная работа [59,5 K], добавлен 29.09.2008Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа [4,0 M], добавлен 05.03.2012
