Приведите пример транспортной задачи

Частным случаем задачи линейного программирования является транспортная задача(ТЗ).

Транспортная задача возникает тогда, когда речь идет о рациональной перевозке одного продукта или сырья от производителей к потребителям Обозначив через а12,…,аm запасы продуктов в пунктах отправления, а через b1,b2,…bn - потребности в продукте в пунктах назначения. Пусть известна стоимость cij 1<=i<=m,1<=j<=n перевозки единицы груза из пункта отправления в пункт назначения. Требуется найти такую программу перевозок, чтобы их общая стоимость была наименьшей.

Транспортная задача является закрытой (замкнутой), если выполняются следующие условия:

А)все запасы должны быть вывезены

Б)все потребности должны быть удовлетворены

В)суммарные запасы равны суммарным потребностям, т.е:

.

Через xij обозначают объем перевозок из первого пункта отправления в j-ый пункт назначения. Выполняются следующие условия:

(i = l, ..., m),

(j = 1, ..., n),

Общая стоимость перевозок вычисляется по формуле:

Пример транспортной задачи:

22 когда транспортная задача называется вырожденнойДопустимый опорный план транспортной задачи называется невырожденным, если число заполненных клеток транспортной таблицы, т.е. число положительных перевозок равно , где m – число пунктов отправления, n– число пунктов назначения.

если допустимый опорный план содержит менее элементов , то он называется вырожденным, а транспортная задача называется вырожденной транспортной задачей.

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

23 в чем суть метода потенциалов?

После отыскания первого базисного решения все неизвестные задачи оказываются разбитыми на две группы:

1)xk1 – базисные

2)xpg – свободные

Целевую функцию можно представить в виде: Z=ΣSpg Xpg +C

Для определения коэффициентов Spg при свободных неизвестных Xp используют метод потенциалов. В методе потенциалов каждому пункту отправления предписывают некоторую величину (потенциал) αi (j=1,m), и каждому пункту назначения – величину (потенциал) βi(j=1,n),т.е. для каждой базисной неизвестной стоимости перевозки разбивают на потенциалы: αk и βln(k); αki=ckl

Для решения системы одному из немзвестных (потенциалов), оказавшимся свободным, приписывают любое числовое значение, чаще всего «0», и предварительно переходят к косвенным стоимостям Cpg. Тогда Spg= Cpg- Cpg коэффициенты при свободных неизвестных будут равны:

1. если величины неотрицательны, то исходное базисное решение будет оптимальным, или если для любой небазисной клетки матрицы перевозок (p,g) выполнимо неравенство: αp+ βg-cij<=0,то допустимое базисное решение оптимально

2. если среди них находятся отрицательные величины, допустим Spogo то следует переходить к следующему шагу, увеличивая Xpogo (оставляя другие свободные неизвестные равные нулю) до тех пор, пока одна из базисных неизвестных не обратится в ноль. Исключая из старого базиса эту переменную и вводя вместо него Xpogoпереходим к новому базису. Переходом к новому базису завершается один шаг симплекс-метода. (цикл пересчета (сдвига))

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.

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

24 что находится изначально: опорный план перевозок или оптимальный план перевозок? Дайте определение задачам нелинейного программирования.

Вид F(x) Вид функции ограничений Число переменных Название задачи
Нелинейная Отсутствуют Безусловная однопараметрическая оптимизация
Нелинейная Отсутствуют Более 1 Безусловная многопараметрическая оптимизация
Нелинейная или линейная Нелинейные или линейные Более 1 Условная нелинейная оптимизация

Методами СЗУ и наименьшей стоимости транспортной задачи находится первое базисное (опорное ) решение и на этом решение не заканчивается, так как не установлено оптимальное решение, хотя первое базисное решение может оказаться и оптимальным. оптимальное решение задачи сводится к выражению базисных неизвестных через свободные неизвестные.(метод потенциалов).

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

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

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

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

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

Общая формулировка нелинейных задач:

Найти переменные х1 , х2 , …, хn , удовлетворяющие системе уравнений

Ψ ( х1 , х2 , …, хn ) = bi , i = 1, 2, …m,

и обращающие в максимум ( минимум ) целевую функцию

Z = f ( х1 , х2 , …, хn )

Наши рекомендации