Задача линейного программирования - Программирование, компьютеры и кибернетика курсовая работа

Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ФГОУ ПО “ПСКОВСКИЙ КОЛЛЕДЖ СТРОИТЕЛЬСТВА И ЭКОНОМИКИ”
§ 1 Общая постановка задачи линейного программирования
§ 2 Математическая модель задачи линейного программирования
§ 3 Каноническая форма задачи линейного программирования
Глава ЙЙ Решение задачи симплексным методом
§ 2 Составление математической модели задачи
§ 3 Алгоритмы решения задачи симплексным методом
§ 4 Построение начального опорного решения методом Гаусса
В настоящее время множество задач планирования и управления в отраслях народного хозяйства, а также большой объём частных прикладных задач решаются методами математического программирования. Наиболее развитыми в области решения оптимизационных задач являются методы линейного программирования. Эти методы позволяют описать с достаточной точностью широкого круга задач коммерческой деятельности, таких, как планирование товарооборота; размещение розничной торговой сети города; планирование товароснабжения города, района; прикрепление торговых предприятий к поставщикам; организация рациональных перевозок товаров; распределение работников торговли должностям; организация рациональных закупок продуктов питания; распределение ресурсов; планирование капиталовложений; оптимизация межотраслевых связей; замена торгового оборудования; определение оптимального ассортимента товаров в условиях ограниченной площади; установление рационального режима работы.
В задачах линейного программирования критерий эффективности и функции в системе ограничений линейны.
Если содержательный смысл требует получения решения в целых числах, то такая задача является задачей целочисленного программирования.
Если в задаче математического программирования имеется переменная времени, а критерий эффективности выражается через уравнения, описывающие течение операций во времени, то такая задача является задачей динамического программирования.
Во многих экономических моделях зависимости между постоянными и переменными факторами можно считать линейными.
Использование методов математического программирования в коммерческой деятельности связано со сбором необходимой информации коммерсантом, экономистом, финансистом, затем постановкой задачи вместе с математикой. Поскольку методы математического программирования уже реализованы на компьютере в виде пакета стандартных программ, то доступ к ним обычно прост, автоматизирован и не составляет особых трудностей.
Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в ЭВМ, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
§ 1 Общая постановка задачи линейного программирования
Линейное программирование - это направление математического программирование изучающая методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейной целевой функцией. Для решения задач линейного программирования составляется математическая модель задачи и выбирается метод решения.
Постановка задачи коммерческой деятельности может быть представлена в виде математической модели линейного программирования, если целевая функция может быть представлена в виде линейной формы, а связь с ограниченными ресурсами описать посредством линейных уравнений или неравенств. Кроме того, вводится дополнительное ограничение - значения переменных должны быть неотрицательны, поскольку они представляют такие величины, как товарооборот, время работы, затраты и другие экономические показатели.
Геометрическая интерпретация экономических задач даёт возможность наглядно представить, их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задача линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трёхмерном пространстве такое решение усложняется, а в пространствах, размерность которых более трёх, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства задач линейного программирования, приводит к идее её решения, делает геометрически наглядными способы решения и пути их практической реализации.
§ 2 Математическая модель задачи линейного программирования
Перед решением задачи составляем её математическую модель.
Математическая модель - это совокупность соотношений состоящие из линейной целевой функции и линейных ограничений на переменную.
Принцип составления математической модели.
Переменными задачи называются величины которые полностью характеризуют экономический процесс, описанный в задачи. Обычно записываются в виде вектора X = () Причём )
2. Составляют систему ограничения задачи.
Система ограничений - это совокупность уравнений и неравенств, которым удовлетворяют переменные задачи и которая следует из ограниченности экономических условий задачи.
В общем виде система записывается в виде
Целевая функция - это функция Z(X) которая характеризует качество выполнения задачи, экстремум которой надо найти. В общем виде целевая функция записывается Z(X) = (max, min)
т.о. математическая модель имеет вид найти переменные задачи удовлетворяющие системе ограничений:
и условию неотрицательности 0 (j = ), которая обеспечивает экстремум целевой функции Z(Y) =
Допустимым решением задачи линейного программирования называется любой набор значений переменных удовлетворяющий системе ограничений и условной неотрицательности.
Множество допустимых решений образует область допустимых решений задачи (ОДР).
Оптимальным решением называется допустимое решение задачи, при котором целевая функция достигает экстремума.
§ 3 Каноническая форма задачи линейного программирования
Математическая модель задачи должна иметь каноническую форму.
Если система ограничения состоит только из уравнения и все переменные удовлетворяют условию неотрицательности, то задача имеет каноническую форму.
Если в системе есть хотя бы одно неравенства или какая-либо переменная неограниченна условию неотрицательности, то задача имеет стандартную форму. Чтобы привести задачу к каноническому виду надо:
перейти от неравенств к уравнению следующим образом: в левую часть неравенств вводим дополнительную переменную с коэффициентом (+1) для неравенства () и (-1) для неравенства () дополнительные переменные не наложены целевые неотрицательности, то её заменяют разностью двух неотрицательных переменных, то есть:
Глава ЙЙ Решение задачи симплексным методом
Симплексный метод - это метод последовательного улучшения плана (решения), наиболее эффективный и применяется для решения любой задачи линейного программирования.
Название метода от латинского simplecx - простой т.к. из начального область допустимых решений задачи имела простейший вид. Идеи метода предложил российский математик Контарович Л.В. в 1939 году и затем эту идею развил и разработал Дж. Данциг в 1949 году.
Симплексный метод позволяет за конечное число шагов либо найти оптимальное решение либо доказать что его нет.
На предприятии в процессе производства используется 3 вида станков Й, ІЙ, ІЙІ. При этом расходуется сырьё, трудовые ресурсы, и учитываются накладные расходы.
Известно, что для изготовления станка Й - ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 10 ед. накладных расходов; станка ЙІ - ого вида 6 ед. сырья, 2 ед. трудовых ресурсов и 8 ед. накладных расходов; для станка ЙЙІ - ого вида требуется 4 ед. сырья, 2 ед. трудовых ресурсов и 18 ед. накладных расходов; Предприятие имеет в наличии 420 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных ресурсов.
Прибыль от реализации станка І вида - 28 тыс. руб., ІЙ вида - 24 тыс. руб., ЙІЙ вида - 20 тыс. руб. Условия производства требует, чтобы трудовые ресурсы были использованы полностью, а накладные расходы были бы не менее имеющихся в наличии.
Составить план производства станков, обеспечивающих максимальную прибыль.
§ 2 Составление математической модели задачи
Записываем условие задачи в виде таблицы.
Расход рес. на производство ед. продукции
Пусть количество производимых станков 1-ого, 2-ого и 3-его вида,
2. Составляем систему ограничения задачи
трудовые ресурсы были использованы полностью значит, ставим знак (=), а накладные расходы были бы не менее имеющихся в наличии значит, ставим знак ().
Математическая модель имеет вид: найти план выпуска станков
удовлетворяющий системе ограничений задачи
и условию неотрицательности ), при котором прибыль будет максимальной
§ 3 Алгоритмы решения задачи симплексным методом
Общая идея симплексного метода (метода последовательного улучшения плана) для решения задачи линейного программирования состоит
1) умение находить начальный опорный план;
2) наличие признака оптимальности опорного плана;
3) умение переходит к нехудшему опорному плану.
1) Математическая модель задачи должна иметь каноническую форму. В противном случаи её приводят к каноническому виду.
2) Находят начальное опорное решение задачи. Им является вектор, состоящий из тех переменных, которые входят только в одно уравнение в системе ограничений. Если начальное решение сразу не найти то используют метод Гаусса.
Количество переменных решения равно количеству уравнений системы. Заполняют симплексную таблицу по системе ограничений и целевой функции.
Первый столбец - коэффициенты в целевой функции при базисных переменных.
Второй столбец - базисные переменные.
Самая верхняя строка - коэффициенты при целевой функции.
Вторая верхняя строка - сами переменные, входящие в целевую функцию и в систему ограничений.
Основное поле симплекс метода - система коэффициентов из уравнения.
Последняя строка - служит для того, чтобы ответить на вопрос: “оптимален план или нет ”.
Индексная строка позволяет нам судить об оптимальности плана.
3) Проверяют опорное решение, на оптимальность, вычисляя коэффициенты индексной строки по форме:
При решении задачи возможны два случая:
а) все оценки следует, что решение оптимальное
б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение на котором целевая функция будет больше.
а) все оценки следует, что решение оптимальное
б) хотя бы одна оценка и при соответствующей переменной нет положительных коэффициентов, то задача не имеет оптимального решения m, k, целевая функция неограниченна в О.Д.Р.
в) хотя бы одна оценка и при соответствующей переменной есть положительный коэффициент то данное решение можно улучшить, построив новое опорное решение.
4) Новое опорное решение находится с помощью ключевого столбца, ключевой строки и ключевого элемента.
Ключевой столбец указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевая строка указывает на переменную, которую надо вывести из числа базисных для улучшения решения.
Ключевой элемент нужен для элементов нового опорного решения (для новой симплексной таблицы).
Их нахождения зависит от цели задачи.
а) ключевой столбец - это столбец с отрицательной наименьшей оценкой в индексной строке.
б) ключевая строка - это строка с наименьшим отношением свободных членов к положительным коэффициентам ключевого столбца:
в) ключевой элемент - это число расположенное на пересечении ключевых столбца и строки(не может быть равен нулю).
а) ключевой столбец - это столбец с положительной наименьшей оценкой в индексной строке.
б) ключевая строка - это строка с наибольшим отношением свободных членов к положительным коэффициентам ключевого столбца:
в) ключевой элемент - это число расположено на пересечении ключевых столбца и строки.
5) Заполняют первую симплексную таблицу следующим образом:
а) ключевую строку делят на ключевой элемент и записывают на том же месте в новой таблице.
в) остальные элементы пересчитывают по правилу “прямоугольника”:
6) Возвращаются ко второму этапу алгоритма - проверка плана на оптимальность.
§ 4 Построение начального опорного решения методом Гаусса
Приводим задачу к каноническому виду.
Ответ: max Z(X) = 452 при X = (0; 8; 13)
Максимальная прибыль в размере 425 тыс. руб. может быть достигнута, если производить 8 станков ІЙ вида, 13 станков ІЙІ вида и не производить станки Й вида.
При этом расходуется 146 ед. сырья, 120 ед. трудовых ресурсов и 250 ед. накладных расходов.
Данная курсовая работа посвящена вопросу о решении задачи линейного программирования методом последовательного улучшения плана, иначе симплекс - метод. Состоит из введения, двух глав, заключения и списка литературы.
В первой главе рассказывается о линейном программировании в частности, и о том, что такое общая постановка задачи линейного программирования, как составить математическую модель, а также рассказано о канонической форме задач линейного программирования.
Вторая глава работы посвящена практической части решения задачи. Строится математическая модель, решается задача симплексным методом, а также методом Гаусса.
Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения. контрольная работа [118,5 K], добавлен 11.04.2012
Математическое программирование. Линейное программирование. Задачи линейного программирования. Графический метод решения задачи линейного программирования. Экономическая постановка задачи линейного программирования. Построение математической модели. курсовая работа [581,5 K], добавлен 13.10.2008
Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции. курсовая работа [1,1 M], добавлен 21.03.2012
Теоретическая основа линейного программирования. Задачи линейного программирования, методы решения. Анализ оптимального решения. Решение одноиндексной задачи линейного программирования. Постановка задачи и ввод данных. Построение модели и этапы решения. курсовая работа [132,0 K], добавлен 09.12.2008
Применение методов линейного программирования для решения оптимизационных задач. Основные понятия линейного программирования, свойства транспортной задачи и теоремы, применяемые для ее решения. Построение первичного опорного плана и системы потенциалов. курсовая работа [280,8 K], добавлен 17.11.2011
Графическое решение задач. Составление математической модели. Определение максимального значения целевой функции. Решение симплексным методом с искусственным базисом канонической задачи линейного программирования. Проверка оптимальности решения. контрольная работа [191,1 K], добавлен 05.04.2016
Решение задачи линейного программирования табличным симплексным методом и транспортной задачи венгерским методом. Построение имитационной модели гибкого производственного модуля. Алгоритмы автоматизированного проектирования средств вычислительной техники. контрольная работа [117,9 K], добавлен 08.12.2010
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Задача линейного программирования курсовая работа. Программирование, компьютеры и кибернетика.
Сочинение На Тему Затмению Не Подлежит
Реферат по теме Рецензия по истории на книгу Н. Н. Молчанова Дипломатия Петра великого
Реферат: Экспертиза качества макаронных изделий
Фипи Огэ По Химии Контрольная Работа
Религиозное Сочинение От Луки 9 Букв
Реферат: The Gift Outright Essay Research Paper The
Социальное Регулирование Курсовая Работа
Доклад по теме История русско-чеченских отношений
Дипломная работа: Биржи в экономике отрасли. Скачать бесплатно и без регистрации
Реферат: Организация управления предприятием
Курсовая работа: Размышления о гуманной педагогике
Реферат: Парламентаризм и разделение властей в современной России. Скачать бесплатно и без регистрации
Реферат: Архипов Абрам Ефимович
Реферат: Анализ финансовой устойчивости предприятия тяжелой промышленности на примере ОАО СМК
Сочинение Про Маму 9 Класс
Писать Сочинение Мороженое И Утюжок
Книга: Индивидуальная психология как путь к познанию и самопознанию человека, Адлер Альфред
Общественное Мнение Курсовая Работа
Революция в программном обеспечении УЧПУ
Курсовая работа по теме Система подготовки квалифицированных рабочих в Болгарии
Методические особенности изучения темы "Подобные треугольники" в средней общеобразовательной школе - Педагогика дипломная работа
Управління логістикою виробництва та продажу щебеню в ЗАТ "Тальнівський щебзавод" - Менеджмент и трудовые отношения дипломная работа
Ветеринарно-санітарна експертиза риби та інших гідробіонтів - Маркетинг, реклама и торговля презентация