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

Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин. Линейное программирование основано на решении системы линейных уравнений (с преобразованием в уравнения и неравенства), когда зависимость между изучаемыми явлениями строго функциональна. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальным выходом заготовок).В простейшем виде, когда распределяется один вид продукта и потребителям все равно, от кого из поставщиков его получать, задача формулируется следующим образом. Исходная информация: Mi - количество единиц груза в i-м пункте отправления (i = 1, 2, …, k ); Обозначим через xij планируемое количество единиц груза для перевозки из i-ro пункта в j-й. В простейшем случае должны выполняться следующие очевидные условия: Таким образом, математической формулировкой транспортной задачи будет: найти при условиях ; ;Простейшими транспортными задачами являются задачи о перевозках некоторого однородного груза из пунктов отправления (от поставщиков) в пункты назначения (к потребителям) при обеспечении минимальных затрат на перевозки. Например, для k поставщиков и l потребителей такая задача имеет следующий вид: Здесь показатели aij означают затраты на перевозку единицы груза от i-го поставщика (i =1,2,…,k ) к j-тому потребителю (j =1,2,…,l ), Mi - мощность i-того поставщика в планируемый период, Nj - спрос j-того потребителя на этот же период. Обозначим через xij поставку (количество груза), которая планируется к перевозке от i-того поставщика к j-тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, т.е. функции при ограничениях Система ограничений включает k уравнений, связывающих поставки i-того поставщика с мощностью Mi (i=1,2,…,k ) этого поставщика, и l уравнений, связывающих поставки j-тому потребителю со спросом Nj (j =1,2,…,l ) этого потребителя.Ограничение и условия не отрицательности переменных, исключающие обратные перевозки xij >0; i= 1, 2, …, k ; j = 1, 2,., l. Эти условия образуют систему ограничений. Установим условия, при которых эта система будет совместной, т.е. будет иметь решения. Сложим элементы xij матрицы перевозок по строкам, каждая строка в сумме дает Mi, и в итоге получим . Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие .Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограниченийОпорное решение (опорный план, базисное решение, basic solution) - одно из допустимых решений, находящихся в вершинах области допустимых решений. При решении задачи линейного программирования можно поступить следующим образом: найти любое из таких "вершинных" решений, не обязательно оптимальное, и принять его за исходный пункт расчетов.Начав заполнение с клетки (1.1) - "северо-западного угла" таблицы, ступенями спускаются вниз до клетки (k, l ), вычеркивая либо одну строку, либо один столбец. На последнем шаге вычеркиваются последняя (k-я) строка и последний (l-й) столбец.При построении первоначального плана по способу северо-западного угла совершенно не учитываются тарифы, потому план получается весьма далеким от оптимального. Способ минимального элемента учитывает тарифы и потому позволяет найти план, более близкий к оптимальному. В клетку с минимальным тарифом записываем наибольшую возможную перевозку (исходя из запасов и потребностей), затем заполняем очередную по порядку клетку и т.д., пока не получим план. Он будет лучше плана, построенного по способу северо-западного угла, и для нахождения оптимума потребуется меньше вычислений. Наличие положительной оценки свободной клетки () при проверке опорного решения на оптимальность свидетельствует о том, что полученное решение не оптимально и для уменьшения значения целевой функции надо перейти к другому опорному решению.Распределительный метод решения транспортной задачи отличается от метода потенциалов некоторым изменением вычислительного процесса и иным (по форме) критерием оптимальности.

Содержание

Введение

1. Формулировка транспортной задачи

2. Математическая модель транспортной задачи

3. Необходимое и достаточное условия разрешимости транспортной задачи

4. Свойство системы ограничений транспортной задачи

5. Опорное решение транспортной задачи

6. Методы построения начального опорного решения

6.1 Построение первоначального плана по способу северо-западного угла

6.2 Построение первоначального плана по способу минимального элемента

7. Переход от одного опорного решения к другому

8. Распределительный метод

9. Метод потенциалов

10. Особенности решения транспортных задач с неправильным балансом

11. Алгоритм решения транспортной задачи методом потенциалов

11.1 Предварительный шаг

11.2 Общий повторяющийся шаг

12. Транспортная задача с ограничениями на пропускную способность

13. Транспортная задача по критерию времени

14. Применение транспортной задачи для решения экономических задач

Заключение

Список использованной литературы