Криминалистика. Вырожденность в транспортной задаче возникает, когда одна или более базисных переменных обращаются в 0

Пример

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

Вырожденность в транспортной задаче

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

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

Еще раз вернёмся к рассмотренной выше задаче. Найдем оптимальный план, взяв в качестве опорного план, полученный с помощью метода "северо-западного угла" Х11=15, Х21=5, Х22=12, Х23=5, Х24=3, Х34=5, Х35=15. Все остальные Хij= 0.

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

Построенный план не является оптимальным, следовательно, производим перерасчет. Выберем ячейку 31.

Строим следующую транспортную таблицу.

В результате две базисные переменные обратились в нуль. Количество заполненных ячеек уменьшилось на одну. Поэтому для дальнейших действий (составление системы для нахождения потенциалов решения) необходимо рассмотреть или ячейку 21 или 34. Выберем ячейку 34. Проверим построенный план на оптимальность.

Полученный план не является оптимальным. Выберем ячейку 33.

И так далее.

Тема 2.6. Постановка и классификация задач нелинейного программирования

• задачи нелинейного программирования
• классификация

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

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

В самом общем виде классификация представлена в таблице.

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

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

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

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

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

Дата добавления: 2014-01-20