Минимизация стоимостей перевозок

процесса необходимо провести проверку полученного плана на вырожденность. Если количество заполненных клеток равно m + n -1 , то план является невырожденным. Если план вырожденный , т.е количество заполненных клеток стало меньше m + n -1 , то незаполненные клетки с минимальными стоимостями перевозок заполняются нулями , чтобы общие количество заполненных клеток стало равным m + n -1. Транспортная задача с неправильным балансом называется открытой моделью . Чтобы ее решить , необходимое сбалансировать. Достигается это следующим образом: Когда еai >еbj это транспортная задача с избытком запасов. еxij<= ai (i=1,m)

??. 2203 81 21 еxij=bj (j=1,n) Здесь вводим фиктивного потребителя Bф и приписываем ему заявку bф=еai - еbj . Вводим фиктивный сотолбец , т.е Ciф=0 (i =1,m). Все стоимости будут равны нулю , это значит , что грузы ciф останутся невостребованными , т.е введением фиктивного потребителя , мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом. Если сумма подданных заявок превышает наличные запасы еbj >еai , то такая задача называется транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления Aф , приписав ему фиктивный запас aф =еbj - еai . Добавляем фиктивную строку , где Cфi= 0 ( j=1,n). Стоимости будут равны нулю . это значит , что часть заявок cфj останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент: R=еai : еbj и каждый запас bj умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом. Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов. Каждому поставщику Ai поставим в соответствии некоторые числа ai , называемые потенциалом , а каждому потребителю Bj число bj. Для каждой независимой клетки , т.е для каждой независимой переменной рассчитываются так называемые косвенные тарифы ( Cўij) по формуле Cўij= ai + bj. А для заполненных клеток , т.е базисных переменных Cўij =Cij. Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие Cўij - Cij <=0 , то такой план является оптимальным. Если хотя бы в одной свободной клетке Cўij > Cij , то следует приступить к улучшению плана. Для правильного перемещения перевозок , чтобы не нарушить ограничений , строится цикл , т.е замкнутый путь , соединяющий выбранную свободную клетку с той же самой , и проходящий через заполненные клетки. Цикл строится следующим образом. Вычеркиваются все строки и столбцы , содержащие ровно одну заполненную клетку (выбранная при этом клетка считается заполненной). Все остальные заполненные клетки составляют и лежат в его углах. Направление построения цикла ( по часовой стрелке или против ) несущественно. В каждой клетки цикла , начиная со свободной , проставляются поочередно знаки І + І и І - І . В клетках со знаком І - І выбирается минимальная величина. Новый базисный план начинается путем сложений выбранной величины с величинами , стоящих в клетках цикла со знаком І + І и вычитанием этой величины из величины , стоящей в клетке со знаком І - І . Выбранная минимальная величина будет соответствовать перемененной выводимой из базиса.

КП. 2203 81 - 21 Значения переменных включенных в цикл , после описанной корректировки , переносятся в новую таблицу. Все остальные переменные записываются в новую таблицу без изменения. Осуществляется переход к шагу один. Дальше подсчитывается значение целевой функции F = ее Cij· cij min.

Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум.

??. 2203 81 - 21 5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений. Это связано с тем , что первые компьютеры создавались как устройства для вычислений , грубо говоря , усовершенствованные , арифметические арифмометры. Принципиальное отличие компьютеров от арифмометров и других счетных устройств состояло в том , что арифмометры могли выполнять лишь отдельные вычислительные операции(сложение , вычитание , умножение , деление и др.) , а компьютеры позволяли проводить без участия человека сложные последовательные вычислительные операции по заранее заданной инструкции - программе. Кроме того , для хранения данных , промежуточных и итоговых результатов вычислений компьютеры содержат память. Компьютер - это универсальный прибор для переработки информации. Но сам по себе компьютер является просто ящиком с набором электронных схем. Он не обладает знаниями ни в одной области своего применения. Все эти знания сосредоточены в выполняемых на компьютере программах. Для того , чтобы компьютер мог осуществить определенные действия , необходимо составить для компьютера программу , т.е точную и пол=дробную последовательность инструкций на понятном компьютере языке , как надо правильно обрабатывать информацию. Меняя программы для компьютера , можно привести его в рабочие место бухгалтера ил конструктора , статистика или агронома , редактировать документ или играть в игры. Поэтому для эффективного использования компьютера необходимо знать назначение и свойства необходимые при работе с ним программ. Программы . работающие на компьютеры можно разделить на три категории : n Прикладные программы , непосредственно обеспечивающие выполнение необходимых пользователям работ : редактирование текстов , рисование картинок , обработку информационных массивов и т.д. n Системные программы , выполняющие различные вспомогательные функции , например создание копий используемой информации , проверку работоспособности устройств компьютера и т.д. Огромную роль среди всех системных программ играет операционная система - программа , управляющая компьютером , запускающая все другие программы и выполняющая для них различные сервисные функции. n Инструментальные системы (системы программирования ) , обеспечивающие создание новых программ для компьютера.

??. 2203 81 - 21 6.ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА

В 1992 году фирма Borland International выпустила два пакета программирования , основанные на использовании языка Паскаль - Borland Pascal 7.0 и Turbo Pascal 7.0. Система программирования Turbo Pascal , разработанная американской корпорацией Borland остается одной из самых популярных систем программирования в мире. Этому способствует , с одной стороны , простота лежащего в ее основе языка программирования Паскаль , а с другой - труд и талант сотрудников Borland во главе с идеологом и создателем Turbo Pascal Андерсом Хейлсбергом , приложившим немало усилий к ее совершенствованию. Придуманный швейцарским ученым Никласом Виртом как средство для обучения студентов программированию , язык Паскаль стараниями А. Хейлсберга превратилась в мощною современною профессиональную систему программирования