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

еx_ij <= a_i (i=1,m)

КП. 2203 81 – 21

еx_ij =b_j (j=1,n)

Здесь вводим фиктивного потребителя B_ф и приписываем ему заявку b_ф =еa_i - еb_j . Вводим фиктивный сотолбец , т.е C_iф =0 (i =1,m). Все стоимости будут равны нулю , это значит , что грузы c_iф останутся невостребованными , т.е введением фиктивного потребителя , мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом.

Если сумма подданных заявок превышает наличные запасы

еb_j >еa_­i , то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом , если ввести фиктивный пункт отправления A_ф , приписав ему фиктивный запас a_ф =еb_j - еa_i . Добавляем фиктивную строку , где C_фi = 0 ( j=1,n).

Стоимости будут равны нулю . это значит , что часть заявок c_фj останутся неудовлетворенными. Среди них могут оказаться те потребности , которые необходимо обязательно удовлетворить. Для этого вводим коэффициент:

R=еa_i : еb_j и каждый запас b_j умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом.

Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов.

Каждому поставщику A_i поставим в соответствии некоторые числа a_i , называемые потенциалом , а каждому потребителю B_j – число b_j .

Для каждой независимой клетки , т.е для каждой независимой переменной рассчитываются так называемые косвенные тарифы ( Cў_ij ) по формуле

Cў_ij = a_i + b_j . А для заполненных клеток , т.е базисных переменных Cў_ij =C_ij .

Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие Cў_ij - C_ij <=0 , то такой план является оптимальным. Если хотя бы в одной свободной клетке Cў_ij > C_ij , то следует приступить к улучшению плана.

Для правильного перемещения перевозок , чтобы не нарушить ограничений , строится цикл , т.е замкнутый путь , соединяющий выбранную свободную клетку с той же самой , и проходящий через заполненные клетки. Цикл строится следующим образом.

Вычеркиваются все строки и столбцы , содержащие ровно одну заполненную клетку (выбранная при этом клетка считается заполненной). Все остальные заполненные клетки составляют и лежат в его углах. Направление построения цикла ( по часовой стрелке или против ) несущественно.

В каждой клетки цикла , начиная со свободной , проставляются поочередно знаки

І + І и І - І . В клетках со знаком І - І выбирается минимальная величина. Новый базисный план начинается путем сложений выбранной величины с величинами , стоящих в клетках цикла со знаком І + І и вычитанием этой величины из величины , стоящей в клетке со знаком І - І . Выбранная минимальная величина будет соответствовать перемененной выводимой из базиса.

КП. 2203 81 - 21

Значения переменных включенных в цикл , после описанной корректировки , переносятся в новую таблицу.

Все остальные переменные записываются в новую таблицу без изменения. Осуществляется переход к шагу один. Дальше подсчитывается значение целевой функции

F = ее C_ij · c_ij min.

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

КР. 2203 81 - 21

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

Слово « компьютер »означает « вычислитель » , т.е устройство для вычислений.

Это связано с тем , что первые компьютеры создавались как устройства для вычислений , грубо говоря , усовершенствованные , арифметические арифмометры. Принципиальное отличие компьютеров от арифмометров и других счетных устройств состояло в том , что арифмометры могли выполнять лишь отдельные вычислительные операции(сложение , вычитание , умножение , деление и др.) , а компьютеры позволяли проводить без участия человека сложные последовательные вычислительные операции по заранее заданной инструкции - программе. Кроме того , для хранения данных , промежуточных и итоговых результатов вычислений компьютеры содержат память.

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

Программы . работающие на компьютеры можно разделить на три категории :

- Прикладные программы , непосредственно обеспечивающие выполнение необходимых пользователям работ : редактирование текстов , рисование

картинок , обработку информационных массивов и т.д.

- Системные программы , выполняющие различные вспомогательные функции , например создание копий используемой информации , проверку работоспособности устройств компьютера и т.д. Огромную роль среди всех системных программ играет операционная система - программа , управляющая компьютером , запускающая все другие программы и выполняющая для них различные сервисные функции.