Частным случаем задачи линейного программирования является транспортная задача(ТЗ).
Транспортная задача возникает тогда, когда речь идет о рациональной перевозке одного продукта или сырья от производителей к потребителям Обозначив через а1,а2,…,аm запасы продуктов в пунктах отправления, а через b1,b2,…bn - потребности в продукте в пунктах назначения. Пусть известна стоимость cij 1<=i<=m,1<=j<=n перевозки единицы груза из пункта отправления в пункт назначения. Требуется найти такую программу перевозок, чтобы их общая стоимость была наименьшей.
Транспортная задача является закрытой (замкнутой), если выполняются следующие условия:
А)все запасы должны быть вывезены
Б)все потребности должны быть удовлетворены
В)суммарные запасы равны суммарным потребностям, т.е:
.
Через xij обозначают объем перевозок из первого пункта отправления в j-ый пункт назначения. Выполняются следующие условия:
(i = l,..., m),
(j = 1,..., n),
Общая стоимость перевозок вычисляется по формуле: 
Пример транспортной задачи:
2 2 когда транспортная задача называется вырожденной Допустимый опорный план транспортной задачи называется невырожденным, если число заполненных клеток транспортной таблицы, т.е. число положительных перевозок 
равно 
, где 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); αk+βi=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)
