36061
Нахождение начального решения для транспортной задачи
Доклад
Информатика, кибернетика и программирование
Для решения транспортной задачи разработано несколько методов каждый из которых отличается от другого методом заполнения матрицы перевозок. Метод минимального элемента Алгоритм метода минимального элемента состоит в следующем. Метод Фогеля Метод состоит в следующем. В выбранной строке или столбце как и в методе минимального элемента заполняется клетка с наименьшим значением тарифа.
Русский
2013-09-20
30.5 KB
5 чел.
2. Нахождение начального решения для транспортной задачи.
Для решения транспортной задачи разработано несколько методов, каждый из которых отличается от другого методом заполнения матрицы перевозок.
Существуют два типа транспортной задачи: открытая и закрытая. Транспортная задача называется открытой если сумма запасов товара на складах отличается от суммы потребностей товаров у магазинов. Транспортная задача называется закрытой , если сумма запасов товара на складах равняется сумме потребностей магазинов. Решение существует только для закрытой транспортной задачи, поэтому если транспортная задача открытая , то ее надо привести к закрытому типу. Для этого в случае , если запас товара на складах превышает потребность магазинов, то вводят фиктивного потребителя, который выбирает весь избыток товара. В случае же, если существует дефицит товара, т.е. потребность магазинов больше, чем запас товаров на складах, то вводят фиктивного поставщика, с фиктивным запасом товара на складе. В обоих случаях в матрице тарифов перевозок C данному складу или магазину проставляется нулевая цена перевозки.
Метод минимального элемента
Алгоритм метода минимального элемента состоит в следующем. Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения.
Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай , когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.
Метод Фогеля
Метод состоит в следующем. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей выбирается строка или столбец с максимальной разность. В выбранной строке или столбце , как и в методе минимального элемента, заполняется клетка с наименьшим значением тарифа. Затем обнулявшаяся строка или столбец исключаются из рассмотрения и весь процесс повторяется до полного исчерпания запаса товаров на складах. По полученной матрице перевозок вычисляется целевая функция Z.
Метод двойного предпочтения
В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B), соответствующие запас и потребность уменьшаются на эту величину. Обнулившаяся строка или столбец исключаются из рассмотрения и процесс повторяется, начиная с первого неисключенного столбца. Если найденный минимальный элемент не минимален в своей строке, то происходит переход к следующему столбцу и так до тех пор, пока не будет найден такой элемент. По полученной матрице перевозок вычисляется целевая функция Z. Этот метод требует интенсивных операции обмена с памятью , поэтому более громоздок посравнению с остальными и требует больших вычислительных ресурсов. Как и любая задача линейного программирования, необходимо построить первоначальный опорный план для решения задачи. Одним из методов построения исходного опорного плана является так называемый метод «северо-западного» угла.
Метод северо-западного угла
Метод состоит в следующем. Просматривается матрица тарифов перевозок C, начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клеткиоставшейся матрицы и так до тех пор пока весь запас товаров не будет
исчерпан. Полученный опорный план не оптимален, поэтому его дальнейшее решение продолжают одним из вышерассмотренных методов. Определение начального допустимого решения
А также другие работы, которые могут Вас заинтересовать | |||
29331. | Формула Юлла-Нильсена | 38.5 KB | |
Чем больше линиатура растра тем ближе расположены точки тем хуже функция размытия. ∆S получила название растискивания точки. На самом деле в этом значении растискивания точки значительную долю вносит рассеивание света в процессе визуального рассмотрения оттиска. Конечно в это ∆S удобно внести все искажения которые возникают не только в процессе визуального восприятия рассеивания света а также реальное растискивание в процессе печати и изменение размера растровой точки в копировальноформном процессе. | |||
29332. | Технологическая настройка системы обработки под реальный технологический процесс | 54 KB | |
Имеется специальный тестобъект который по сути дела представляет собой шкалу цветового охвата которая доступна в виртуальном виде то есть в виде информации записанной на магнитный носитель. Однако в некоторых случаях получение такой информации не оправдано изза разовых тиражей или если часть информации не доступна. Второй метод основан на использовании некоторой стандартной информации которая включается в состав программного обеспечения обработки изобразительной информации фирмой изготовителем. Эта информации по сути своей позволяет... | |||
29333. | Цветовые системы, используемые в обрабатывающей станции | 58 KB | |
Недостатки такого выражения: неоднозначность системы координат RGB и аппаратная зависимость неясное представление о цвете на основе соотношения этих сигналов Воздействие на один из каналов приводит к изменению цвета которое трудно предсказать. Если хотим получить насыщенные цвета должны работать в пределах 50 светлоты По координате а цвет меняется от Зеленого до Пурпурного. У нас имеются две группы основных цветов: цвета аддитивного синтеза однозональные цвета: Красный Зеленый Синий двузональные цвета субтрактивного синтеза:... | |||
29334. | Калибровка монитора без использования специальных аппаратных средств (по разработкам фирмы Gretag) | 56 KB | |
Однако для более точной коррекции цвета на экране монитора и корректного представления его в колориметрических координатах необходимо провести стадию технологической калибровки монитора. Это приводит к тому что если не принять специальных мер коррекции голубая краска выделится на синефильтровой и зеленофильтровой фотоформе будет запечатываться соответственно желтой и пурпурной краской. По сути дела при правильной настройки системы и правильной работе в соответствующих цветовых пространствах задача базовой коррекции решается автоматически... | |||
29335. | Селективная коррекция | 56.5 KB | |
Цветопроба в процессе коррекции Без проведения цветопробы оптимальная цветовая коррекция является затруднительной и может не дать удовлетворительных результатов. Контроль этого изображения экранная цветопроба. Такая цветопроба называется контрактной цветопробой. Такая цветопроба называется аналоговой. | |||
29336. | Коррекция структурных свойств изображения | 54.5 KB | |
Коррекция резкости изображения Коррекция резкости изображения в системе поэлементной обработки может осуществляться двумя методами: аппертурным и программным. Аппертурный метод включает аппертурную коррекцию резкости изображения по методу нерезкого маскирования при этом коррекция производится непосредственно при сканировании изображения. В соответствие с этой процедурой производится обработка массива цифровой информации формируя сигнал нерезкого изображения путем интегрирования нескольких пиксель в окрестностях обрабатываемой пиксели. | |||
29337. | Геометрические преобразования в системе поэлементной обработки изображения | 62 KB | |
В процессе преобразования на этапе сканирования формируется пиксель размер которого уже выбран в соответствии с масштабом окончательного изображения. Сложнее при масштабировании изображения записанного в виде цифрового массива высокого разрешения. Сложнее при увеличении или уменьшении изображения не в целое число раз. | |||
29338. | Технология обработки изобразительной информации | 53.5 KB | |
Соотношение свойств изображения на входе системы и свойств изображения которые должны получить на выходе системы диктует ряд преобразований это технологические преобразования. Часть системных преобразований может служить в качестве технологических например преобразование изображения из позитивного в негативное при фотографировании так же могут быть использованы изменения полярности и зеркальности. Так обработка штрихового изображения и растрового изображения цветного или чернобелого осуществляется с использованием разных технологий.... | |||
29339. | Вычисление экспонирования | 39.5 KB | |
При правильном выборе экспозиции для широких и узких штрихов и просветов очень узкие штрихи и просветы будут воспроизведены с искажениями. При необходимости возможно воспроизвести геометрически точно штрихи и просветы относящиеся к классу очень узких или суперузких при использовании материала с бесконечно большим коэффициентом контрастности. Однако при таком выборе условий экспонирования все остальные штрихи и просветы в том числе широкие и узкие будут воспроизводиться геометрически не точно а с определенными искажениями геометрических... | |||