Математическое моделирование. Задача реберной раскраски графа

Страницы работы

9 страниц (Word-файл)

Фрагмент текста работы

1.  Математическое моделирование

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

Процесс решения проблемы методами исследования операций включает такие этапы, как:

− уяснение содержательной постановки задачи;

− построение математической модели (формализация основных аспектов задачи);

− поиск оптимального решения.

Настоящая глава посвящена математическому моделированию − процессу перехода от содержательной постановки к математической задаче.

Пример 1.1. Рассмотрим завод, который способен производить изделия из данного перечня. Для изготовления конкретного изделия необходимо определенное количество различных ресурсов. Объемы ресурсов ограничены. Известны стоимость единицы каждого ресурса, цена реализации изделия и мощность предприятия, т. е. максимальное число изделий, которое может быть произведено в течение рабочего дня.

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

Постановка. Пусть выпускаются изделия типа i = 1, …, n, и используются ресурсы типа j = 1, …, m. Мощность завода обозначим через M. На изготовление одного изделия i-го типа завод использует aij единиц ресурса j-го типа, его общий объем равен Aj. Затраты на приобретение единицы ресурса j для изготовления изделия типа i равны dij. Пусть ci – цена одного изделия i-го типа, а переменная x– количество таких изделий, выпускаемых заводом. 

Требуется найти объем выпускаемых заводом изделий, т. е. значения переменных x1, …, xn, при которых прибыль завода максимальна.

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

n

(∑ cixi)         за       вычетом       затрат       на       использованные      ресурсы

i=1

    n           m

(∑ ∑ aijdijxi). Следовательно, критерий задачи запишется в виде  i=1 j=1

                                     n                        n          m

cixi −∑ ∑ aijdijxi →max,

{ }xi

                                    i=1                    i=1        j=1

где стрелкой показана цель – максимизация, а под максимумом указаны переменные, выбором значений которых он достигается. (Для представления критерия наряду с формой f x( )→max используется эквивалентная

xD

запись   .)

В допустимом решении переменные задачи должны удовлетворять ог-

n

раничениям на объем используемых ресурсов ∑ aijxi Aj, а также огра-

i=1

n

ничениям на мощность производства ∑ xi M. 

i=1

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

                                      n                       n           m

cixi −∑ ∑ aijdijxi →max;

{ }x

                                     i=1                    i=1       j=1                                i

n

aijxi   Aj, j = 1, …, m;

i=1

n

xi   M;

i=1 xi Z+, i = 1, …, n, где Z+ – множество неотрицательных целых чисел.

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

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

1)  осуществлять прямое соединение пользователей, тогда единица информации, равная пропускной способности, достигнет адресата за единицу времени;

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

Предполагается, что линия связи может быть загружена одновременно

Похожие материалы

Информация о работе

Предмет:
Математика
Тип:
Конспекты лекций
Размер файла:
236 Kb
Скачали:
0