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

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

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

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

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

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

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

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

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

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

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

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

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

n

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

i=1

    n           m

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

                                     n                        n          m

∑ c_ix_i −∑ ∑ a_ijd_ijx_i →max,

{ }xⁱ

                                    i=1                    i=1        j=1

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

x∈D

запись   .)

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

n

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

i=1

n

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

i=1

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

                                      n                       n           m

∑ c_ix_i −∑ ∑ a_ijd_ijx_i →max;

{ }x

                                     i=1                    i=1       j=1                                ⁱ

n

∑ a_ijx_i ≤  A_j, j = 1, …, m;

i=1

n

∑ x_i ≤  M;

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

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

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

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

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

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