Коврижных А.Ю., Конончук Е.А. и др. Прикладное программное обеспечение для решения экономических задач

Подождите немного. Документ загружается.

Рис.7

На рис.8 показано полученное значение целевой функции. Оно полностью

совпадает с расчетным значением.

Рис.8

Полученный контур можно увидеть на рис.7 в ячейках, соответствующих

изменяемым ячейкам: 1 в изменяемых ячейках на рис.7 означает включение

соответствующей дуги в контур. При расчетах с помощью MS EXCEL получен

контур, приведенный на рис.9 справа.

Рис.9

7. Решение задачи о максимальном потоке и минимальном

разрезе.

Для получения математической модели задачи введем неотрицательные

целочисленные переменные x

, которые интерпретируются как величина

потока по дуге (i, j). Тогда математическая модель может иметь, например,

такой вид, как на рис.1.

Ограничение (2) требует, чтобы величина потока, выходящего из

источника s, была равна величине потока, пришедшего в вершину t.

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

через вершины графа G.

Ограничение (5) требует, чтобы все переменные

модели были неотрицательными целочисленными переменными.

{}()

⎪

⎩

⎪

⎨

⎧

∈∀∈

≤≤

≠≠∈∀=−

=−

→

∑∑

∑

∆∈

. ..., ,2 ,1,

; , , ..., ,2 ,1 0

,max

njiZx

tisinixx

ijij

jiij

iisj

(1)

(2)

(3)

(4)

(5)

Рис.1

Задание. Используя приведенную на рис.2 сеть, найти максимальный

поток с использованием надстройки «Поиск решения».

Рис.2

Выполнение. Расположим исходные данные на рабочем листе так, как на

рис.3. В столбец Е введены ограничения в соответствии с моделью для данной

индивидуальной задачи. На рис.4 приведено окно диалога надстройки «Поиск

решения», а на рис. 5 – полученное решение. Величина максимального потока

в точности равна полученному значению при использовании алгоритма Форда

Фалкерсона.

Рис.3

Рис.4

Рис.5

8. Решение задачи о поиске кратчайшего пути

Для получения математической модели задачи введем булевы переменные

, которые интерпретируются следующим образом: x

=1, если дуга (i, j)

входит в маршрут; x

=0, если дуга (i, j) не входит в маршрут. Тогда

математическая модель может иметь, например, такой вид, как на рис.1.

Ограничение (2) требует, чтобы искомый путь начинался в вершине s.

Ограничение (3) требует, чтобы искомый путь заканчивался в вершине t.

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

через вершины графа G. Ограничение (5)

требует, чтобы все переменные

модели были булевыми.

,min

∑∑

∆∈

→

ijij

(1)

(2)

(3)

(4)

{}()

{} { }()

⎪

⎩

⎪

⎨

⎧

∈∀∈

≠≠∈∀=−

−=−

=−

∑∑

. ..., ,2 ,1, 1,0

; , , ..., ,2 ,1 0

njix

tisinixx

jiij

ittj

issj

(5)

Рис.1

Задание. Используя приведенный на рис.2 граф, найти кратчайший путь

между вершинами 1 и 10 с использованием надстройки «Поиск решения».

Выполнение. В заданном графе 10 вершин и 16 дуг. Следовательно,

переменными математической модели этой индивидуальной задачи о

построении кратчайшего пути являются 16 переменных:

, , , ,, , , , , , , , , ,

10,7786710,669575446353424231512

xxxxxxxxxxxxxx

. ,

10,910,8

Рис.2

Математическая постановка такой индивидуальной задачи имеет

следующий вид:

,min 107825 6

7543239465

10,910,810,7786710,6

69575446353424231512

∆∈

→++++++

+++

xxxxxx

xxxxxxxxxx

где множество ограничений выглядит так, как на рис.3.

Воспользуемся надстройкой «Поиск решения», входящей в состав MS

EXCEL. Расположим исходные данные на рабочем листе, например, так, как

на рис.4. В ячейках показаны формулы, связывающие переменные модели.

Целевая функция находится в ячейке Е19. На рис.5 приведено окно диалога

надстройки перед запуском на выполнение. На

рис.6 показан результат работы

надстройки, а на рис.7 – путь из вершины 1 в вершину 10 минимальной длины.

Это значение совпадает с решением, полученным в соответствии с алгоритмом

Дейкстры.

{}

⎪

⎩

⎪

⎨

⎧

∈

=−

=−−+

=−−−

=−−+

=−+

=−−

=+++

.1 ,0 . , , ,

, ,, , , , , , , , , ,

;

10,910,810,778

6710,669575446353424231512

10,969

10,878

19,7786757

10,6696746

57541535

462434

353423

242312

10,910,810,710,6

1512

xxxx

xxxxxxxxxxxx

xxxx

xxx

xxxx

Рис.3

Рис.4

Рис.5

Рис.6

Рис.7

ЭКОНОМИЧЕСКОЕ МОДЕЛИРОВАНИЕ СРЕДСТВАМИ

MAPLE

1. Возможности пакета.

1. Пользовательский интерфейс

Пакет Maple – интерактивная программа, позволяющая проводить

аналитические выкладки и вычисления, снабженная средствами двумерной и

трехмерной графики, имеющая мощный язык программирования и богатую

библиотеку математических формул и сведений. Работа с Maple заключается в

том, что пользователь вводит математическое выражение и инструкции

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

(или не

получив) ответ, пользователь вводит новые инструкции и так далее –

взаимодействие с пакетом происходит в диалоговом режиме. Благодаря

собственному языку программирования высокого уровня, введенные

выражения и инструкции, а также результаты выполнения команд – формулы,

графики, таблицы и числа – запоминаются в едином документе (worksheet).

Это обеспечивает уникальную технологию работы, когда чуть ли не все

этапы

математического исследования можно отразить в одном документе.

Запуск системы

Запуск Maple производится, как обычно, из меню Пуск. Найдя строчку

Maple , необходимо открыть подменю и щелкнуть на команде Maple

Интерфейс системы Maple.

Обзор интерфейса Maple

Как у всех приложений под Windows интерфейс Maple имеет ряд

характерных элементов, перечисленных ниже:

• строка заголовка (сверху);

• строка главного меню;

• главная панель инструментов;

• контекстная панель инструментов, вид которой зависит от режима

работы с Maple;

• окно ввода и редактирования документов;

• строка состояния (в самом низу окна).

Рис.1

Пользовательский интерфейс Maple позволяет готовить документы,

содержащие одновременно текстовые комментарии, команды входного языка

(с возможным преобразованием их в естественную математическую форму),

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

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

данных и результатов вычислений, а также удобство их повторного

использования.

В основе пользовательского интерфейса

Maple лежит графический

многооконный интерфейс операционной системы Windows. Управление

системой Maple возможно с помощью главного меню, панелей инструментов

и палитр, а также «горячих» клавиш. Поддерживаются также многие

возможности мыши, присущие приложениям под Windows.

Пользователь Maple работает с документами, которые являются

одновременно описаниями алгоритмов решения задач, программами и