Транспортная задача. Построение цикла перерасчета таблицы

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

Если опорный план транспортной задачи не оптимальный, то для построения нового плана строим цикл перерасчета.

Цикл перерасчёта таблицы – это последовательность ячеек, удовлетворяющая условиям:

1. Одна ячейка пустая, все остальные занятые.

2. Любые две соседние ячейки находятся в одной строке или в одном столбце. Пустой ячейке присваивают знак "+", остальным – поочерёдно знаки "–" и "+".

В минусовых клетках находят число X = min(X_ij). Далее составляют новую таблицу по следующему правилу:

3. В плюсовых клетках добавляем Х.

4. Из минусовых клеток вычитаем Х.

5. Все остальные клетки вне цикла остаются без изменения.

Нелинейное программирование. Основные понятия

Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейными являются и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.

Задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора х (вектора решений).

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.

В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут непропорционально количеству закупленных или произведённых товаров.

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

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