Минимизация стоимостей перевозок (стр. 2 из 3)

Когда еa_i >еb_j это транспортная задача с избытком запасов.

е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.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

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

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

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

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

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

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

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

- Инструментальные системы (системы программирования ) , обеспечивающие создание новых программ для компьютера.

КР. 2203 81 - 21

6.ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА

В 1992 году фирма Borland International выпустила два пакета программирования , основанные на использовании языка Паскаль - Borland Pascal 7.0 и Turbo Pascal 7.0. Система программирования Turbo Pascal , разработанная американской корпорацией Borland

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

Пакет Turbo Pascal включает в себя как язык программирования - одно из расширений языка Паскаль для ЭВМ типа IBM , так и среду , предназначенную для написания , отладки и запуска программ.

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

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

КР. 2203 81 - 21

7.РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРРАММЫ.

B1	B2	B3	B4	ai	ai
A1	1 1 30	2 2 20	0 4	4 1	50	0
A2	2 2	3 3 10	1 1 10	5 5 10	30	1
A3	1 3	2 2	0 4	4 4 10	10	0
заявки bj	30	30	10	20	90
Bj	1	2	0	4

1,2 1,4

10

2,2 2,4

B1	B2	B3	B4	ai	ai
A1	1 1 30	2 2 10	0 4	1 1 10	50	0
A2	2 2	3 3 20	1 1 10	2 5	30	1
A3	4 3	5 2	3 4	4 4 10	10	3
bj	30	30	10	20	90
Bj	1	2	0	1

1,1 1,4

10

3,1 3,4

КР. 2203 81 - 21

B1	B2	B3	B4	ai	ai
A1	1 1 20	2 2 10	0 4	1 1 20	50	0
A2	2 2	3 3 20	1 1 10	2 5	30	1
A3	3 3 10	4 2	2 4	3 4	10	2
bj	30	30	10	20	90
Bj	1	2	0	1

1,1 1,2