33. Альтернативный оптимум в транспортной задаче.

Альтернативный оптимум (множество оптимальных решений). В этом случае опорная изоцель совпадает с одной из сторон ОДЗ многоугольника в двухмерном пространстве, а в трёхмерном пространстве с одной из граней многогранника.

В данном случае целевая функция достигает своего максимального значения в любой точке отрезка [A;B]: хmax ∈[A;B]. В транспортной же задаче таким «отрезком» считаются ячейки с оценками равные нолю. При цикле пересчета такие оценки просто бесконечно перемещаются, из чего следует что в такой задаче нет единственного оптимального решения.

33. Запреты в транспортной задаче.

Сохранение установившихся связей. Некоторые поставщики могут быть связаны с отдельными потребителями долгосрочными договорами на поставку определённых объёмов продукции. Однако в результате решения задачи может оказаться, что соответствующие объёмы не будут поставлены нужным потребителям. Чтобы этого не произошло, необходимо перед решением задачи уменьшить на заданную величину объёмы запасов и объёмы потребления соответствующих поставщика и потребителя. Затем решить задачу обычным способом. После нахождения решения соответствующий оптимальный объём поставки увеличить на заданную величину.

Условие полного обеспечения некоторого потребителя или полный. Такие условия возникают, когда исходная задача является открытой. Пусть суммарные объёмы запасов продукции, имеющейся у поставщиков, меньше суммарной потребности в этой продукции потребителей. Для того чтобы преобразовать задачу к закрытому типу, необходимо ввести фиктивного поставщика. В этом случае некоторые потребители недополучат определённые объёмы продукции. Чтобы этого не произошло с заданным потребителем, необходимо в клетку, соответствующую поставке от фиктивного поставщика заданному потребителю, записать очень большие удельные транспортные затраты М. Затем задача решается обычным способом. Так же задача решается и при превышении предложения поставщиков над спросом.

35 Задача динамического программирования. Функция Беллмана.

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

Функция Беллмана: F_k(c)=max{g_k(x)+F_k-1(c-x)}

36. Задачи целочисленного программирования. Метод ветвей и границ. Метод Гомори.

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

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

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