Параметрическое программирование пример решения

Параметрическое программирование

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

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

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

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

Пусть коэффициенты целевой функции исходной задачи линейного программирования (2.2) зависят от одного параметра. В задаче (2.2) коэффициенты целевой функции представляют собой цену единицы количества некоторого продукта, а координаты векторов-ограничений могутбыть истолкованы как запасы различных ресурсов.

Читайте также:  Faac c721 программирование пульта

Целевая функция рассматриваемой задачи параметрического программирования может иметь (в простейшем случае) следующий вид:

Параметрическое программирование

где Параметрическое программирование— исходные (старые) коэффициенты задачи линейного программирования; Параметрическое программирование— новые коэффициенты; Параметрическое программирование— параметр, Параметрическое программирование.

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

Рассмотрим случай, когда от параметра зависят координаты системы ограничений. Можно учесть зависимость этих показателей от времени, способа выработки ресурса, района размещения объекта, модель которого рассматривается в задаче и т. п. Условия-ограничения примут вид:

Параметрическое программирование

Параметрическое программирование

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

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

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Рассмотрим метод решения частной задачи линейного параметрического программирования, в которой все коэффициенты целевой функции линейно зависят от некоторого действительного параметра , на конкретном примере:

Параметрическое программирование

В матрично-векторной форме:

Параметрическое программирование

Параметрическое программирование

Для каждого фиксированного значения задача (5.1) становится задачей линейного программирования, которую называют принадлежащей этому значению .

Решением параметрической задачи (5.1) называют явным образом заданную функцию

Параметрическое программирование

решающую функцию задачи (5.1), вместе с набором решающих отношений

Параметрическое программирование

Параметрическое программирование

каждое из значений которых при данном значении равно значениям переменных

Параметрическое программирование

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

Параметрическое программирование

Параметрическое программирование

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

Параметрическое программирование

При любом Для всех значений t из критической области решающая функция линейна и в силу этого непрерывна в области множества значений отношений

Параметрическое программирование

ограничены постоянными величинами; сами эти отношения полунепрерывны сверху.

Параметрическое программирование

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

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Полученная строка подвергается тем же преобразованиям, что и остальные (табл. 5.1; ). Естественно, что в задаче (5.1) мы предварительно перешли к ограничениям-равенст-

Параметрическое программирование

вам и ввели новые переменные Параметрическое программирование. Затри итерации Параметрическое программированиемы получили оптимальное решение при Параметрическое программирование(в табл. 5.1 для каждой итерации выделены разрешающие элементы).

Коэффициенты в целевой функции для выбора разрешающего элемента задаются двумя последними строками при фиксированном (заданном) значении Параметрическое программирование. Для данного допустимого базисного решения надо построить соответствующую критическую область — множество всех значений Параметрическое программирование, при которых это решение будет оптимальным. Это множество будет замкнутым интервалом. Надо найти границы интервала. Их находят по формулам

Параметрическое программирование

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

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

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Из табл.5.1 при следует, что при

Параметрическое программирование

Параметрическое программирование

Это критическое значение может быть превзойдено. В табл. 5.1 при Параметрическое программированиевыбран разрешающий элемент, равный 2/3 при Параметрическое программирование. Общая формула для выбора этой небазисной переменной имеет вид

Параметрическое программирование

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

Параметрическое программирование

Параметрическое программирование

Отыскиваем верхнюю границу области , полагая

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Выбираем разрешающий элемент из столбца для Параметрическое программированиеи получаем новую таблицу при Параметрическое программирование. Из этой таблицы находим новое Параметрическое программирование, превышающее критическое значение Параметрическое программирование= 1/2. При

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

Следующую таблицу строим при Параметрическое программирование. Получаем Параметрическое программирование.

Окончательные результаты приведены в табл. 5.2 и на рис. 5.1, где показаны «вращение» целевой функции, поведение решающей функции Параметрическое программированиеи геометрические образы отношений Параметрическое программирование.

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

Параметрическое программирование

Параметрическое программирование

Параметрическое программирование

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

  1. При Параметрическое программирование-я симплекс-таблица является оптимальной. Полагаем Параметрическое программированиепереходим к п. 2.
  2. Определяем критическое значение Параметрическое программирование

а) если Параметрическое программирование, то достигнута граница области Параметрическое программирование

а’) если Параметрическое программирование, то отыскиваем нижнюю границу области Параметрическое программирование. Полагаем Параметрическое программирование, Параметрическое программированиезаменяем Параметрическое программированиена Параметрическое программированиеи переходим снова к п. 2;

а») если Параметрическое программирование, то отыскиваем верхнюю границу области Параметрическое программирование, после чего переходим к п. 3;

б) если Параметрическое программирование, то определяем возможность превзойти критическое значение выражения для Параметрическое программирование, определяем, иногда подбором из Рис. 5.1. Решение задачи параметрическо-нескольких возможных го линейного программирования значений, новую базисную переменную. В этом случае следует принимать во внимание наличие множества различных решений;

б’) если Параметрическое программирование, то достигнута граница области Параметрическое программирование. Переходим к п. Параметрическое программированиеили Параметрическое программирование;

б» ) в противном случае строим новую симплекс-таблицу. Заменяя Параметрическое программированиена Параметрическое программированиена Параметрическое программирование, снова начинаем вычисления с п. 2.

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

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

1) значение параметра Параметрическое программированиепринадлежит некоторому заранее выбранному интервалу Параметрическое программирование;

2) требуется отыскать только минимум (максимум) функции Параметрическое программированиедля всех Параметрическое программирование, т.е. требуется определить те значения Параметрическое программирование, при которых возможно достижение этого минимума (максимума);

3) требуется отыскать интервал возможных изменений какого-то одного из коэффициентов целевой функции.

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

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

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

Если требуется только определить возможность вариации одного из коэффициентов, то сначала устанавливают, существует ли решение при Параметрическое программирование=0, а затем находят это решение. Вводя параметр сводят проблему к определению значений Параметрическое программирование(равных Параметрическое программирование) и Параметрическое программирование(равных Параметрическое программирование).

Эта теория взята со страницы лекций по предмету «математическое программирование»:

Возможно эти страницы вам будут полезны:

Помощь студентам в учёбе lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal lfirmal

Образовательный сайт для студентов и школьников

Копирование материалов сайта возможно только с указанием активной ссылки «www.lfirmal.com» в качестве источника.

© Фирмаль Людмила Анатольевна — официальный сайт преподавателя математического факультета Дальневосточного государственного физико-технического института

Источник

Задачи параметрического программирования

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word . При этом ограничения типа xi≥0 не учитывайте.

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

Алгоритм решения задач параметрического линейного программирования

  1. Считая значение параметра λ равным некоторому числу λ 0 ∈ [α, β], находим оптимальный план Х * или устанавливаем неразрешимость полученной задачи линейного программирования.
  2. Определяют множество значений параметра λ, для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключаются из рассмотрения.
  3. Полагают значение параметра λ равным некоторому числу, принадлежавшему оставшейся части промежутка [α, β], и находят решение полученной задачи линейного программирования.
  4. Определяют множество значений параметра λ, для которых новый оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяются до тех пор, пока не будут исследованы все значения параметра λ ∈ [α, β].

Источник

Оцените статью