Программа для решения транспортной задачи. Метод потенциалов, его математический смысл и порядок действий по его применению. Математические методы решения транспортных задач. Вычисление стоимости перевозок, расхода топлива, общей прибыли и окупаемости.
Аннотация к работе
Данный курсовой проект представляет собой программу для решения транспортной задачи методом потенциалов. Программа предоставляет пользователю возможность пошагового нахождения оптимального решения.Транспортная задача ставится следующим образом: имеется m пунктов отправления, в которых сосредоточены запасы каких-то однородных грузов. Имеется n пунктов назначения подавшие заявки соответственно на груза. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Далее, предполагается, что (1) где bi есть количество продукции, находящееся на складе i, и aj - потребность потребителя j. В этом случае начальные условия должны быть изменены таким образом, чтобы потребность в продукции могла быть обеспечена.Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ("северо-западного угла" таблицы). Удовлетворим эту заявку за счет запаса 15, имеющегося в пункте b 1 , и запишем перевозку 15 в клетке (1,1). После этого дополним заявку за счет заявка пункта b 2, и запишем 5 в клетке (1,2), теперь заявка удовлетворена, но в пункте b 2 осталось еще 10 единиц груза. Удовлетворим за счет них заявку пунктов а2 (5 единиц клетка 2,2) и а3 (5 единиц клетка 2,3). На складе b3 есть запас в 20 единиц, за счет его мы удовлетворим оставшиеся заявки а3 (оставшиеся 5 единиц клетка 3,3), а3 (10 единиц клетка 3,4) и а5 (5 единиц клетка 3,5).Пусть имеется транспортная таблица, соответствующая начальному решению, xil = для базисного решения переменных, xil = 0 для свободных переменных (ячейки, соответствующие свободным переменным, остаются пустыми). Заполним таблицу расходов, оставив ячейки, соответствующие свободным переменным, пустыми. В крайний правый столбец внесем значения неизвестных u1,…,um, в нижнюю строку - значения неизвестных v1,…,vn,. Если значения k неизвестных определены, то в системе всегда имеется уравнение, одно из неизвестных в котором уже найдено, а другое еще нет. Симплекс - множители нужны для того, чтобы найти свободную ячейку (i, j), которая при замене базиса переходит в базисную (это соответствует отысканию разрешающего столбца в симплекс - методе).Мною был выбран язык программирования Turbo Pascal по следующим соображениям: · Изучение данного языка в школеИмеется m пунктов отправления А1, А2 , ..., Ам , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... Имеется n пунктов назначения В1 , В2 , ... Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. При запуске программа предлагает ввести количество поставщиков (не меньше 2, но не больше 5), затем количество потребителей (условие тоже). Если вводятся числа не удовлетворяющие этому условию, то программа предлагает ввести их заново.
План
Содержание
Введение 3
1. Транспортная задача 4
1.1 Составление опорного плана 7
1.2 Метод потенциалов 9
2. Практическая часть 16
2.1 Обоснование выбора языка программирования 16
2.2 Разработка 16
2.3 Руководство пользователей 16
Заключение 18
Литература 19
Введение
Данный курсовой проект представляет собой программу для решения транспортной задачи методом потенциалов. Программа предоставляет пользователю возможность пошагового нахождения оптимального решения. Все промежуточные результаты выводятся на экран, пользователь может следить за ходом решения.
Транспортная задача заключается в нахождении такого плана поставок, при котором его цена минимальна.
Условия задачи задаются в виде таблицы: поставщик потребитель Запас груза
В1 В2 … Bn
А1 C11 X11 C12 X12 … C1n X1n a1
А2 C21 X21 C22 X22 … C2n X2n a2
… … … … … …
Am Cm1 Xm1 Cm2 Xm2 … Cmn Xmn am
Потребность в грузе b1 b2 … bn
Матрица (cij)m*n называется матрицей тарифов. Планом транспортной задачи называется матрица х=(xij)m*n, где каждое число обозначает количество единиц груза, которое надо доставить из i-го пункта отправления в j-й пункт назначения.