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

Главное правление образования Курганской области

ГБПОУ «Шадринский политехнический колледж»

 

 

Руководитель МСО

                                                                                           __________ Плещеева Л.А

«___»____________2014 г.

 

 

 

 

Курсовая работа

по дисциплине «Математические методы»

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

 

 

 

 

 

 

 

Студент:______________/Глазов М. Е./

  Руководитель:__________/Ханина  О. В./

 

 

 

 

 

 

Шадринск, 2014 г.

Содержание.

 

1. Введение…………………………………………………………………3стр.
2. Основные понятия линейного программирования……………………4стр.
3. Параметрическое программирование………………………………….5стр.

 

Содержание

 

Введение

Глава 1

1.1 Основные понятия линейного программирования

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

Заключение

Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

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

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

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

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

Нами были рассмотрены задачи параметрического программирования и на примерах показаны методы решения различных задач этого типа.

 

 

Линейное программирование

Линейное программирование — математическая дисциплина, посвященная теории и методам решения задач об экстремумах линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.

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

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

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

 

Математическая формулировка задачи линейного программирования:

Нужно максимизировать

при условиях

 при  .

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

Такую задачу называют "основной" или "стандартной" в линейном программировании.

Примеры задач линейного программирования:

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

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

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

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

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

Транспортная задача 

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

Ограничениями будут   и

.

Целевая функция имеет вид:  , которую надо минимизировать.

Алгоритмы решения общей задачи линейного программирования

 

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 г. советским математиком Л.Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешенной. Метод эллипсоидов имеет совершенно другую, некомбинаторную, природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным. Тем не менее сам факт полиномиальной сложности задач привел к созданию целого класса эффективных алгоритмов ЛП - методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 г. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования , разработанные в 60-х гг. Fiacco и McCormick.

 

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

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

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

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

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

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

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

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

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

Отыскать максимум (или минимум) функции:

L(X, λ) =

при условиях

,   Xj ≥ 0,    

Если обратиться к геометрической интерпретации задачи, то можно заметить, что вектор-градиент линейной формы определяется её параметром. Например, для целевой функции L(X, λ) = λX1 + (1-λ)X2 при различных значениях параметра λ градиент определяет различные направления роста функции.

Нетрудно видеть, что, если при некотором значении параметра максимум достигается  в вершине A, то небольшая вариация этого значения несколько изменит направление градиента, но не изменит положение точки максимума. Отсюда напрашивается вывод, что некоторый план, оптимальный при λ = λ0 оптимален и в окрестности λ0, т.е. при α ≤ λ ≤ β где λ0  ∈ [α, β].

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

В случае неограниченности множества планов можно утверждать, что если линейная форма не ограничена при λ = λ0, то она не ограничена при всех λ, больших или меньших λ0.

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

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

L(X) =

при условиях

,   Xj ≥0,   j = 1 ... n;   

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

Пример 1. Рассмотрим задачу минимизации

L(X, λ) = λX1 - λX2 - λX3 + λX4

при условиях

3X1 - 3X2 - X3 + X4 ≥ 5;

2X1 - 2X2 + X3 - X4 ≤ 3;

Xk ≥ 0,   k = 1 ... 4;    -∞ < λ < ∞.

Решение. Как обычно, приводим задачу к канонической форме и с использованием метода искусственного базиса отыскиваем начальный опорный план X0 = (0, 0, 0, 0, 0, 3, 5) c L(X0, λ) = 5M.