Методы и способы решения задач целочисленного параметрического программирования

Содержание
Введение
1. Основные понятия линейного программирования
2. Целочисленное программирование
2.1 Постановка задачи и методы решения
2.2 Пример решения задачи целочисленного программирования
3. Параметрическое программирование
3.1 Задача с параметром в целевой функции
3.2 Задача с параметром в свободных членах системы ограничений
3.3 Задача, целевая функция и правая часть ограничений которой содержит параметр
4. Целочисленное параметрическое программирование
4.1 Пример решения задачи целочисленного программирования с параметром в целевой функции
4.2 Пример решения задачи целочисленного программирования с параметром в свободных членах системы ограничений
Заключение
Список литературы

Введение
Математическое программирование представляет собой математическую дисциплину, занимающуюся изучением экстремальных задач и разработкой методов их решения.
В общем виде математическая постановка экстремальной задачи состоит в определении наибольшего или наименьшего значения целевой функции при условиях , где и – заданные функции, а – некоторые действительные числа.
В зависимости от свойств функций и математическое программирование можно рассматривать как ряд самостоятельных дисциплин, занимающихся изучением и разработкой методов решения определенных классов задач.
Прежде всего задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции и линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.
Наиболее изученным разделом математического программирования является линейное программирование. Для решения задач линейного программирования разработан целый ряд эффективных методов, алгоритмов и программ.
Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно-линейного программирования.
В первой главе данной работы рассмотрены основные понятия линейного программирования.
Во второй главе сформулирована задача целочисленного программирования и рассмотрены методы её решения. Приведён пример решение задачи целочисленного программирования.
В третьей главе рассмотрены задачи параметрического программирования и на примерах показаны методы решения различных задач этого типа.
В четвертой главе сформулированы и исследованы задачи целочисленного параметрического программирования. Самостоятельно была решена задача целочисленного параметрического программирования с параметром в целевой функции двумя способами. На основе решения данной задачи определен метод решения задач такого типа. Также решена задача целочисленного программирования с параметром в свободных членах системы ограничений.
При написании диплома использовалась следующая справочная литература: Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование, Ашманов С.А. Линейное программирование. Некоторые примеры были взяты из книг Копылов В.И. Лекции и практические занятия по математическому программированию, Акулич И.Л. Математическое программирование в примерах и задачах. Алгоритмы методов решения задач целочисленного и параметрического программирования наиболее доступно и полно, на мой взгляд, раскрываются в книге Акулич И.Л.

1. Основные понятия линейного программирования
Различают три основные формы задач линейного программирования в зависимости от ограничений разного типа.
Стандартная задача линейного программирования имеет вид:
(1.1)
(1.2)
В матричной форме задача (1.1) - (1.2) имеет вид:
где - матрица коэффициентов. Вектор называют вектором коэффициентов линейной формы, вектор – вектором ограничений.
Каноническая задача линейного программирования имеет вид:

или, в матричной форме:
Общая задача линейного программирования – часть ограничений выражается в виде неравенств, часть – в виде уравнений. Кроме того, не ко всем переменным относится условие неотрицательности:
Теорема. Стандартная, каноническая и общая задачи линейного программирования эквивалентны.
Замечание. Тот случай, когда в стандартной задаче требуется минимизировать линейную форму, легко сводится к задаче на максимум – следует рассмотреть задачу на максимум функции при тех же ограничениях на переменные, что и в исходной задаче.

2. Целочисленное программирование
Значительная часть экономических задач, относящихся к задачам линейного программирования, требует целочисленного решения. К ним относятся задачи, у которых переменные величины означают количество единиц неделимой продукции, например распределение производственных заданий между предприятиями, раскрой материалов, загрузка оборудования, распределение судов по линиям, самолетов по рейсам, а также задачи по производству неделимой продукции. Если единица составляет малую часть всего объема производства, то оптимальное решение находят обычным симплексным методом, округляя его до целых единиц, исходя из смысла задачи. В противном случае округление может привести к решению, далекому от оптимального целочисленного решения.

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию