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

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

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

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

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

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

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

31.Понятие о динамическом программировании. Особенности решения задач.

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

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

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

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

34. Задача распределения ресурсов

Предприятие изготов n типов продукции для произ-ва которой треб-ся m видов сырья. Для изготов ед j прод-ции треб-ся a_ij ед сырья i-го вида.

Запасы сырья ограничеры, и состав-ют b_i ед для i-го сырья. Прибыль реализ-цтт одной ед прод-ции j типа равна .. единиц. Сколько ед прод-ции кажд вида нужно произвести, чтобы получ мах прибыль и улажиться в имеющиеся запасы ресурсов.

Пусть х₁, х₂, .. х_n – кол-во продукции каждого вида. Тогда прибыль от реализации прод-ции будет иметь вид z=c₁x₁+c₂x₂+…+c_nx_n

A₁₁x₁+a₁₂x₂+..+a_1nx_n<=b₁

A₂₁x₁+a₂₂x₂+..+a_2nx_n<=b₂

A_m1x₁+a_m2x₂+..+a_mnx_n<=b_m