Программный продукт, реализующий сравнительный анализ методов линейного целочисленного программирования

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

Для уменьшения вредного воздействия электромагнитных полей и излучений был разработан стандарт TCO-99, который предъявляет следующие требования к свойствам электронно-лучевых устройств:

1) Линейность - при выводе на экран матрицы изображения элементы, образующие ее столбцы и строки, должны быть выстроены по прямым и необрывающимся линиям; в противном случае изображение теряет четкость. Максимальное отклонение от прямой не должно составлять более 1% на половину активного экрана (по ширине или по высоте).

2) Ортогональность - геометрически правильное построение перпендикулярных линий. Нарушения перпендикулярности горизонтальных и вертикальных линий приводит к появлению характерного явления "подушки". Среднее отклонение по высоте и ширине не должно быть не более 0, 02, а по диагонали - 0,03.

3) Уровень яркости - количество проецируемого света. Яркость может определяться как для одной точки излучателя света, так и для какой-то части освещаемой поверхности. Для оценки яркости экрана в целом, а также отдельного символа берется вторая методика. Смысл этого требования заключается в обеспечении достаточной яркости экрана (с учетом рассеянного освещения), при котором пользователю не пришлось бы напрягать глаза для того, чтобы понять, что же на экране отображается. Требуемое значение параметра - не менее 100 канделл на квадратный метр, а рекомендуемое - 125.

4) Равномерность освещения - обеспечение одинакового уровня яркости экрана на все активной зоне. Этот параметр вычисляют как отношение максимальной яркости в рассматриваемой зоне к минимальной. Для проведения оценки равномерности освещенности в качестве активной зоны берется вся рабочая площадь монитора. Сильная неоднородность может привести к ошибочному восприятию выводимой на экран информации. Стандарт приписывает этому параметру не выходить за рамки соотношения 1,5:1 и даже рекомендует более узкий диапазон - 1,25:1.

5) Контрастность экрана - достаточная контрастность между отдельным экранным символом и его окружением. Ясно, что символ, не отличающийся по яркости от фона, крайне трудно прочесть. Вычисляется этот параметр по формулам контрастной модуляции; допустимое значение должно составлять не менее 0,5, а рекомендованное - 0,7.

6) Уровень отражения - условный коэффициент между фактической яркостью корпуса и стандартной яркостью для белого цвета. Здесь же учитывается степень отражения от стекла монитора, исчисляемая в глоссах. Чем ближе освещенность к номинальной и чем меньше света отражается стеклом, тем удобней читать с монитора. TCO-99 задает максимальный уровень отражения равным 30 единицам, а освещенность корпуса - не менее 20% от яркости экрана (рекомендован диапазон 20-75%).

7) Варьируемость температуры цвета - насыщенность белого света часто измеряют при помощи так называемой температура цвета. Так, например, свет, излучаемой обычной лампой накаливания, имеет очень низкую температуру, в то время как белые облака на ярком летнем небе - очень высокую. Измеряется цветовая температура в градусах по шкале Кельвина. В зависимости от условий освещенности рабочего места, ТСО-99 устанавливает несколько значений - 9300, 7500, 6500, 5000 оК.

8) Равномерность цвета - визуальная характеристика, описывающая, насколько однородно выглядит дисплей при 100%-ой заливке его белым цветом. При искажении цветовых характеристик монитор нельзя использовать. Стандарт допускает относительное смещение по шкалам RGB не более чем на 0,01, а рекомендует - 0,005.

9) Показатели стабильности изображения описывают, насколько монитору удается сохранять статическое изображение неизменным. Именно в этот раздел внесены требования к скорости вертикальной развертки и рабочему разрешению: 14”, 15”: 800x600, 17”: 1024x768,19”, 21”: 1280x1024. При этом скорость развертки должна составлять не менее 85 Гц, а рекомендовано - 100 Гц.

Также для защиты от электромагнитного излучения следует соблюдать следующие рекомендации:

1) По возможности, стоит приобрести жидкокристаллический монитор, поскольку его излучение значительно меньше, чем у распространённых ЭЛТ мониторов (монитор с электроннолучевой трубкой).

2) При покупке монитора необходимо обратить внимание на наличие сертификата.

3) Системный блок и монитор должен находиться как можно дальше от вас.

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

5) В связи с тем, что электромагнитное излучение от стенок монитора намного больше, постарайтесь поставить монитор в угол, так что бы излучение поглощалось стенами. Особое внимание стоит обратить на расстановку мониторов в офисах.

6) По возможности сократите время работы за компьютером и почаще прерывайте работу.

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

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

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

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

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

Для уменьшения влияния этого фактора на организм человека необходимо сократить общее время работы за ЭВМ до четырех часов в день. При этом необходимо, чтобы расстояние от глаз оператора до монитора составляло не менее 50 сантиметров. В связи с этим в программе все объекты, выводимые на экран, имеют соответствующие размеры. В соответствии с ГОСТ 12.2.018 - 88, мощность дозы рентгеновского излучения видеотерминала не должна превышать 100 мкР/ч на расстоянии 5 см от корпуса аппарата на стороне, обращенной к оператору, поэтому необходимо выбирать видеомонитор, удовлетворяющий этому требованию.

Программа предназначена для работы с цветными мониторами не ниже VGA. Мониторы типа VGA, SVGA полностью соответствуют ГОСТ 23144 - 78 на средства отображения информации типа ЭЛТ:

яркость свечения экрана не менее 0,5 кд/м2;

контрастность экрана не менее 5:1;

ширина линий индикации не более 1 мм;

частота мерцания изображения 75 - 90 Гц;

мощность дозы рентгеновского излучения не более 100 мкР/ч.

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

Конструкция ВДТ должна обеспечивать возможность фронтального наблюдения экрана путем поворота корпуса в горизонтальной плоскости вокруг вертикальной оси в пределах ±30 градусов и в вертикальной плоскости вокруг горизонтальной оси в пределах ±30 градусов с фиксацией в заданном положении. Дизайн ВДТ должен предусматривать окраску корпуса в спокойные мягкие тона с диффузным рассеиванием света. Корпус ВДТ и ПЭВМ, клавиатура и другие блоки и устройства ПЭВМ должны иметь матовую поверхность одного цвета с коэффициентом отражения 0,4 0,6 и не иметь блестящих деталей, способных создавать блики. На лицевой стороне корпуса ВДТ не рекомендуется располагать органы управления, маркировку, какие-либо вспомогательные надписи и обозначения. При необходимости расположения органов управления на лицевой панели они должны закрываться крышкой или быть утоплены в корпусе.

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

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



1.7.5 Защита от шума

При выполнении основной работы на ВДТ и ПЭВМ (диспетчерские, операторские, расчетные кабины и посты управления, залы вычислительной техники и др.), во всех учебных и дошкольных помещениях с ВДТ и ПЭВМ уровень шума на рабочем месте не должен превышать 50 дБА.

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

В помещениях операторов ЭВМ (без дисплеев) уровень шума не должен превышать 65 дБА.

На рабочих местах в помещениях для размещения шумных агрегатов вычислительных машин (АЦПУ, принтеры и т.п.) уровень шума не должен превышать 75 дБА.

программный изделие модуль требование

Таблица 1.24 - Уровни звука, эквивалентные уровни звука и уровни звукового давления в октавных полосах частот

Уровни звукового давления. дБ	Уровни звука, эквивалентные уровни звука, дБА
Среднегеометрические частоты октавных полос. Гц
31,5 63 125 250 500 1000 2000 4000 8000
59 48 40 34 30 27 25 23	35
63 52 45 39 35 32 30 28	40
67 57 49 44 40 37 35 33	45
86 71 61 54 49 45 42 40 38	50
93 79 70 63 58 55 52 50 49	60
96 83 74 68 63 60 57 55 54	65
103 91 83 77 73 70 68 66 64	75



1.7.6 Микроклимат производственных помещений предприятий информационного обслуживания

Микроклимат помещений с ПЭВМ и ВДТ должен удовлетворять следующим основным правилам и нормам (ГОСТ 12.1.005 - 88):

1) В производственных помещениях, в которых работа на ВДТ и ПЭВМ является вспомогательной или основной (диспетчерские, операторские, расчетные, кабины и посты управления, залы вычислительной техники и др.), температура, относительная влажность и скорость движения воздуха на рабочих местах должны соответствовать действующим санитарным нормам микроклимата производственных помещений:

Таблица 1.25 - Оптимальные нормы микроклимата для помещений с ВДТ и ПЭВМ

Период года	Категория работ	Темп. воздуха, гр. С не более	Относит. влажность воздуха, %	Скорость движения воздуха, м/с
Холодный	легкая -1а	22-24	40-60	0,1
	легкая -1б	21-23	40-60	0,1
Теплый	легкая -1а	23-25	40-60	0,1
	легкая -1б	22-24	40-60	0,2

Примечания: к категории 1a относятся работы, производимые сидя и не требующие физического напряжения, при которых расход энергии составляет до 120 ккал/ч; к категории 1б относятся работы, производимые сидя, стоя или связанные с ходьбой и сопровождающиеся некоторым физическим напряжением, при которых расход энергии составляет от 120 до 150 ккал/ч.

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

3) Уровни положительных и отрицательных аэроионов в воздухе помещений должны соответствовать нормам, приведенным в таблице №.



Таблица 1.26 - Уровни ионизации воздуха помещений при работе на ВДТ и ПЭВМ

Уровни	Число ионов в 1 см. куб. воздуха
	n+	n-
Минимально необходимые	400	600
Оптимальные	1500-3000	3000-5000
Максимально допустимые	50000	50000

4) Содержание вредных химических веществ в воздухе производственных помещений, в которых работа на ВДТ и ПЭВМ является вспомогательной, не должно превышать "Предельно допустимых концентраций вредных веществ в воздухе рабочей зоны". Содержание вредных химических веществ в производственных помещениях, работа на ВДТ и ПЭВМ в которых является основной (диспетчерские, операторские, расчетные, кабины и посты управления, залы вычислительной техники и др.), не должно превышать "Предельно допустимых концентраций загрязняющих веществ в атмосферном воздухе населенных мест".

5) Запрещается проводить ремонт ВДТ и ПЭВМ непосредственно в рабочих, учебных и дошкольных помещениях.

1.7.7 Пожароопасные ситуации на предприятиях информационного обслуживания

Пожарная профилактика

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

Для предотвращения пожаров необходимо строго соблюдать следующие правила:

1) На рабочем месте запрещается иметь огнеопасные вещества.

2) В помещениях запрещается:

а) зажигать огонь;

б) включать электрооборудование, если в помещении пахнет газом;

в) курить;

г) сушить что-либо на отопительных приборах;

д) закрывать вентиляционные отверстия в электроаппаратуре

Источниками воспламенения являются:

а) искра при разряде статического электричества

б) искры от электрооборудования

в) искры от удара и трения

г) открытое пламя

3) При возникновении пожароопасной ситуации или пожара персонал должен немедленно принять необходимые меры для его ликвидации, одновременно оповестить о пожаре администрацию.

4) Помещения с электрооборудованием должны быть оснащены огнетушителями.

Вода и водяной пар непригодна для тушения ЭВМ, находящихся под напряжением. В этом случае применяется тушение углекислым газом вследствие изоляции горящего предмета от кислорода воздуха и сильного охлаждения зоны горения. Первичным средством пожаротушения являются ручные огнетушители типа ОУ-5, ОУ-8, а также углекислотные возимые огнетушители VII-1м и VII-2м (ГОСТ 9230-69). Также для тушения электроустановок, находящихся под напряжением, применяют ручные порошкообразные огнетушители ОПС-6, ОПС-10 и ОП-1.

1.7.8 Электробезопасность. Действие электрического тока на человека. Предотвращение электротравматизма

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

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

2) Во избежание повреждения изоляции проводов и возникновения коротких замыканий не разрешается:

а) вешать что-либо на провода;

б) закрашивать и белить шнуры и провода;

в) закладывать провода и шнуры за газовые и водопроводные трубы, за батареи отопительной системы;

г) выдергивать штепсельную вилку из розетки за шнур, усилие должно быть приложено к корпусу вилки.

3) Для исключения поражения электрическим током запрещается:

а) часто включать и выключать компьютер без необходимости;

б) прикасаться к экрану и к тыльной стороне блоков компьютера;

в) работать на средствах вычислительной техники и периферийном оборудовании мокрыми руками;

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

д) класть на средства вычислительной техники и периферийное оборудование посторонние предметы.

3) запрещается под напряжением очищать от пыли и загрязнения электрооборудование.

4) Запрещается проверять работоспособность электрооборудования в неприспособленных для эксплуатации помещениях с токопроводящими полами, сырых, не позволяющих заземлить доступные металлические части.

5) Ремонт электроаппаратуры производится только специалистами-техниками с соблюдением необходимых технических требований.

6) Недопустимо под напряжением проводить ремонт средств вычислительной техники и перифейного оборудования.

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

8) При пользовании электроэнергии в сырых помещениях соблюдать особую осторожность.

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

10) Спасение пострадавшего при поражении электрическим током главным образом зависит от быстроты освобождения его от действия током.

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

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

1.8 Стадии и этапы разработки

Выполнение разработки должно осуществляться в три стадии:

- техническое задание,

- технический проект,

- рабочий проект.

На стадии «Техническое задание» проводится:

- постановка задачи;

- разработка требований к программному изделию;

- изучение литературы по задаче.

На стадии «Технический проект» проводится:

- разбиение программы на модули и согласование передачи данных и управления между различными модулями программы;

- разработка функциональных модулей;

- разработка структуры данных.

На стадии «Рабочий проект» проводится:

- разработка схемы алгоритма;

- физическое проектирование программного изделия;

- тестирование и отладка программных модулей;

- тестирование и отладка готового программного продукта;

- оформление дипломной работы.

1.9 Порядок контроля и приемки

Приемка программного продукта осуществляется при сдаче документально оформленных этапов разработки и проведении испытаний на основе установленных тестов. Тесты должны быть разработаны на этапе рабочего проектирования программного изделия.



2. ТЕХНИЧЕСКИЙ ПРОЕКТ

2.1 Введение

В соответствии с требованиями технического задания основную функцию программного изделия “Целочисленные методы” можно реализовать в виде следующих этапов:

- реализация методов построения опорного плана

- реализация методов улучшения опорного плана

- реализация одноэтапных методов

- учет времени выполнения методов

- построение графиков скорости

- оценка близости методов к оптимальному решению

- построение графиков оценки близости методов к оптимальному решению.

2.2 Функция, реализующая метод «Северо-западного угла»

2.2.1 Методические ограничения

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

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

если , то и исключается поставщик с номером i, , k=1, 2, …, n, kj,



; (2.1)

если , то и исключается потребитель с номером j, , k=1, 2, …, m, ki,

; (2.2)

если , то

(2.3)

и исключается либо i-й поставщик, , k=1, 2, …, n, kj, , либо j-й потребитель, , k=1, 2, …, m, ki, .

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

2.2.2 Входные данные

Входными данными является вводимая пользователем исходная матрица задачи о назначениях - матрица С в виде одномерного целочисленного массива.



2.2.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.2.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения методом «Северо-западного угла».

Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.3 Функция, реализующая метод «Наименьшей стоимости»

2.3.1 Методические ограничения

Метод минимальной стоимости прост, он позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи С=(), i=1,2,,…,m, j=1,2,…,n. Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости min {}, и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую min {}, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.

2.3.2 Входные данные

Входными данными является вводимая исходная матрица задачи о назначениях - матрица С в виде одномерного целочисленного массива.

2.3.3 Инициирование работы

Инициирование осуществляется при запуске пользователем соответствующего модуля.

2.3.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения методом «Наименьшей стоимости».

2.3.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.4 Функция, реализующая метод «Фогеля»

2.4.1 Методические ограничения

Этот метод является эвристическим и обычно приводит к лучшему начальному решению, чем метод Северо-западного угла и метод наименьшей стоимости. На самом деле ПМФ часто дает близкое к оптимальному начальное решение.

Алгоритм состоит из следующих шагов.

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

Шаг 2. Отметить строку или столбец с самым большим штрафом, (если таких несколько, выбрать среди них любую строку пли любой столбец). В отмеченной строке или столбце выбрать переменную с самой низкой стоимостью и придать ей наибольшее возможное значение. Скорректировать объем производства и спрос и вычеркнуть строку или столбец, соответствующие выполненному ограничению.Если ограничения по строке и столбцу выполняются одновременно, вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке) приписать нулевой спрос (объем производства). Строка (столбец) с нулевым объемом производства (или спросом) не пользуется в дальнейших вычислениях (на шаге 3).

Шаг 3. (а) Если невычеркнутой остается в точности одна строка или один столбец, то закончить вычисления.

(б) Если остается невычеркнутой только одна строка (столбец) с положительным объемом производства (спросом), найти базисные переменные в этой строке (столбце), используя метод наименьшей стоимости.

(в) Если всем невычеркнутым строкам и столбцам соответствуют рулевые объемы производства и величины спроса, найти нулевые базисные переменные, используя метод наименьшей стоимости.

(г) В других случаях вычислить новые значения штрафов для вычеркнутых строк и столбцов и перейти к шагу 2.

2.4.2 Входные данные

Входными данными является вводимая исходная матрица задачи о назначениях - матрица С в виде одномерного целочисленного массива.

2.4.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.



2.4.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения методом «Фогеля».

2.4.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.5 Функция, реализующая метод «Потенциалов»

2.5.1 Методические ограничения

Алгоритм складывается из предварительного этапа и конечного числа однотипных итераций.

На предварительном этапе строят начальный опорный план и составляют матрицу

(2.4)

где  - предварительные потенциалы пунктов

. (2.5)

Предварительный этап. С помощью известного метода (например северо-западного угла или минимального элемента) определяют начальный опорный план Х0 и вычисляют предварительные потенциалы

.



Вычисление предварительных потенциалов производят так. По найденному опорному плану Х0 строят схему перевозок Т-задачи из основных коммуникаций плана. Основные коммуникации  плана Х0 =  - это те, которым отвечают базисные компоненты плана, т.е. коммуникации для которых . Далее образуют следующие множества: J1 - множество индексов всех пунктов Bj, которые связаны с пунктом А1 основными коммуникациями; І1 - множество индексов тех пунктов Аі, которые связаны основными коммуникациями с множеством J1; J2 - множество пунктов Bj, которые связаны основными коммуникациями с множеством І1 и т.д. Образование таких множеств Ік продолжаем до тех пор, пока не получим пустое множество.

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

Полагаем для определенности

(2.6)

и вычислим систему потенциалов относительно А1. Тогда

(2.7)

где j J1. Затем по значениям  определяем потенциалы пунктов

 . (2.8)



Аналогично вычисляем потенциалы

(2.9)

(для и  .) и т.д. После того как потенциалы всех пунктов найдены, строим матрицу

(2.10)

Очевидно, позиции матрицы С1, отвечающие базисным элементам плана Х0, будут заняты нулями. Если матрица С1 не содержит отрицательных элементов, то Х0 - оптимальный план. В противном случае Х0 - неоптимальный план, который может быть улучшен. Тогда переходим к выполнению однотипных итераций.

(k+1)-я итерация. Каждая итерация, кроме первой, где отсутствует первый этап, состоит из двух этапов. Предположим, что уже проведено k итераций (k=1,2,.),в результате которых получен план Хk и вспомогательная матрицу Сk. Цель (k+1)-й итерации - построение матрицы Сk+1, а также либо установление оптимальности плана Хk, либо нахождение более экономичного плана Xk+1.

Первый этап. Вычисляют матрицу Сk+1. Преобразвание матрицы Сk в матрицу Сk+1 состоит в следующем. Выбирают наибольший по модулю отрицательный элемент Сk. Пусть это элемент . Тогда вычеркивают (или выделяют) строку , в которой он содержится. Просматривают эту строку и отыскивают множество существенных его элементов. Хk -существенными элементами называют те элементы =0, которые отвечают базисным элементам плана Хk т.е. для которых . Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают вычеркнутые столбцы и ищут в них новые существенные элементы, которые лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы имеются, то вычеркивают строки, в которых они содержатся. Процесс выделения продолжают до тех пор, пока очередное множество новых существенных элементов не окажется пустым. Поскольку каждые строка и столбец не могут быть выделены дважды, то весь процесс заканчивается не более чем за l =m+ n - 1 шагов. Далее строят матрицу Сk+1. Для этого величину прибавляют ко всем элементам выделенных строк и вычитают из элементов всех выделенных столбцов матрицы Сk. При этом все существенные элементы матрицы Сk остаются равными нулю, а кроме того, в нуль превращается и элемент .

Если все элементы матрицы Сk+1 окажутся неотрицательными, то Xk - оптимальный план, и на этом процесс заканчивается. В противном случае переходят ко второму этапу.

Второй этап. Цель этого этапа - построить более экономичный план Хk+1. Выбирают наибольший по модулю отрицательный элемент матрицы Сk+1. Пусть это элемент . Строят цепочку из положительных элементов плана, которая замыкается на . После того, как цепочка построена, в ней находят минимальный нечетный по порядку следования элемент:

(2.11)

Прибавляют  ко всем четным элементам (по порядку следования) цепочки и к элементу и вычитают  из всех нечетных элементов. Остальные элементы Хk оставляют без изменения.

Новый план Хk+1 построен. Он является базисным, так как число его ненулевых элементов не изменилось.

Пусть Lk - транспортные издержки, отвечающие плану Хk. Тогда новое значение целевой функции, отвечающее плану Xk+1, находят по соотношению

. (***)

Так как  и , то . Поэтому Хk+1 - улучшенный опорный план.

Затем производят аналогично (k+2)-ю итерацию.

2.5.2 Входные данные

Входными данными является исходная матрица задачи о назначениях и матрица опорного плана решения - матрицы С и Х в виде одномерных целочисленных массивов.

2.5.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.5.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения методом «Потенциалов».

2.5.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.



2.6 Функция, реализующая «Венгерский» метод

2.6.1 Методические ограничения

Алгоритм состоит из предварительного этапа и не более чем (n-2) последовательно проводимых итераций. Каждая итерация связана с эквивалентными преобразованиями матрицы, полученной в результате проведения предыдущей итерации, и с выбором максимального числа независимых нулей. Окончательным результатом итерации является увеличение числа независимых нулей на единицу. Как только количество независимых нулей станет равным n, проблему выбора оказывается решенной, а оптимальный вариант назначений определяется позициями независимых нулей в последней матрице.

Предварительный этап. Разыскивают максимальный элемент в j - м столбце и все элементы этого столбца последовательно вычитают из максимального. Эту операцию проделывают над всеми столбцами матрицы С. В результате образуется матрица с неотрицательными элементами, в каждом столбце которой имеется, по крайней мере, один нуль.

Далее рассматривают i - ю строку полученной матрицы, разыскивают ее минимальный элемент и из каждого элемента этой строки вычитают минимальный. Эту процедуру повторяют со всеми строками. В результате получим матрицу С0 (С0 ~ C), в каждой строке и столбце которой имеется, по крайней мере, один нуль. Описанный процесс преобразования С в С0 называется приведением матрицы.

Находим произвольный нуль в первом столбце и отмечаем его звездочкой. Затем просматриваем второй столбец, и если в нем есть нуль, расположенный в строке, где нет нуля со звездочкой, то отмечаем его звездочкой. Аналогично просматриваем один за другим все столбцы матрицы С0 и отмечаем, если возможно, следующие нули знаком '*'. Очевидно, что нули матрицы С0, отмеченные звездочкой, являются независимыми. На этом предварительный этап заканчивается.

(k+1)-ая итерация. Допустим, что k-я итерация уже проведена и в результате получена матрица Сk. Если в ней имеется ровно n нулей со звездочкой, то процесс решения заканчивается. В противном случае переходим к (k+1) - й итерации.

Каждая итерация начинается первым и заканчивается вторым этапом. Между ними может несколько раз проводиться пара этапов: третий - первый. Перед началом итерации знаком '+' выделяют столбцы матрицы Сk, которые содержат нули со звездочками.

Первый этап. Просматривают невыделенные столбцы Сk. Если среди них не окажется нулевых элементов, то переходят к третьему этапу. Если же невыделенный нуль матрицы Сk обнаружен, то возможен один из двух случаев:

1) строка, содержащая невыделенный нуль, содержит также и нуль со звездочкой;

2) эта строка не содержит нуля со звездочкой.

Во втором случае переходим сразу ко второму этапу, отметив этот нуль штрихом.

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

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

Этот процесс за конечное число шагов заканчивается одним из следующих исходов:

1) все нули матрицы Сk выделены, т.е. находятся в выделенных строках или столбцах. При этом переходят к третьему этапу;

2) имеется такой невыделенный нуль в строке, где нет нуля со звездочкой. Тогда переходят ко второму этапу, отметив этот нуль штрихом.

Второй этап. На этом этапе строят следующую цепочку из нулей матрицы Сk: исходный нуль со штрихом, нуль со звездочкой, расположенный в одном столбце с первым нулем со штрихом в одной строке с предшествующим нулем со звездочкой и т.д. Итак, цепочка образуется передвижением от 0' к 0* по столбцу, от 0* к 0' по строке и т.д.

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

Далее над элементами цепочки, стоящими на нечетных местах ( 0' ) -, ставим звездочки, уничтожая их над четными элементами ( 0* ). Затем уничтожаем все штрихи над элементами Сk и знаки выделения '+'. Количество независимых нулей будет увеличено на единицу. На этом (k+1) -я итерация закончена.

Третий этап. К этому этапу переходят после первого, если все нули матрицы Сk выделены. В таком случае среди невыделенных элементов Сk выбирают минимальный и обозначают его h (h>0). Далее вычитают h из всех элементов матрицы Сk, расположенных в невыделенных строках и прибавляют ко всем элементам, расположенным в выделенных столбцах. В результате получают новую матрицу С'k, эквивалентную Сk. Заметим, что при таком

преобразовании, все нули со звездочкой матрицы Сk остаются нулями и в С'k, кроме того, в ней появляются новые невыделенные нули. Поэтому переходят вновь к первому этапу. Завершив первый этап, в зависимости от его результата либо переходят ко второму этапу, либо вновь возвращаются к третьему этапу.

После конечного числа повторений очередной первый этап обязательно закончится переходом на второй этап. После его выполнения количество независимых нулей увеличится на единицу и (k+1) - я итерация будет закончена.

2.6.2 Входные данные

Входными данными является вводимая исходная матрица задачи о назначениях - матрица С в виде одномерного целочисленного массива.

2.6.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.6.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения Венгерским методом.

2.6.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.7 Функция, реализующая метод «Не реализованных прибылей (Этап 1)»

2.7.1 Методические ограничения

Алгоритм состоит из следующих шагов.

Шаг 1. Получить новую матрицу А, для этого из каждого элемента матрицы С, Cij вычитается сумма элементов по i строке и j столбцу (исключая сам элемент Cij).



Aij=3*Cij - УCik - УCkj (2.12)

Шаг 2. Включить в базисное решение элемент min{A}. Вычеркнуть соответствующую строку и столбец. Повторить шаг 1 для матрицы С, не учитывая вычеркнутые строки и столбцы.

Метод заканчивает работу когда все строки и столбцы вычеркнуты.

2.7.2 Входные данные

Входными данными является вводимая исходная матрица задачи о назначениях - матрица С в виде одномерного целочисленного массива.

2.7.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.7.4 Процессы обработки

Процесс обработки заключается в поиске опорного плана решения методом «Не реализованных прибылей (Этап 1)»

2.7.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.8 Функция, реализующая метод Не реализованных прибылей (Этап 2)

2.8.1 Методические ограничения

Алгоритм состоит из следующих шагов.

Предварительный шаг. Одним из методов рассчитывается опорный план решения.

Шаг 1. Получить новую матрицу А, по формуле

Aij= (Cij + Ckm) - (Cim + Ckj), (2.13)

где Cim и Ckj - элементы, входящие в базис.

Шаг 2. Если элемент Aij=min{A}

а) меньше нуля, то включить в базисное решение элементы Сij, Сkm

и выводим элементы из базиса Сim, Сkj

Затем переходим к шагу 1.

б) больше или равен нулю, то метод заканчивает работу и выводится результат.

2.8.2 Входные данные

Входными данными является исходная матрица задачи о назначениях и матрица опорного плана решения - матрицы С и Х в виде одномерных целочисленных массивов.

2.8.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.8.4 Процессы обработки

Процесс обработки заключается в улучшении опорного плана решения методом «Не реализованных прибылей (Этап 2)»

2.8.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.



2.9 Функция, реализующая метод Не реализованных прибылей (Этап 3)

2.9.1 Методические ограничения

Алгоритм состоит из следующих шагов.

Предварительный шаг. Одним из методов рассчитывается опорный план решения. Затем с помощью метода «Не реализованных прибылей (Этап 2)» опорный план решения улучшается.

Шаг 1. Получить новую матрицу А, для этого из всех элементов строки вычитается соответствующий базовый элемент этой строки.

Шаг 2. Ищется элемент Aij=min{A}.

Шаг 3. Начиная с Aij строится цикл, состоящий из базовых элементов в столбце и минимальных элементов в строке. Цикл замыкается на Aij. При этом в цикле рассчитывается значение Н - оценка введения в базис новых элементов.

Н = УCсij, (2.14)

где Cсij - элемент входящий в цикл.

Шаг 4. Если значение Н:

а) меньше нуля, то вводим новые базисные решения и удаляем старые, из тех элементов, что вошли в цикл. Переходим к шагу 1.

б) больше или равно нулю, то метод заканчивает работу и выводится результат.

2.9.2 Входные данные

Входными данными является исходная матрица задачи о назначениях и матрица опорного плана решения - матрицы С и Х в виде одномерных целочисленных массивов.



2.9.3 Инициирование работы

Инициирование осуществляется головным модулем при выборе пользователем соответствующего метода.

2.9.4 Процессы обработки

Процесс обработки заключается в получении оптимального опорного плана решения методом «Не реализованных прибылей (Этап 3)»

2.9.5 Выходные данные

Входными данными является матрица опорного плана решения - матрица Х в виде одномерного целочисленного массива.

2.10 Функция построения графика зависимости скорости работы метода от размерности исходной матрицы

Входные данные

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

Инициирование работы

Инициирование осуществляется при запуске функции пользователем.

Процессы обработки

Процесс обработки заключается в построения графика зависимости скорости работы метода от размерности исходной матрицы.

Выходные данные

Выходными данными является график зависимости скорости работы метода от размерности исходной матрицы.



2.11 Функция построения графика зависимости близости опорного плана к оптимальному от размерности исходной матрицы

Входные данные

Входными данными являются данные, полученные от функции оценки оптимальности выбранного метода.

Инициирование работы

Инициирование осуществляется при запуске функции пользователем.

Процессы обработки

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

Выходные данные

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

2.12 Функция оценки скорости работы метода

Входные данные

Входными данными является выбор пользователем оцениваемого метода.

Инициирование работы

Инициирование осуществляется функцией построения графика оценки скорости работы метода.

Процессы обработки

Процесс обработки заключается в оценке скорости работы метода.

Выходные данные

Выходными данными является время выполнения оцениваемого метода.



2.13 Функция оценки оптимальности результата работы метода

Методические ограничения

Оптимальность полученного результата оценивается следующим образом:

1) рассчитывается опорный план с помощью оцениваемого метода;

2) с помощью метода получения оптимального опорного плана рассчитывается значения целевой функции для тех же исходных данных;

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

4) коэффициент оптимальности равен отношению количества совпавших базисных элементов к рангу матрицы.

Входные данные

Входными данными является выбор пользователем оцениваемого метода.

Инициирование работы

Инициирование осуществляется функцией оценки оптимальности работы метода.

Процессы обработки

Процесс обработки заключается в оценке оптимальности полученного при работе метода результата.

Выходные данные

Выходными данными является коэффициент оптимальности полученного результата.

3. РАБОЧИЙ ПРОЕКТ

3.1 Общие сведения

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

В рамках дипломного проектирования разрабатывается ПО, предназначенное для оценки скорости и точности работы методов решения задачи о назначениях.

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

1) Реализуемые методы:

а) Метод Северо-Западного угла;

б) Метод Наименьшей стоимости;

в) Метод Фогеля;

г) Метод Не реализованных прибылей (этап 1);

д) Метод Не реализованных прибылей (этап 2);

е) Метод Не реализованных прибылей (этап 3);

ж) Метод Потенциалов;

з) Венгерский метод.

2) Реализация возможности комбинации различных методов.

3) Необходимость организации работы в диалоговом режиме.

4) Обеспечение минимального количества вводимых с клавиатуры символов и знаков.

5) Возможность использования мыши для работы с программой.

6) Возможность получения результатов работы на экране дисплея.

7) Возможность построения графиков зависимости скорости работы методов от размерности исходной матрицы.

8) Возможность построения графиков зависимости точности работы методов от размерности исходной матрицы.

3.2 Описание модулей

Модуль S_z

Предназначен для решения задачи о назначениях методом Северо-Западного угла

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
n	Переменная типа int	Размерность матрицы С

Процессы обработки

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

Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х

Схема передачи управления

Схема передачи управления представлена на рисунке 3.1



Рисунок 3.1

Модуль N_st

Предназначен для решения задачи о назначениях методом Наименьшей стоимости.

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Наименьшей стоимости (См. Приложение. Текст программы стр. 153).

Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х



Схема передачи управления

Схема передачи управления представлена на рисунке 3.2.

Рисунок 3.2

Модуль Fogel

Предназначен для решения задачи о назначениях методом Фогеля

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Фогеля (См. Приложение. Текст программы стр. 152).

Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х



Схема передачи управления

Схема передачи управления представлена на рисунке 3.3

Рисунок 3.3

Модуль Ner_p1

Предназначен для решения задачи о назначениях методом Не реализованных прибылей (этап 1)

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Не реализованных прибылей (этап 1) (См. Приложение. Текст программы стр. 154).

Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х



Схема передачи управления

Схема передачи управления представлена на рисунке 3.4

Рисунок 3.4

Модуль Ner_p2

Предназначен для решения задачи о назначениях методом Не реализованных прибылей (этап 2).

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
mas3	Динамический массив типа int	Матрица Х
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Не реализованных прибылей (этап 2) (См. Приложение. Текст программы стр. 154).

Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х

Схема передачи управления

Схема передачи управления представлена на рисунке 3.5

Рисунок 3.5

Модуль Ner_p3

Предназначен для решения задачи о назначениях методом Не реализованных прибылей (этап 3).

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
mas3	Динамический массив типа int	Матрица Х
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Не реализованных прибылей (этап 3) (См. Приложение. Текст программы стр. 155).



Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х

Схема передачи управления

Схема передачи управления представлена на рисунке 3.6

Рисунок 3.6

Модуль Potenc_m

Предназначен для решения задачи о назначениях методом Потенциалов

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
mas3	Динамический массив типа int	Матрица Х
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, методом Потенциалов (См. Приложение. Текст программы стр. 157).



Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х

Схема передачи управления

Схема передачи управления представлена на рисунке 3.7

Рисунок 3.7

Модуль Venger_m

Предназначен для решения задачи о назначениях Венгерским методом

Входные данные

Переменная	Тип	Назначение
mas2	Динамический массив типа int	Матрица С
n	Переменная типа int	Размерность матрицы С

Процессы обработки

Процессы обработки заключаются в решении задачи о назначениях, заданной матрицей С, Венгерским методом (См. Приложение. Текст программы стр. 161).



Выходные данные

Переменная	Тип	Назначение
mas3	Динамический массив типа int	Матрица Х

Схема передачи управления

Схема передачи управления представлена на рисунке 3.8.