Решение транспортной задачи 3 — страница 5

  • Просмотров 348
  • Скачиваний 5
  • Размер файла 108
    Кб

переменной сбалансировать значения базисных переменных. Не существенно, в каком направлении происходит обход цикла. Для каждого базисного переменного и соответствующей небазисной переменной можно построить только один цикл. После построения цикла вводимой небазисной переменной ставится в соответствие знака «+», далее базисным переменным, находящимся в узлах цикла ставятся поочередно знаки «» и «+». Выводимой переменной

считается базисная переменная, имеющая минимальное значение на местах со знаком «». Далее к базисным переменным, находящимся на местах со знаком «+» прибавляется это значение, из переменных со знаком «» – вычитается. Вводимой переменной присваивается найденное минимальное значение. После снова производятся оценки базисных и небазисных переменных и устанавливается, выполнены ли условия оптимальности. 3 ПРАКТИЧЕСКАЯ

РЕАЛИЗАЦИЯ Рассмотрим основные алгоритм решения задачи. Он состоит из следующего: нахождение начального базисного решения, из число небазисных переменных выделяем переменную вводимую в базис, проверяем условия оптимальности, если они удовлетворены то заканчиваем расчет, если нет – переходим к следующему шагу, из числа базисных переменных выделяем выводимую из базиса, находим новое базисное решение и возвращаемся ко

второму шагу. Далее приведены основные шаги алгоритма и демонстрация их на примере который представлен в данной курсовой работе как тестовый пример. Данные приведены в таблице 1. Таблица 1. Исходные данные Фабрика Склады (расходы на 1 партию) Предложение Г Д Е Ж А 20 40 15 30 60 Б 10 25 25 35 100 В 15 45 30 20 80 Спрос 70 50 90 30 240 Шаг 1. Находим начальное допустимое решение. Как уже сказано выше в данной курсовой ра­боте для отыскания начального решения

будем применять про­цедуру северо-западного угла (табл. 2). Таблица 2. 60 10 50 40 50 30 И в данном случае мы имеем базисные переменные – X11,, X21, X22, X23, X33 и X34. И небазисные переменные - X12, X13, X14, X31, X24 и X32. Шаг 2. Выделить из числа небазисных переменных переменную, кото­рую введем в базис. Оценки для базисных переменных: С11=20 С21=10 С22=25 С23=25 С33=30 С34=20 Обычно полагают что U1=0. Оценки для небазисных переменных определяются в соответствии с

отношением: Имеем переменную с наибольшим положительным значением X13=20, которую и будем вводить в базис (табл. 3). Таблица 3. Построение цикла 60- Xij+ 10+ 50 40- 50 30 Далее переходим к «шагу 3». Шаг 3. Выбираем выводимую из базиса переменную из числа перемен­ных текущего базиса. Затем находим новое базисное решение и вернутся к «шагу 2». X23 – выводим эту переменную из базиса. Таблица 4. Новое базисное решение 20 40 50 50 50 30 Оценки для базисных