Решение транспортной задачи методом потенциалов - Курсовая работа

Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта. Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования. Метод потенциалов - первый точный метод решения транспортной задачи - был предложен в 1949 г.Функция W, определенная на совокупности пунктов производства и потребления задачи T, была названа вектором потенциалов или просто потенциалом данной задачи, если (1.1) Будем называть план X потенциальным, если существует потенциал задачи T, связанный с этим планом условием (1.2). Заметим, что потенциал вовсе не следует считать зависящим от конкретного оптимального плана задачи T. Поэтому функция W может быть определена еще и так: W - потенциал задачи T, если причем для тех , которые являются Х-существенными элементами некоторого оптимального плана X этой задачи, соответствующие неравенства переходят в равенства. Напомним, что значения потенциала W в пунктах задачи T были названы потенциалами этих пунктов.Вырожденные опорные планы задачи Т содержат меньше чем n m - 1 положительных перевозок. Это обстоятельство может в свою очередь привести к тому, что при переходе по методу потенциалов к следующему плану величина окажется равной нулю и, следовательно, суммарные транспортные издержки не уменьшатся. При построении базиса нового плана нам, как и в случае общей задачи линейного программирования, необходимо знать ответ на два вопроса: какой вектор необходимо ввести в старый базис, какой вектор (один!) необходимо из него вывести? Можно было бы, конечно, выводить из старого базиса произвольный вектор коммуникаций из числа удовлетворяющих указанному критерию. Существует такое число , что при любом , удовлетворяющем условию задача обладает свойством невырожденностиПоэтому состоит из m n-1 векторов и является базисом опорного плана . Переименуем векторы базиса и обозначим l-й вектор через стоимость единичной перевозки по коммуникации, соответствующей вектору . (оценка вектора условий ) достигает минимума, и осуществляется переход к новому базису путем замены одного из векторов системы вектором . Согласно методу улучшения плана после разложения вводимого вектора (вектора ) по векторам старого базиса разыскивается величинаМатрица составлена из оценок векторов относительно базиса плана , т.е. где и - предварительные потенциалы, отвечающие плану . Пусть - номера тех столбцов матрицы С, которые содержат-существенные элементы в 1-й строке; - номера строк матрицы С, которые содержат-существенные элементы в столбцах с номерами . Если множества и для уже определены, то объединяет номера тех столбцов матрицы С, не принадлежащих , которые содержат-существенные элементы в строках с номерами , а состоит из номеров строк этой матрицы, не включенных в и содержащих-существенные элементы в столбцах с номерами . Аналогично, для определим как элемент , при котором является-существенным элементом С. Затем выделим столбцы , содержащие элемент и через обозначим множество - существенных элементов, лежащих в этих столбцах и отличных от элементов .После запуска программы на экране появляется главное окно. Нажимаем на кнопку «Добавить».Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).

Содержание

Введение

1. Теоретические основы метода

2. Вырожденность

3. Метод потенциалов и метод последовательного улучшения плана

4. Алгоритм метода потенциалов

5. Руководство пользователя

Заключение

Список литературы