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

2015-12-06

631

Обсуждений (0)

0.00 из 5.00 0 оценок

Классификация задач оптимального программирования

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

1. По характеру взаимосвязи между переменными:

а) линейные,

б) нелинейные.

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

2. По характеру изменения переменных:

а) непрерывные,

б) дискретные.

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

3. По учету фактора времени —

а) статические,

б) динамические.

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

4. По наличию информации о переменных —

а) задачи в условиях полной определенности (детерминированные),

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

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

5. По числу критериев оценки альтернатив —

а) простые, однокритериальные задачи,

б) сложные, многокритериальные задачи.

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

Сочетание признаков классификации 1—5 позволяет группировать (классифицировать) в самом общем виде задачи и методы оптимального программирования, например:

1а)2а)3а)4а)5а) — задачи и методы линейного программирования;

1б)2а)3а) 4а)5а) — задачи и методы нелинейного программирования;

1а)2б)3а)4а)5а) — задачи и методы целочисленного (дискретного) линейного программирования и т.д.

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

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум(максимум или минимум) линейной целевой функции

f (x) :

max (min) f ( x ) = c₁*x₁+c₂*x₂+……….+c_n*x_n(9)

при ограничениях (условиях):

a₁₁*x₁+a₁₂*x₂+…….+a_1n*x_n {£, =, ³} b₁,

a₂₁*x₁+a₂₂*x₂+…….+a_2n*x_n {£, =, ³} b₂, (10)

………………………………………….

a_m1*x₁+a_m2*x₂+…….+a_mn*x_n {£, =, ³} b_m,

X_j ³ 0, j = 1, n , (11)

где a_ij, b_i, c_j (i=1,m , j=1, n ) – заданные постоянные величины.

1) Так записывается общая задача линейного программирования в развернутой форме.

Знак {£, =, ³} означает, что в конкретной ЗЛП возможно ограничение типа равенства или неравенства (в ту или иную сторону).

Систему ограничений (10) называют функциональными ограничениями ЗЛП, а ограничения (11) – прямыми ограничениями.

Вектор X= (x₁, x₂,…., х_п), удовлетворяющий системе ограничений (10) и (11), называется допустимым решением, или планом ЗЛП, т.е. ограничения (10)- (11) определяют область допустимых решений, или плановзадачи линейного программирования (область определения ЗЛП).

План (допустимое решение), который доставляет максимум или минимум целевой функции (9), называется оптимальным планом (оптимальным решением) ЗЛП.

2) Канонической формой записи задачи линейного программирования (КЗЛП) называют задачу вида (запись с использованием знаков суммирования):

Найти: max f ( X) = C_j *X_j (12)

при ограничениях: a_ij *X_j = b_i , i =1, m , (13)

X_j ³ 0, j= 1, n. (14)

Приведение ЗЛП к каноническому виду осуществляется введением в левую часть соответствующего ограничения вида (10) k-тойдополнительной переменной X_n₊_k ³ 0 со знаком “ - “ в случае ограничения типа “³” b и знаком “+” в случае ограничения типа “£”.

Если на некоторую переменную х_r не накладывается условие неотрицательности, то делают замену переменных х_r = х'_r - х" _r, х' _r ³ 0, х"_r ³0. В преобразованной задаче все переменные неотрицательные. Переход к задаче на максимум достигается изменением в случае необходимости знака у целевой функции.

3) Векторная форма записи ЗЛП имеет вид:

Найти: max (min) f(X)=C*X

при ограничениях: A₁₁ *x₁+ A₂₂ *x ₂+ ... + А_n*х_n {£, =, ³} В(b₁,b₂,…,b_n),

х_j ³0,

где С = (c₁,с₂, ...,с_n)-вектор-строка;Х = (х_1,х₂,...,х_n) – вектор-столбец;

С*Х — скалярное произведение векторов С,Х; Ajи В — вектор-столбцы:

A₁= , A₂= , ….., A_n= , B =

4) Матричная форма записи ЗЛП:

max (min) f(X) =C*X

при условиях: A*X{£, =, ³} B

X ³ 0

Здесь С = (с₁,с₂,….,с_n) –вектор-строка; A= (a_ij ) – матрица размерности m ´n, столбцами которой являются вектор-столбцы A_j.

X = - вектор-столбец, B = - вектор-столбец.

5) Стандартная форма записи ЗЛП:

max (min) f (X) =C * X ,

A*X {£, =, ³} B,

X ³ 0.

При этом запись X ³ 0 понимают как вектор ( или вектор-столбец в зависимости от контекста), у которого все компоненты (элементы) неотрицательны.

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