Идея решения ЗЦЛП методом отсечения и его геометрическая иллюстрация.

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

1.Ограничение должно быть линейным

2.Оно должно отсекать найденное целочисленное решение

3.Оно не должно отсекать не одного целочисленного плана.

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

Xk=βk-(n-m,s=1)∑αkm+sXm+s

Преобразуя это уравнение представим свободные члены и коэфиц как ∑ целой и дробной части.

Xk=([βk]-(n-m,s=1)∑[αkm+s]Xm+s)+({βk}-(n-m,s=1)∑ {αkm+s}Xm+s)

Сумма в первых скобках-целое число, во вторых-дробное.Для того, чтобы Хк было целым, надо,что и сумма во вторых скобках была целой. Обозначим ее

Sk={βk}-(n-m,s=1)∑ {αkm+s}Xm+s

Чтобы s было целым оно должно быть не положительным

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk} (1)

 

 

47. Алгоритм метода Гомори.

1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он –оптимальный. В противном случае переходят к пункту 2

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

(n-m,s=1)∑ {αkm+1}Xm+1≥{βk}

3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом

4.Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2.

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

 

48. Метод ветвей и границ решения целочисленных задач.

Этот метод относится к группе комбинаторных.Применение этих методов заменяет полный перебор планов их частным перебором. Идея метода: пусть дана ЗЦЛП

f=(n,j=1)∑CjXimax

(n,j=1)∑AijXj=bi, i=1,m

xj≥0, j=1,n

xi-целое,j=1,n

Сначала в ОДЗ этой задачи определяется оптимальный план без учета условия целочисленности. Если в полученном решении некоторые переменные имеют дробное значение, то выбирают любую из дробных переменных и разветвляют исходную задачу на 2 подзадачи

f =∑CjXjmaxf =∑CjXjmax

(n,j=1)∑AijXj≤bi, i=1,m (n,j=1)∑AijXj≤bi, i=1,m

Xk≤[Xk˚] Xk≥[Xk˚]+1

Xj≥0 Xj≥0

Xj-целое,j=1,n Xj-целое,j=1,n

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

 

 

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

 

 

50. Задача о выборе кратчайшего пути на сети дорог.

Надо перевезти груз из А в Б, известна сеть дорог, их соединяющих.

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

Рассматривается некоторый управляемый процесс. В результате управления система переводится из состояния S0 в состояние S. Предположим, что управление может разбиться на n шагов, на кождом из которых выбирается одно из множества допустимых управлений Un (n=1,N). Элементы множества Un и Sn определяются из условия задачи.

На каждом шаге достигается эффект Zn. Общий эффект это сумма эффектом, достигнутых на каждом шаге. Тогда задача динам программир будет формулироваться: Определит такое допустимое управление U*=(U1, U2,..,UN), переводящее систему из состояния S0 в состояние SN, при котором общий эффект

Решение задач методом динамического программирования осуществляется на основе принципа оптимальности. Обозначим через fn (Sn-1; Un) условно оптимальное значение целевой функции в интервале от шага n до шага N включительно, при условии, что перед n-шагом система, находясь в одном из состояний множества Sn-1, а на n шаге было выбрано такое управление из множества Un, которое обеспечивало целевой функции условно оптимальное значение—fn+1 (Sn

 

51. Задача об оптимальном распределении средств м/д предприятиями на расширение производства.

Группе предприятий выделяют дополнительные средства для реконструкции и модернизации производства. По каждому из n предприятий известен возможный прирост gi(x) (i=1,n) выпуска продукции в зависимости от выделенной ему суммы х. Требуется так распределить между предприятиями средства с, чтобы общий прирост fn (c) выпуска продукции был максимальным.

Пусть n=1. Обозначим через f1(x) максимально возможный прирост выпуска продукции на этом предприятии. Соответствующий выделенной сумме x. Каждому значению х отвечает вполне определенное значение gi(x) выпуска, поэтому можно записать f1(x)=max(g1(x))= g1(x)

Если n=2 средства распределяются между 2 предприятиями. Если второму распределяется сумма х, то прирост продукции на нем составит g2(x)..Оставшиеся другому предприятию средства (с-х) в зависимости от х позволяет увеличить прирост выпуска до max возможного значения f1(с-x). Общий прирост выпуска на двух предприятиях: g2(x)+ f1(с-x).

Функциональное уравнение Беллмана для рассматриваемой задачи запишется в виде

fn(с)=max(gn(x)+fn-1(c-x)) (1)

0≤x≤c

Максимальный прирост выпуска продукции на n предприятиях определяется как max суммы прироста выпуска на n-м предприятии и прироста выпуска на остальных n-1 предприятиях при условии, что оставшиеся после n-го предприятия средства распределяются между остальными предприятиями оптимально. Имея уравнения типа (1) последовательно находим f1, затем f2, f3, и наконецfn-1, fn для различных значений распределяемой суммы.

Для отыскания оптимального распределения средств находим с средств n- мупредприятияю. По величине оставшихся средств

И известному нам значению fn-1 устанавливаем --величину ассигнований(n-1)-му предприятию. И наконец находим

 

55. Метод Лагранжа решения задач нелинейного программирования.

Пусть рассматривается задача на условный экстремум

Y=f(x1,x2,..,xn) extr

Φi(x1,x1,..,xn)=bi, i=1,m

Причем среди ограничений нет неравенств, условия неотрицательности, дискретности переменных m<n функции f и φi непрерывны и имеют частные производные второго порядка.

Общий порядок решения задач методом Лагранжа

1.Записать функцию Лагранжа

L(X1,X2,X3,..Xn,λ1,λ2,…,λm)=f(x1,x2,..,xn)+(m,i=1)∑λi(bi-φi(x1,x2,…,xn)) extr

2.Найти частные производные функции Лагранжа по всем переменным и равно 0

И решить полученную систему

3.Функция f(x) имеет в стационарной точке (х1,х2,λ) условный максимум, если в ней и условный минимум, если

Для задач с двумя переменными второй дифференциал по формуле

При условии, что dx1 и dx2 связаны соотношением

 

 

56. Понятие о градиентном методе решения задач нелинейного программирования.

Градиентные методы можно применять к любой задаче нелинейного программирования. Градиент в каждой точке Х0, в которой он существует, направлен по нормали к линии уровня поверхности f(x) и показывает направление наискорейшего возрастания функции в данной точке. Идея решения—в допустимой области необходимо взять производную в точкеХ0 и переместиться из нее в градиентном направлении в точке Х1 сделав некоторый шаг в градиентном направлении перейдем в точку Х2 и т.д.

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

Xk+1=Xk+λkΔf(Xk) c использованием необходимого признака экстремума