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

Основные понятия математического линейного программирования. Постановка и методы решения заданий целочисленного и параметрического составления программ. Примеры вычисления задач с параметрами в целевой функции и в свободных членах системных ограничений.
Краткое сожержание материала:

Содержание

Введение

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. Целочисленное программирование

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

2.1 Постановка задачи и методы решения

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

Требуется найти минимальное значение линейной функции

(2.1.1)

при ограничениях

(2.1.2)

(2.1.3)

- целые. (2.1.4)

Предположим, что задача линейного программирования имеет многогранник решений, приведенные на рис.2.1. Если наложить требование целочисленности, то допустимое множество решений такой задачи представляет собой совокупность изолированных целочисленных точек и не

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

1) новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка является целой;

2) так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.

Если найти решение задачи (2.1.1)-(2.1.4) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (2.1.1)-(2.1.4) требуется специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори.

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

Недостатком метода Гомори является требование целочисленности для всех переменных: как основных, выражающих единицы продукции, так и для дополнительных, выражающих величину неиспользованных ресурсов, которые могут быть и дробными.

Дополнительное ограничение составляется следующим образом. Пусть оптимальный план получен на базисе ; тогда последняя симплексная таблица имеет следующий вид:

Предположим, что - дробное; тогда некоторые - также дробные (в противном случае задача не имеет целочисленного решения). Обозначим через и целые части чисел и , т. е. наибольшие целые числа, не превосходящие чисел и . Тогда величины дробных частей и чисел и определяются как разности:

где и - неотрицательные.

Так как по условию - неотрицательные целые числа, то и разность

(2.1.5)

также целое неотрицательное число.

Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную , умножи...