Анализ задачи или модели

4. Анализ задачи или модели.

4.1 Определение опорного плана транспортной задачи

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

Метод минимального элемента

Алгоритм метода минимального элемента состоит в следующем.

Просматривается вся матрица тарифов перевозок, и из нее выбирается позиция с наименьшим значением тарифа C, затем просматриваются значения наличия запасов на складе A и потребности у потребителя B, затем в данную клетку записывается величина D=MIN(A,B). Из запасов соответствующего склада и потребностей магазина вычитается величина D . Если запас товара на складе исчерпан, то эта строка исключается из дальнейшего рассмотрения. Если потребность магазина в товаре удовлетворена полностью, то этот столбец исключается из дальнейшего рассмотрения. Может быть случай , когда одновременно исключаются и строка и столбец, этот случай называется вырожденным. В дальнейшем весь процесс повторяется до тех пор , пока не будет исчерпан весь запас товаров на складах и не будет удовлетворена потребность всех магазинов. По полученной матрице перевозок вычисляется целевая функция задачи Z.

Лист

Кп-км-п-44-2203-99

Метод Фогеля

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

Метод двойного предпочтения

В начальной своей стадии этот метод похож на метод минимального элемента , но для столбцов. Просматривается первый столбец матрицы тарифов, в нем находится наименьший элемент. Затем проверяется , минимален ли этот элемент в своей строке. Если элемент минимален в своей строке, то по методу минимального элемента в эту клетку заносится значение D=MIN(A,B),

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

Как и любая задача линейного программирования, необходимо построить первоначальный опорный план для решения задачи. Одним из методов построения исходного опорного плана является так называемый метод «северо-западного» угла.

Лист

Кп-км-п-44-2203-99

Метод северо-западного угла

Метод состоит в следующем. Просматривается матрица тарифов перевозок C , начиная с левого верхнего угла (клетки). В эту клетку записывается величина D=MIN(A,B). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс опять повторяется для левой верхней клетки оставшейся матрицы и так до тех пор пока весь запас товаров не будет исчерпан. Полученный опорный план не оптимален, поэтому его дальнейшее решение продолжают одним из вышерассмотренных методов.

Лист

Кп-км-п-44-2203-99

2. Предмодельный анализ.

2.1 Анализ существующих аналогов и подсистем

Программное обеспечение для решения задач линейного программирования и в частности, транспортной задачи разработано уже в конце 60-ых – начале 70-ых годов и было реализовано как пакет программ – библиотек. Данный пакет задач был реализован на таких алгоритмических языках как Алгол, Фортран. В западных разработках в основном применялся алгоритмический язык Кобол. С появлением персональных компьютеров данный пакет был перемещен на ПК, с учетом особенностей реализации трансляторов вышеперечисленных языков на ПК. Также дополнительно были реализованы пакеты программ, в основном усилиями вузов на языках Паскаль, Си. Перенос программного обеспечения на ПК открыл новые возможности в решении задач линейного программирования и наглядного отображения результатов вычислении, что отсутствовало на больших вычислительных системах – мэйнфреймах.

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

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

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

Одним из бурно развивающихся алгоритмических языков является Pascal и его диалекты. Первоначально этот язык был создан для обучения студентов основам программирования, ввиду своей простоты и наглядности конструкции. Он был создан Никлаусом Виртом, и послужил основой для целого семейства паскале-подобных языков – Modula, Classcal, Object Pascal.

Наиболее развитую систему программирования на языке Pascal построила фирма Borland – Turbo Pascal. Первоначально она была реализована для DOS, с появлением Windows , она была перенесена в нее. И наконец, была выпущена новая версия для Windows – Delphi.

Лист

Кп-км-п-44-2203-99

5.2 Среда разработки Delphi

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

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

"быстрота, простота, эффективность, надежность".

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

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

Н

Лист

Кп-км-п-44-2203-99

о вот проста ли Delphi? И да, и нет. Она лишь кажется простой, поскольку многие "подводные камни" скрыты от разработчика. Однако чем больше изучаешь ее, тем больше становится ясной ее глубина, которая одновременно и вызывает уважение, и пугает. Лишь со временем приходит понимание того, что для написания действительно мощных и функциональных приложений требуется постоянное изучение Delphi.

Блок-схема меню определение опорного плана (Transtask.pas)

1

2

3

Да

нет

4 Да

5

нет