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



Скачать 200.87 Kb.
страница1/3
Дата02.01.2013
Размер200.87 Kb.
ТипДокументы
  1   2   3
Параметрическое линейное программирование
Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых целевая функция или ограничения зависят от одного или нескольких параметров.

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

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

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

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

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



при условиях



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



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

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


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

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

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

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

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

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

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

Задача линейного программирования с параметрами целевой функции.

Пусть . Введем .

где

Для первого интервала , для остальных , где

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

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

Задача 1. Предприятие должно выпустить два вида продукции А и В, для изготовления которых используется три вида сырья, нормы расходов заданы в таблице. Известно, что цена на А единицу продукции может изменяться от 2 до 12 у.е., для В от 13 до 3 у.е. Найти оптимальные планы выпуска для заданных интервалов цен.




А

В

Запасы

1

4

1

16

2

2

2

22

3

6

3

36









х1

х2

х3

х4

х5

bi

х3

4

1

1

0

0

16

х4

1

1

0

1

0

11

х5

2

1

0

0

1

12



-2-

-13

0

0

0

0



Решение начинаем при =0




х1

х2

х3

х4

х5

bi

х4

4

1

1

0

0

16

х5

1

1

0

1

0

11

х5

2

1

0

0

1

12



-2-

-13

0

0

0

0





х1

х2

х3

х4

х5

bi

х3

3

0

1

-1

0

5

х2

1

1

0

1

0

11

х5

1

0

0

-1

1

1



11-2

0

0

13-

0

143-11
  1   2   3

Похожие:

Параметрическое линейное программирование iconЛинейное программирование
Царегородцев Л. И., Каргин Ю. Н., Царегородцева В. В. Линейное программирование: Методические указания и контрольные задания для...
Параметрическое линейное программирование iconЛинейное программирование
Линейное программирование (ЛП) это наука о методах исследования и отыскания наибольших и наименьших значений линейной функции, на...
Параметрическое линейное программирование iconПеречень вопросов для вступительного экзамена в аспирантуру по специальности 05. 13. 18 «Математическое моделирование, численные методы и комплексы программ» Математические основы
Математическое программирование, линейное программирование, выпуклое программирование
Параметрическое линейное программирование iconЛинейное программирование. Методы решения одношаговых задач оптимального управления
Методы решения таких задач получили название математического программирования. Простейшим случаем математического программирования...
Параметрическое линейное программирование iconМатематическое программирование
В математическом программировании выделяют линейное программирование – когда функции и линейны, квадратичное программирование, когда...
Параметрическое линейное программирование iconЛинейное программирование задачи математического и линейного программирования
Соответствующие методы, позволяющие решать указанные задачи, объединяются под общим названием «математическое программирование»
Параметрическое линейное программирование icon«Линейное программирование и симплекс метод»

Параметрическое линейное программирование iconВопросы экзамена Методы оптимизации Раздел Линейное программирование
Алгоритм симплекс-метода без корректного вида базиса с искусственными переменными
Параметрическое линейное программирование iconЛинейное программирование и симплекс метод
...
Параметрическое линейное программирование iconТранспортная задача
Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org