34. Алгоритм метода Гомори решения полностью целочисленной задачи линейного программирования.

1.Симплекс-методом находят оптимальный план задачи. Если все компоненты оптимального плана целые, то он – оптимальный. В противном случае переходят к пункту 2. 2.Среди нецелых компонент следует выбрать ту, у которой дробная часть является наибольшей и по соответствующей этой строке симплексной таблицы сформулировать правильное отсечение по формуле (n-m,s=1)∑ {αkm+1}Xm+1≥{βk}3.Сформулированное неравенство преобразовать в эквивалентное нулевое равенство и включить в симплексную таблицу с нецелочисленным оптимальным планом 4. Полученную расширенную задачу решают симплекс-методом. Если полученный план не является целочисленным нова переходят к пункту 2. Если в процессе решения появится строка с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В таком случае и исходная задача неразрешима в целых числах. Метод Гомори имеет ограниченное применение. С его помощью целесообразно решать небольшие задачи.

35. Построение правильного отсечения и его свойства.

Если полученное симплекс методом решение задачи не является целочисленным, то к условию задачи добавляют новое ограничение, кот называется правильным отсечением. Оно должно удовлетворять 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). Полученное неравенство—правильное отсечение.

36. Графическая интерпретация решения целочисленной задачи.

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

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

Динамическое программирование — математический метод для нахожд оптимальных решений многошаговых задач. Многошаговым явл процесс, развивающийся во времени и распадающийся на ряд шагов, или этапов. Одна из особенностей метода динамич программирования состоит в том, что принятые решения по отношению к многошаговым процессам рассматр не как единичный акт, а как целый комплекс взаимосвязанных решений. Эту последовательность взаимосвязанных решений называют стратегией. Цель оптимального планирования—выбрать стратегию, обеспечивающую получение наилучшего результата с точки зрения заранее выбранного критерия. Такую стратегию называют оптимальной. Другой важной особенностью метода явл независимость оптимального решения, принимаемого на очередном шаге, от предистории, т.е. от того, каким образом оптимизируемый процесс достиг теперешнего состояния. Оптимальное решение выбирается лишь с учетом факторов, характериз процесс в данный момент. Метод динам программ характериз также тем, что выбор оптимального решения на каждом шаге должен производиться с учетом его последствий в будущем. Это означает, что, оптимизируя процесс на каждом отдельном шаге, ни в коем случае нельзя забыть обо всех последующих шагах. Метод динам программ позволяет одну задачу со многими переменными заменить рядом последовательно решаемых задач с меньшим числом переменных. Решение осуществл по шагам. Основной принцип, на котором базируется оптимизация многошагового процесса, а также особенности вычислительного метода—принцип оптимальности Беллмана. Оптимальное поведение обладает тем св-вом, что каковы бы ни были начальное состояние и начальное решение, последующие решения должны быть оптимальными относительно состояния, полученного в результате первоначального решения. Математически он записывается выражением вида: fn-1(Sl)=optimum(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1) ul+1(l=0,n-1) Optimum в выражении означ максимум или минимум в зависимости от условия задачи. Все вычисления, дающие возможность найти оптимальное значение эффекта, достигаемого за n шагов, fn(S0), проводятся по формуле (1), которая носит название основного функционального уравнения Беллмана или рекуррентное соотношение. При вычислении очередного значения ф-ции fn-1 использ значение ф-ции fn-(l+1), полученное на предыдущем шаге, и непосредственное значение эффекта Rl+1(Sl,Ul+1), достигаемого в результате выбора решения Ul+1 при заданном состоянии системы Sl. Процесс вычисления значения ф-ции fn-1(l=0,n-1).