Курсовая работа на тему: "Решение транспортных задач методом потенциалов" Содержание. 1. Линейная транспортная задача 2. Составление опорного плана 3. Метод потенциалов 3. Список использованной литературы 1. Транспортная задача. Транспортная задача ставится следующим образом: имеется m пунктов отправления, в которых сосредоточены запасы каких-то однородных грузов. Имеется n пунктов назначения подавшие заявки соответственно на груза. Известны стоимости р i j перевозки единицы груза от каждого пункта отправления до каждого пункта назначения. Все числа р i j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна. Далее, предполагается, что
    1 где bi есть количество продукции, находящееся на складе i, и aj - потребность потребителя j. Замечание. Если то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n +1 с потребностью и положим транспортные расходы pi,n+1 равными 0 для всех i. Если то потребность не может быть покрыта. В этом случае начальные условия должны быть изменены таким образом, чтобы потребность в продукции могла быть обеспечена. Обозначим через xij количество продукции, поставляемое со склада i потребителю j. В предложении (1) нам нужно решить следующую задачу (математическая модель транспортной задачи):
    
    2
     Транспортную задачу мы можем характеризовать транспортной таблицей и таблицей издержек: а1 ... аn b1 . . . bm . . . . . . p11 ... p1n . . . . . . pm1 ... pmn Допустимый план перевозок будем представлять в виде транспортной таблицы: а1 ... аn b . . . bm ... . . . . . . ... Cумма элементов строки i должна быть равна bi, а сумма элементов столбца j должна быть равна aj, и все должны быть неотрицательными. Пример 1. 20 5 10 10 5 15 15 20 5 6 3 5 9 6 4 7 3 5 2 5 3 1 8 Мы получаем следующую задачу: х11+х12+х13+х14+х15 =15, х21+х22+х23+х24+х55 =15, х31+х32+х33+х34+х35 =20,
    х11 +х21 +х31 =20,
    х12 +х22 +х32 =5,
    х13 +х23 +х33 =10, х14 +х24 +х34 =10, х15 +х25 +х35 =5; хij 0 для i = 1,2,3; j = 1,2,3,4,5;
    Кmin=5х11+6х12+3х13+5х14+9х15+6х21+4х22+7х23+3х24+5х25+2х31+5х32+3х33+х34+8х35; Такие задачи целесообразно решать при помощи особого варианта симплекс-метода - так называемого метода потенциалов. Все транспортные задачи имеют оптимальное решение. Если все значение aj и bi в условиях транспортной задачи целочисленные, то переменные xij во всех базисных решениях (а так же и в любом оптимальном базисном решении) имеют целочисленные значения. ............