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

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

Транспортная задача возникает тогда, когда речь идет о рациональной перевозке одного продукта или сырья от производителей к потребителям Обозначив через а₁,а₂,…,а_m запасы продуктов в пунктах отправления, а через b₁,b₂,…b_n - потребности в продукте в пунктах назначения. Пусть известна стоимость c_ij 1<=i<=m,1<=j<=n перевозки единицы груза из пункта отправления в пункт назначения. Требуется найти такую программу перевозок, чтобы их общая стоимость была наименьшей.

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

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

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

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

.

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

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

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

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

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

 

 

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

 

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

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

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

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

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

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

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

Для определения коэффициентов S_pg при свободных неизвестных X_p используют метод потенциалов. В методе потенциалов каждому пункту отправления предписывают некоторую величину (потенциал) αi (j=1,m), и каждому пункту назначения – величину (потенциал) β_i(j=1,n),т.е. для каждой базисной неизвестной стоимости перевозки разбивают на потенциалы: α_k и β_lⁿ(k); α_k+β_i=c_kl

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

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

 

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

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 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)