Содержание
Введение
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) так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.--PAGE_BREAK--
Если найти решение задачи (2.1.1)-(2.1.4) симплексным методом, то оно может оказаться как целочисленным, так и нет (примером задачи линейного программирования, решение которой всегда является целочисленным, служит транспортная задача). В общем же случае для определения оптимального плана задачи (2.1.1)-(2.1.4) требуется специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори.
Метод Гомори. Метод решения поставленной задачи, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают, если же оптимальный план содержит хотя бы одну дробную компоненту />, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до получения нового оптимального плана. Если и он является нецелочисленным, то составляют следующее ограничение, учитывающее целочисленность. Процесс присоединения дополнительных ограничений повторяют до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных планов. Это имеет место в случае, если для дробного /> все /> в этой строке окажутся целыми.
Недостатком метода Гомори является требование целочисленности для всех переменных: как основных, выражающих единицы продукции, так и для дополнительных, выражающих величину неиспользованных ресурсов, которые могут быть и дробными.
Дополнительное ограничение составляется следующим образом. Пусть оптимальный план /> получен на базисе />; тогда последняя симплексная таблица имеет следующий вид:
/>
Предположим, что />– дробное; тогда некоторые />– также дробные (в противном случае задача не имеет целочисленного решения). Обозначим через /> и />целые части чисел />и />, т. е. наибольшие целые числа, не превосходящие чисел />и />. Тогда величины дробных частей /> и /> чисел />и />определяются как разности:
/>/>
где />и /> – неотрицательные.
Так как по условию /> — неотрицательные целые числа, то и разность
/>(2.1.5)
также целое неотрицательное число.
Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную />, умножим уравнение на -1, добавим к последней симплексной таблице и, применяя двойственный симплексный метод, находим новый план. Если он не является целочисленным, то по последней симплексной таблице составляем новое дополнительное ограничение.
Если в оптимальном плане несколько дробных />, то дополнительное ограничение составляется для максимального />. Это ускоряет процесс получения оптимального целочисленного решения.
Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы:
Используя симплексный метод, находят решение задачи (2.1.1)-(2.1.3) без учета требования целочисленности переменных.
Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (2.1.1)-(2.1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (2.1.1)-(2.1.4) должна быть целочисленной.
Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительного ограничения.
В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (2.1.1)-(2.1.4) или установления ее неразрешимости.
Метод ветвей и границ. Продолжим рассмотрение задачи (2.1.1)-(2.1.4), состоящей в определении минимального значения линейной функции
/>
при ограничениях
/>
/>— целые.
Как и при решении сформулированной задачи методом Гомори, первоначально надо найти симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план />. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и />.
Если же среди компонент плана /> имеются дробные числа, то /> не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи.
Предположим, что найденный оптимальный план /> не удовлетворяет условию целочисленности переменных, т.е. среди его компонент есть дробные числа. Пусть, например, переменная />приняла в плане /> дробное значение. Тогда в оптимальном целочисленном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу />, либо больше или равно ближайшему большему целому числу />. Определяя эти числа, находим симплексным методом решение двух задач линейного программирования:
/>
/>
При решении задач линейного программирования /> и /> возможен один из следующих четырех случаев:
Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам /> и />.
Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает исходное решение.
Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные/> и />.
4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные /> и />.
Итак, процесс нахождения решения задачи целочисленного программирования (2.1.1)-(2.1.4) методом ветвей и границ включает следующие основные этапы:
1. Находят решение задачи целочисленного программирования (2.1.1)-(2.1.3).
2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (2.1.1)-(2.1.3) является дробным числом.
3. Находят решение задач /> и />, которые получаются из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительных ограничений.
4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам /> и />, и находят их решение. Итерационный процесс продолжается до тех пор, пока не будет найден оптимальный целочисленный план задачи (2.1.1)-(2.1.4). продолжение
--PAGE_BREAK--
2.2 Пример решения задачи целочисленного программирования
Пример 2.2.1. Найти наименьшее значение /> при ограничениях
/>
Решение. Умножим второе неравенство на (-1):
/>
Для того чтобы перейти от неравенств к равенствам, добавим к левым частям неравенств дополнительные переменные:
/>
За базисные переменные примем дополнительные переменные />. тогда свободными переменными являются />. Целевая функция в дополнительных преобразованиях не нуждается, так как уже выражена через свободные переменные. Далее начнем заполнять симплексные таблицы.
Таблица 2.2.1
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
2
-1
1
1
/>
2
-4
2
-1
1
/>
5
3
1
1
С
-1
1
3
Таблица 2.2.2
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
2
-1
1
1
/>
3
-2
1
1
1
/>
4
1
1
-1
1
С
-3
-7
4
Таблица 2.2.3
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
-2
1
1
1
/>
1
3
-2
-1
1
С
-15
1
-7
-4
Таблица 2.2.4
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1 продолжение
--PAGE_BREAK--
/>
11/3
1
-1/3
1/3
2/3
/>
1/3
1
-2/3
-1/3
1/3
С
-46/3
-19/3
-11/3
-1/3
Получили оптимальное решение этой задачи />, в котором /> — дробные. Составим дополнительное ограничение для переменной, имеющей наибольшую дробную часть. Имеем:
/>
/>
/>/>/>
Тогда согласно формуле (2.1.5), дополнительное ограничение имеет вид:
/>
Умножим обе части последнего неравенства на (-1) и преобразуем его в уравнение:
/>
Допишем коэффициенты этого уравнения снизу к таблице 2.2.4, добавим дополнительный столбец, соответствующий переменной />, получим
Таблица 2.2.5
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
11/3
1
-1/3
1/3
2/3
/>
1/3
1
-2/3
-1/3
1/3
/>
-2/3
-2/3
-1/3
-2/3
1
С
-46/3
-19/3
-11/3
-1/3
Применим двойственный симплекс – метод, в результате получим
Таблица 2.2.6
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
1
-1
1
/>
1
-1
-1/2
1/2
/>
1
1
1/2
1
-3/2
С
-15
-6
-7/2
-1/2
Оптимальное целочисленное решение: />
3. Параметрическое программирование
Общая задача линейного программирования содержит постоянные величины: коэффициенты />, /> и свободные члены />. С одной стороны, при определении этих величин на практике встречаются с тем, что в действительности они не являются постоянными, а их значения изменяются в некоторых интервалах; с другой, найдя оптимальный план некоторой экономической задачи при фиксированных значениях />,/>, />, полученных из опыта, необходимо знать, в каких допустимых пределах можно их изменять, чтобы план оставался оптимальным. продолжение
--PAGE_BREAK--
Поэтому возникает необходимость исследовать поведение оптимального решения задачи линейного программирования при изменении ее коэффициентов и свободных членов. Исследования подобного рода составляют предмет параметрического линейного программирования. Параметрическое программирование возникло в связи с изучением задач планирования производства и дает возможность управлять оптимальным планированием различных экономических процессов, которые могут быть описаны линейной математической моделью.
3.1 Задача с параметром в целевой функции
Предположим, что коэффициенты линейной функции /> могут изменяться в некоторых допустимых пределах />, тогда для удобства исследования коэффициенты линейной функции можно заменить выражением />, где /> – постоянные, а t – параметр, изменяющийся в некоторых пределах. В этом случае математическая задача может быть поставлена следующим образом.
Дана линейная функция
/>(3.1.1)
и система линейных ограничений
/>/>(3.1.2)
/>/>
Считая значение параметра /> равным некоторому числу />, находим симплексным методом или методом искусственного базиса решение, полученной таким образом задачи линейного программирования.
В результате при данном значении /> либо найдем оптимальный план задачи, либо установим ее неразрешимость. В первом случае, используя элементы /> – й строки последней симплекс — таблицы решения задачи, в которой записаны числа />, находим:
/>/>/>
/>/>/>
Для всех /> задача имеет один и тот же оптимальный план, что и при />.
В том случае, если задача при /> неразрешима, /> – в строке последней симплекс — таблицы ее решения имеется число />, где />. Тогда:
1) если />, то задача неразрешима для любого />;
2) если />, то задача неразрешима для всех />;
3) если />, то задача неразрешима для всех />.
Определив все значения параметра />, для которых задача имеет один и тот же оптимальный план или для которых задача неразрешима, получаем промежуток изменения параметра />, который исключаем из рассмотрения. Снова полагаем значение параметра /> равным некоторому числу, принадлежащему промежутку, и находим решение полученной задачи.
После каждой итерации определяется либо промежуток, в котором для всех значений параметра задача имеет один и тот же оптимальный план, либо промежуток, в котором для всех значений параметра задача не имеет решения.
Процесс нахождения решения задачи включает следующие этапы:
1. Считая значение параметра /> равным некоторому числу />, находят оптимальный план /> или устанавливают неразрешимость полученной задачи линейного программирования.
2. Определяют множество значений параметра />, для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения.
3. Полагают значения параметра /> равным некоторому числу, принадлежащему оставшейся части промежутка />, и находят решение полученной задачи линейного программирования.
4. Определяют множество значений параметра />, для которых новый оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяют до тех пор, пока не будут исследованы все значения параметра />.
Пример 3.1.1. Для всех значений параметра /> найти максимальное значение функции
/>
при условиях:
/>
Решение. Возьмем (число 0 выбрано произвольно) и найдем симплекс-методом оптимальный план.
Таблица 3.1.1.
БП
СЧ
/>
/>
/>
/>
/>
/>
12
1
1
1
/>
10
1
-1
1
/>
6
-1
1
1
С
-2
/>
Таблица 3.1.2.
БП
СЧ
/>
/>
/>
/>
/>
/>
6 продолжение
--PAGE_BREAK--
2
1
/>
16
1
/>
6
-1
1
1
С
/>
/>
/>
Таблица 3.1.3.
БП
СЧ
/>
/>
/>
/>
/>
/>
3
1
1/2
-1/2
/>
16
1
1
/>
9
1
1/2
1/2
С
/>
/>
/>
Определим значения />, при которых план, соответствующий таблице 3.1.3, останется оптимальным:
/>/>/>
Следовательно, при /> задача имеет оптимальное решение: /> Возьмем />. Тогда столбец /> – разрешающий. Переходим к новому опорному плану:
Таблица 3.1.4.
БП
СЧ
/>
/>
/>
/>
/>
/>
11
1
1/2
1/2
/>
16
1
1
/>
1
1
1/2
-1/2
С
/>
/>
/>
Этот план оптимален при условии:
/>/>/>
Следовательно, при />При /> имеем:
Таблица 3.1.5.
БП
СЧ
/>
/>
/>
/>
/>
/>
10
1
-1
1
/>
16
1
1
/>
2
2
1
-1
С
20
/>
2
Этот план оптимален при условии: />. Следовательно, при /> продолжение
--PAGE_BREAK--
2. Задача с параметром в свободных членах системы ограничений
Дана линейная функция и система линейных ограничений
/>(3.2.1)
/>/>(3.2.2)
/>/>
Алгоритм решения задачи (3.2.1)-(3.2.2) подобен рассмотренному выше алгоритму решения задачи (3.1.1)-(3.1.2). Полагая значение параметра /> равным некоторому числу />, находим решение полученной задачи линейного программирования. При данном значении параметра /> либо определяем оптимальный план задачи, либо установим ее неразрешимость. В первом случае найденный план является оптимальным для любого />, где
/>/>/>
/>/>/>
и числа /> и /> определены компонентами оптимального плана и зависят от />:
/>/>.
Если при /> задача (3.2.1) — (3.2.2) неразрешима, то либо целевая функция задачи (3.2.1) не ограничена на множестве планов, либо система уравнений (3.2.2) не имеет неотрицательных решений. В первом случае задача неразрешима для всех />, а во втором случае определяем все значения параметра />, для которых система уравнений (3.2.2) несовместна, и исключаем их из рассмотрения. После определения промежутка, в котором задача (3.2.1) — 3.2.2) имеет один и тот же оптимальный план или неразрешима, выбираем новое значение параметра />, не принадлежащее найденному промежутку, и находим решение полученной задачи линейного программирования. При этом решение новой задачи ищем с помощью двойственного симплекс-метода. Продолжая итерационный процесс, после конечного числа шагов получаем решение задачи (3.2.1) — (3.2.2). Итак, процесс нахождения решения задачи (3.2.1) — (3.2.2) включает следующие основные этапы:
1. Считая значение параметра /> равным некоторому числу />, находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.
2. Находят значения параметра />, для которых задача (3.2.1) — (3.2.2) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра исключают из рассмотрения.
3. Выбирают значения параметра /> из оставшейся части промежутка /> и устанавливают возможность определения нового оптимального плана. В случае существования оптимального плана находят его двойственным симплекс-методом..
4. Определяют множество значений параметра />, для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра />.
Пример 3.2.1. Для каждого значения параметра найти максимальное значение функции
/>
/>
Решение. Считая />, находим решение:
Таблица 3.2.1.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
1
1
/>
/>
2
-1
1
/>
/>
-2
2
1
С
/>
10
-1
Таблица 3.2.2.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
2
1
-1/2
/>
/>
1
1
1/2
/>
/>
-1
1
1/2
С
/>
9
1/2
Оптимальный план при />: /> Этот план будет оставаться оптимальным, пока среди его компонент не окажется отрицательного числа:
/>/>/>. продолжение
--PAGE_BREAK--
Следовательно, при />/> Исследуем, имеет ли задача оптимальные планы при />. Если />, то /> и, следовательно, /> не является планом задачи. Поэтому надо перейти к новому плану. Это можно сделать, когда в строке /> имеются отрицательные числа. В данном случае это условие выполняется. Переходим к оптимальному плану, применяя двойственный симплекс-метод.
Таблица 3.2.3.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
2
1
1/2
/>
/>
1
1
1
/>
/>
1
-1
-1/2
С
/>
9
5
/>Этот план остается оптимальным при
/>/>/>.
Если />, то это решение не является планом, так как />. Так как в строке /> нет отрицательных чисел, то исходная задача неразрешима.
При />, /> не является планом, так как />. С помощью таблицы 3.2.2 переходим к следующему решению:
Таблица 3.2.4.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
-4
-2
1
/>
/>
3
1
1
/>
/>
1
1
1
С
/>
11
1
/>Этот план оптимален при условии />. При /> задача неразрешима, так как в строке /> нет отрицательных чисел.
3. Задача, целевая функция и правая часть ограничений которой содержит параметр
Пример 3.3.1. Для всех значений параметра найти максимальное значение функции
/>
/>
Решение. Пусть />. Находим симплекс-методом решение задачи.
Таблица 3.3.1.
БП
СЧ
/>
/>
/>
/>
/>
/>
1
-1
1
/>
/>
-1
2
1
С
/>
/>
/>
Таблица 3.3.2.
БП
СЧ
/>
/>
/>
/> продолжение
--PAGE_BREAK----PAGE_BREAK--
1
2
-1
1
1
/>
2
-4
2
-1
1
/>
5
3
1
1
С
/>+1
1
3+4/>
Таблица 4.1.2.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
2
-1
1
1
/>
3
-2
1
1
1
/>
4
1
1
-1
1
С
-3/>
/>
/>
-3/>
Таблица 4.1.3.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
-2
1
1
1
/>
1
3
-2
-1
1
С
-15/>
/>
/>
/>
Таблица 4.1.4.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
11/3
1
-1/3
1/3
2/3
/>
1/3
1
-2/3
-1/3
1/3
С
/>
/>
/>
/>
Определим значения параметра t, при которых план, соответствующий таблице 4.1.4 останется оптимальным:
/>/>/>. продолжение
--PAGE_BREAK--
Следовательно, при /> задача имеет оптимальное решение: />, />. Оно не является целочисленным: /> — дробные. Составим дополнительное ограничение для переменной />. Имеем:
/>,
/>, />, />, />.
/>,
/>.
Таблица 4.1.5.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
11/3
1
-1/3
1/3
2/3
/>
1/3
1
-2/3
-1/3
1/3
/>
-2/3
-2/3
-1/3
-2/3
1
С
/>
/>
/>
/>
Применим двойственный симплекс-метод. Получим:
Таблица 4.1.6.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
1
-1
1
/>
1
-1
-1/2
1/2
/>
1
1
1/2
1
-3/2
С
/>
/>
/>
/>
Получили целочисленное решение. Рассмотрим, при всех ли />
/>/>/>.
Следовательно, при /> получили оптимальное целочисленное решение />, />. Найдем оптимальное целочисленное решение для />.
Из таблицы 4.1.6 получим
Таблица 4.1.7.
БП
СЧ
/>
/>
/>
/>
/>
/>
/> продолжение
--PAGE_BREAK--
/>
2
1
1
-2
3
/>
4
1
1/2
1
-1/2
/>
1
1
1
-1
/>
1
1
1/2
1
-3/2
С
/>
-1/2
/>
/>
Получили целочисленное решение, посмотрим, является ли оно оптимальным:
/>/>/>.
Следовательно, для /> оптимальное целочисленное решение: />, />. Найдем оптимальное решение задачи для значений параметра />. Пусть />, тогда получим разрешающий столбец — />, разрешающая строка — />. Проведем одну итерацию, получим
Таблица 4.1.8.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
-2
1
1
1
/>
1
3
-2
-1
1
С
-/>
/>
/>
/>
Решение целочисленное. Определим />, при которых план остается оптимальным
/>/>/>
Следовательно, для /> оптимальное целочисленное решение />, />. Найдем оптимальное решение задачи без условия целочисленности для значений параметра />. Пусть />, разрешающий столбец — />, разрешающая строка — />. Проведем одну итерацию
Таблица 4.1.9.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
2
1/2
1
1/2
/>
13/3
1
1/6
1/2
2/3
/>
5/3
1
1/3
1/3
С
/>
/>
-1/2
/>
Определим значения параметра />, при которых план остается оптимальным
/>/>/>. продолжение
--PAGE_BREAK--
Решим с условием целочисленности. /> и /> — дробные. Составим дополнительное ограничение для переменной />.
/>,
/>, />, />, />.
/>,
/>.
Таблица 4.1.10.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
2
1/2
1
1/2
/>
13/3
1
1/6
1/2
2/3
/>
5/3
1
1/3
1/3
/>
-1/3
-1/6
-1/2
-2/3
1
С
/>
/>
-1/2
/>
Таблица 4.1.11.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
2
1/2
1
1/2
/>
4
1
1
/>
3/2
1
1/4
-1/4
1/2
/>
1/2
1/4
3/4
1
-3/2
С
/>
/>
/>
/>
/>и /> — дробные. Составим дополнительное ограничение для />:
/>, />.
Таблица 4.1.12.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
/>
2
1/2
1
1/2
/>
4 продолжение
--PAGE_BREAK--
1
1
/>
3/2
1
1/4
-1/4
1/2
/>
1/2
1/4
3/4
1
-3/2
/>
-1/2
-1/4
-3/4
-1/2
1
С
/>
/>
/>
/>
Таблица 4.1.13.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
/>
2
1/2
1
1/2
/>
3
1
1/2
-3/2
2
/>
1
1
-1
1
/>
2
1
3
1
-3
/>
1
1/2
3/2
1
-2
С
/>
/>
/>
/>
/>/>система не имеет решения.
Получили, что не существует такого значения параметра />, при которых данное целочисленное решение являлось бы оптимальным. Следовательно, для /> не существует оптимального целочисленного решения. Интервалами оптимальности целочисленных планов для различных значений параметра являются:
/>— планы не существуют;
/>— />, />.
/>— />, />.
Основные этапы решения задачи параметрического целочисленного программирования:
1. При /> находят оптимальный план без условия целочисленности или устанавливают неразрешимость задачи.
2. Находят значения />, для которых задача имеет один и тот же план, или неразрешима.
3. Если найденный оптимальный план целочисленный, то переходят к следующему пункту. Если найденный оптимальный план не целочисленный, то вводят дополнительное ограничение и вычисления продолжают до получения нового оптимального плана. Если и он является не целочисленным, то вводят новое ограничение. Процесс продолжают до тех пор, пока не будет найден целочисленный оптимальный план, или будет доказано, что задача не имеет целочисленного оптимального решения. Находят значения />, для которых задача имеет одно и то же целочисленное оптимальное решение, или неразрешима.
4. Выбирают /> из оставшейся части /> и устанавливают возможность определения нового оптимального плана. Если он не целочисленный, то его приводят к целочисленному или доказывают, что задача не имеет целочисленного оптимального решения.
5. Вычисления продолжают до тех пор, пока не будут исследованы все значения параметра />.
II способ. При решении предыдущего примера мы, после нахождения оптимального плана, сначала находили значения параметра />, при которых план оставался оптимальным, и только потом приводили решение задачи к целочисленному виду. Попробуем при решении этой задачи сначала найти целочисленное оптимальное решение, а потом определить удовлетворяющий этому решению промежуток значения />. Перейдем от неравенств к равенствам, добавляя к левым частям неравенств дополнительные переменные: продолжение
--PAGE_BREAK--
/>
Возьмем />(число 0 выбрано произвольно) и найдем симплекс-методом оптимальный план.
Таблица 4.2.1.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
2
-1
1
1
/>
2
-4
2
-1
1
/>
5
3
1
1
С
/>+1
1
3+4/>
Таблица 4.2.2.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1
2
-1
1
1
/>
3
-2
1
1
1
/>
4
1
1
-1
1
С
-3/>
/>
/>
-3/>
Таблица 4.2.3.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
-2
1
1
1
/>
1
3
-2
-1
1
С
-15/>
/>
/>
/>
Таблица 4.2.4.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
11/3
1
-1/3
1/3
2/3 продолжение
--PAGE_BREAK--
/>
1/3
1
-2/3
-1/3
1/3
С
/>
/>
/>
/>
План оптимальный, но не целочисленный. Составим дополнительное ограничение для переменной />:
/>,
/>, />, />, />.
Дополнительное ограничение имеет вид:
/>,
/>.
Таблица 4.2.5.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
11/3
1
-1/3
1/3
2/3
/>
1/3
1
-2/3
-1/3
1/3
/>
-2/3
-2/3
-1/3
-2/3
1
С
/>
/>
/>
/>
Применим двойственный симплекс-метод. Получим:
Таблица 4.2.6.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
1
-1
1
/>
1
-1
-1/2
1/2
/>
1
1
1/2
1
-3/2
С
/>
/>
/>
/>
Получили оптимальное целочисленное решение при />, найдем значения />, при которых остается тот же план:
/>/>/>.
Следовательно, при /> получили оптимальное целочисленное решение />, />. Найдем оптимальное целочисленное решение для />. Пусть />.
Таблица 4.2.7. продолжение
--PAGE_BREAK--
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4
1
2
1
/>
3
-2
1
1
1
/>
2
-2
-1
1
/>
1
3
-2
-1
1
С
/>
/>
/>
/>
Получили оптимальное целочисленное решение при />, найдем значения />, при которых остается тот же план:
/>/>/>
Следовательно, при /> получили оптимальное целочисленное решение />, />. Найдем оптимальное целочисленное решение задачи для значений параметра />. Вернемся к таблице 4.2.6. Пусть />, тогда разрешающий столбец — />, разрешающая строка — />. Получим:
Таблица 4.2.8.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
2
1
-2
3
/>
4
1
1/2
1
-1/2
/>
1
1
1
-1
/>
1
1
1/2
1
-3/2
С
-7t-9
-1/2
9t+6
(-26t-19)/2
Получили целочисленное решение задачи, найдем значения параметра, при которых оно оптимально:
/>/>/>.
Следовательно, при /> получили оптимальное целочисленное решение />, />. Если />, то в строке С столбца /> будет положительный элемент. Переходим к следующей таблице.
Таблица 4.2.9.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
2/3
1/3
-2
1 продолжение
--PAGE_BREAK----PAGE_BREAK----PAGE_BREAK--
2
1/2
1
1/2
3
/>
2
1
3
1
3
/>
1
1/2
3/2
1
-2
С
t-7
(8t+7)/2
(-2t+1)/2
t-1
Решение целочисленное, посмотрим, при каких значениях параметра t оно оптимально:
/>/>система не имеет решения.
Следовательно, для /> не существует оптимального целочисленного решения. Интервалами оптимальности целочисленных планов для различных значений параметра являются:
/>— планы не существуют;
/>— />, />.
/>— />, />.
2. Пример решения задачи целочисленного программирования с параметром в свободных членах системы ограничений
Пример 4.2.1 Для каждого значения /> найти неотрицательное решение, минимизирующее линейную функцию /> при ограничениях
/>
/>, />.
Решение. Перейдем от неравенств к равенствам, добавляя к левым частям неравенств дополнительные переменные:
/>
/>, />.
Возьмем /> и найдем симплекс-методом оптимальный план.
Таблица 4.3.1.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1+t
2
-1
1
1
/>
2
-4
2
-1
1
/>
5
3
1
1
С
-1
1
3
Таблица 4.3.2.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
1+t
2
-1
1
1
/>
3+t
-2
1
1
1
/>
4-t
1
1
-1
1
С
-3-3t
-7
4
-3
Таблица 4.3.3. продолжение
--PAGE_BREAK--
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4+2t
1
2
1
/>
3+t
-2
1
1
1
/>
1-2t
3
-2
-1
1
С
-15-7t
1
-7
-4
Таблица 4.3.4.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
4+2t
1
2
1
/>
(11-t)/3
1
-1/3
1/3
2/3
/>
(1-2t)/3
1
-2/3
-1/3
1/3
С
/>
-19/3
-11/3
-1/3
Решение />, /> оптимально и целочисленное при />. Пусть />. Тогда решение не является целочисленным. Составим дополнительное ограничение:
/>,
/>, />, />, />.
Дополнительное ограничение имеет вид:
/>,
/>.
Таблица 4.3.5.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
4+2t
1
2
1
/>
(11-t)/3
1
-1/3
1/3
2/3
/>
(1-2t)/3
1
-2/3
-1/3
1/3
/>
-2/3
-2/3
-1/3
-2/3
1
С
/>
-19/3
-11/3
-1/3 продолжение
--PAGE_BREAK----PAGE_BREAK--
1
-1/2
-1/2
/>
-1/2
-1/2
-1/2
-1/2
1
С
111/6
-19/2
-1/2
-7/2
Таблица 4.3.9.
БП
СЧ
/>
/>
/>
/>
/>
/>
/>
/>
5
3
1
1
/>
3
-1
1
1
/>
t-1
-2
1
-1
1
/>
1
1
1
1
-2
С
114/6
-9
-3
-1
Получили оптимальное целочисленное решение />, /> для />. Рассмотрим значения параметра />. Вернемся к таблице 4.3.4. Если подставить любое /> из этого промежутка, то получим, что свободный член при переменной /> отрицателен, но в этой строке нет отрицательных коэффициентов, поэтому задача не имеет решения на этом промежутке.
Интервалами оптимальности целочисленных планов для различных значений параметра являются: /> — планы не существуют;
/>— />, />.
/>— />, />.
/>— />, />.
Заключение
Отдельными классами задач математического программирования являются задачи целочисленного, параметрического и дробно – линейного программирования. В данной работе были рассмотрены задачи комбинированного типа, а именно задачи целочисленного параметрического программирования.
Определены основные этапы решения задачи целочисленного программирования с параметром в целевой функции. Рассмотрены алгоритмы решения задач целочисленного программирования с параметром в целевой функции и задач целочисленного программирования с параметром в системе ограничений, приведены соответствующие примеры. По результатам работы подготовлена и сдана в печать статья «Решение задачи целочисленного параметрического программирования». Основные этапы работы были представлены в виде доклада на итоговой научной конференции студентов ФМФ ЧГПУ им. И.Я.Яковлева по секции «Алгебра».
Список литературы
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. – М.: Высшая школа, 1980. – 300 с.
Копылов В.И. Лекции и практические занятия по математическому программированию. – Учебное пособие. – Чебоксары: Чувашский государственный педагогический университет имени И.Я.Яковлева, 2005. – 109 с.
Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. –
Ашманов С.А. Линейное программирование. М.: Наука, 1981. – 304 с.
Юдин Д.Б., Гольдштейн Е.Г. Линейное программирование. — М.: Физматлит, 1963. – 776 с.
Васильев Ф.П., Иваницкий А.Ю. Линейное программирование. — М.: Факториал, 2003. — 347с.