Системное програмирование

Получили следующий  опорный план:

.

.

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

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

  Пример 3. Найти опорный план транспортной задачи методом минимального элемента.

Решение.

I. ; ; ; – 2 столбец исключен.

II. ; ; ; – 1 столбец исключен.

III. ; ; ; – 4 строка исключена.

IV. ; ; ; – 5 столбец исключен.

V. ; ; ; – 3 строка исключена.

VI. ; ; ; – 3 столбец исключен.

VII. ; ; ; – 2 строка исключена.

VIII. ; ; ; – 1 строка и 4 столбец исключены.

Опорный план:

 

Целевая функция:

2.3. Метод аппроксимации Фогеля.

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

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

Пример 4. Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в табл. 1

таблица 1

 

Решение. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке или столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке табл. 2. Так, в строке А₂ минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5 — 4=1. Точно так же разность между минимальными элементами в столбце В₄ равна 6—2=4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу В₄. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А₁и столбца B₄. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворим потребности пункта B₄. Поэтому исключим из рассмотрения столбец B₄ и будем считать запасы пункта А₁ равными 160—110 = 50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке табл. 2. Как видно из этой таблицы, наибольшая указанная разность соответствует строке А₁. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее со столбцом В₃. Следовательно, заполняем эту клетку. Поместив в нее число 50, тем самым предполагаем, что запасы в пункте А1полностью исчерпаны, а потребности в пункте В₃ стали равными 190—50= 140 ед. Исключим из рассмотрения строку А₁ и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки А₃ и столбца В₃, строки А₃ и столбца B₂, строки А₂ и столбца В₁ , строки А₂ и столбца В₂. 

таблица 2.

 

В результате получим  опорный план

При этом плане  общая стоимость перевозок такова:

S = 1*-50 + 2*110 + 4*120 + 5*20 + 2*30+3*140 = 1330.

  Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный  план, близкий к оптимальному, либо сам оптимальный план. Кстати, найденный выше опорный план транспортной задачи является и оптимальным. 
 

Вариант 3.

Этапы моделирования. Компьютерный эксперимент. Анализ результатов моделирования. 

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

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

Этапы математического  моделирования. 

Рис.1. Этапы  математического моделирования  на компьютере. 

   Первый  этап - определение  целей моделирования.

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

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

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

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

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

    Четвертый этап - разработка алгоритма  и составление  программы для ЭВМ.

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

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