Решить задачу параметрического программирования графическим способом

Нахождение решения задачи параметрического программирования

Для всех t≤t≤ t задача (1)-(3) имеет один и тот же оптимальный план, что и при t₀.
В том случае, если задача (1)-(3) при t₀ неразрешима, в (m+1)-й строке последней симплекс-таблицы ее решения имеется число Δ_k= Δ’_k+t₀Δ’’_k 0, то задача (1)-(3) неразрешима для всех t>t₁.
Определив все значения параметра t∈[α, β], для которых задача (1)-(3) имеет один и тот же оптимальный план или для которых задача неразрешима, получаем промежуток изменения параметра t, который исключаем из рассмотрения. Снова полагаем значение параметра t равным некоторому числу, принадлежащему промежутку [α,β], и находим решение полученной задачи.
После каждой итерации определяется либо промежуток, в котором для всех значений параметра задача имеет один и тот же оптимальный план, либо промежуток, в котором для всех значений параметра задача не имеет решения.
Итак, процесс нахождения решения задачи (1)-(3) включает следующие этапы:
1 0 . Считая значение параметра t равным некоторому числу t₀∈[α, β], находим оптимальный план X * или устанавливают неразрешимость полученной задачи линейного программирования.
2 0 . Определяют множество значений параметра t∈[α, β], для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключают из рассмотрения.
3 0 . Полагают значение параметра t равным некоторому числу, принадлежащему оставшейся части промежутка [α,β], и находят решение полученной задачи линейного программирования.
4 0 . Определяют множество значений параметра t, для которых новый оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяют до тех пор, пока не будут исследованы все значения параметра t∈[α, β].

Источник

Графический метод решения задач с параметрами

Теперь вы узнали, что такое параметр, и увидели решение самых простых задач.

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

Вот список тем, которые стоит повторить:

1. Элементарные функции и их графики. Парабола, синус, логарифм, арктангенс и все остальные — всех их надо знать «в лицо».

Только после этого можно переходить к самому простому и наглядному способу решения задач с параметрами — графическому. Конечно, он не единственный. Но начинать лучше всего именно с него.

Мы разберем несколько самых простых задач, решаемых графическим методом. Больше задач — в видеокурсе «Графический метод решения задач с параметрами» (бесплатно).

1. При каких значениях параметра a уравнение имеет ровно 2 различных решения?

Дробь равна нулю тогда и только тогда, когда ее числитель равен нулю, а знаменатель не равен нулю.

В первом уравнении выделим полный квадрат:

Это уравнение окружности с центром в точке и радиусом равным 2. Обратите внимание — графики будем строить в координатах х; а.

Уравнение задает прямую, проходящую через начало координат. Нам нужны ординаты точек, лежащих на окружности и не лежащих на этой прямой.

Для того чтобы точка лежала на окружности, ее ордината а должна быть не меньше 0 и не больше 4.

Кроме того, точка не должна лежать на прямой , которая пересекает окружность в точках и Координаты этих точек легко найти, подставим в уравнение окружности.

Точка С также не подходит нам, поскольку при мы получим единственную точку, лежащую на окружности, и единственное решение уравнения.

2. Найдите все значения a, при которых уравнение имеет единственное решение.

Уравнение равносильно системе:

Мы возвели обе части уравнения в квадрат при условии, что (смотри тему «Иррациональные уравнения»).

Раскроем скобки в правой части уравнения, применяя формулу квадрата трехчлена. Получаем систему.

Приводим подобные слагаемые в уравнении.

Заметим, что при прибавлении к правой и левой части числа 49 можно выделить полные квадраты:

Решим систему графически:

Уравнение задает окружность с центром в точке , где радиус

Неравенство задает полуплоскость, которая расположена выше прямой , вместе с самой этой прямой.

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

Пусть С — точка касания.

На координатной плоскости отметим точки и , в которых прямая пересекает оси Y и Х.

Рассмотрим треугольник ABP. Он прямоугольный, и радиус окружности PC является медианой этого треугольника. Значит по свойству медианы прямоугольного треугольника, проведенной к гипотенузе.

Из треугольника ABP найдем длину гипотенузы AB по теореме Пифагора.

Решая это уравнение, получаем, что

3. Найдите все положительные значения параметра а, при каждом из которых система имеет единственное решение.

График уравнения — окружность с центром и радиусом равным 2.

График уравнения — две симметричные окружности и радиуса 2 c центрами в точках и

Второе уравнение при задает окружность с центром в точке и радиусом a.

Вот такая картинка, похожая на злую птицу. Или на хрюшку. Кому что нравится.

Система имеет единственное решение в случаях, когда окружность , задаваемая вторым уравнением, касается только левой окружности или только правой

Если a — радиус окружности , то это значит, что (только правая) или (только левая).

Пусть А — точка касания окружности и окружности

, (как гипотенуза прямоугольного треугольника МNР с катетами 3 и 4),

В — точка касания окружности и окружности

длину MQ найдем как гипотенузу прямоугольного треугольника KMQ с катетами 7 и 4; Тогда для точки В получим:

Есть еще точки С и D, в которых окружность касается окружности или окружности соответственно. Однако эти точки нам не подходят. В самом деле, для точки С:

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

Аналогично, для точки D:

и значит, окружность с центром М, проходящая через точку D, будет пересекать правую окружность и система будет иметь три решения.

4. При каких значениях a система уравнений имеет 4 решения?

Конечно же, решаем графически. Только непуганый безумец возьмется решать такую систему аналитически : -)

И в первом, и во втором уравнении системы уже можно разглядеть известные «базовые элементы» (ссылка) — в первом ромбик, во втором окружность. Видите их? Как, еще нет? — Сейчас увидите!

Просто выделили полный квадрат во втором уравнении.

Сделаем замену Система примет вид:

Вот теперь все видно! Рисовать будем в координатах

Графиком первого уравнения является ромб, проходящий через точки с координатами и

Графиком второго уравнения является окружность с радиусом и центром в начале координат.

Когда же система имеет ровно 4 решения?

1) В случае, когда окружность вписана в ромб, то есть касается всех сторон ромба.

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

Диагонали нашего ромба равны 8 и 6. Значит,

Сторону ромба найдем по теореме Пифагора. Видите на рисунке прямоугольный треугольник со катетами 3 и 4? Да, это египетский треугольник, и его гипотенуза, то есть сторона ромба, равна 5. Если h — высота ромба, то

При этом Мы помним, что если окружность вписана в ромб, то диаметр этой окружности равен высоте ромба. Отсюда

Мы получили ответ:

2) Есть второй случай, и мы его найдем.

Давайте посмотрим — если уменьшить радиус окружности, сделав , окружность будет лежать внутри ромба, не касаясь его сторон. Система не будет иметь решений, и нам это не подходит.

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

Пусть радиус окружности равен 3. Тогда система имеет 6 решений.

А что, если ? Окружность пересекает каждую сторону ромба ровно 1 раз, всего 4 решения. Подходит!

Значит, Объединим случаи и запишем ответ:

Больше задач и методов решения — на онлайн-курсе Анны Малковой. И на интенсивах ЕГЭ-Студии в Москве.

Источник

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

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)

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

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

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

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

1. Используя симплексный метод, находят решение задачи (2.1.1)-(2.1.3) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (2.1.1)-(2.1.3) имеет максимальное дробное значение, а в оптимальном плане задачи (2.1.1)-(2.1.4) должна быть целочисленной.

3. Используя двойственный симплекс-метод, находят решение задачи, получающейся из задачи (2.1.1)-(2.1.3) в результате присоединения дополнительного ограничения.

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

Метод ветвей и границ. Продолжим рассмотрение задачи (2.1.1)-(2.1.4),состоящей в определении минимального значения линейной функции

— целые.

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

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

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

При решении задач линейного программирования и возможен один из следующих четырех случаев:

1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.

2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам и .

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

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

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).

2.2 Пример решения задачи целочисленного программирования

Пример 2.2.1 . Найти наименьшее значение при ограничениях

Решение . Умножим второе неравенство на (-1):

Для того чтобы перейти от неравенств к равенствам, добавим к левым частям неравенств дополнительные переменные:

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

Источник

Название: Методы и способы решения задач целочисленного параметрического программирования Раздел: Рефераты по информатике Тип: дипломная работа Добавлен 02:33:02 14 декабря 2010 Похожие работы Просмотров: 587 Комментариев: 18 Оценило: 2 человек Средний балл: 5 Оценка: неизвестно Скачать