Л 3. Сетевые модели

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

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

Предприятия Склады

1 1

2

2 3

3 4

Эта схема представляет собой ориентированный граф с семью узлами (вершинами) и семьюдугами.

Классическая транспортная задача.

Рассмотрим частный случай, когда имеются производители с ресурсами и потребители со спросами , соответственно. Если известны издержки с_ij доставки единицы ресурса от i^го производителя к j^ому потребителю, то нетрудно построить классическую транспортную модель, вводя управляемые переменные - допустимое количество товара, перемещаемое от i^го поставщика j^ому потребителю. Переменные удовлетворяют ограничениям

,

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

Изобразим транспортную модель в виде графа, собрав пометки в таблицу.

Производители Потребители

Ресурсы Спрос

Потребители   Поставщики	В1	В2	…	Вn	Предложение
А1	с11   х11	с12     х12	…	с1n     х1n	S1
А2	с21   х21	с22   х22	…	с2n   х2n	S2
...	…	…	…	…	…
Аm	сm   хm1	сm2   хm2	…	сmn   хmn	Sm
Спрос	D1	D2	…	Dn

В таблице кроме издержек с_ij представлены: переменные х_ij, возможности S_i поставщиков и спрос D_j – потребителей.

Теперь можно в рамках этой модели решать задачу оптимального по стоимости закрепления поставщиков за производителями

,

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

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

Задача о назначениях

Вариантом транспортной задачи является следующая задача о назначениях, когда имеется n работ, каждую из которых может выполнять один из исполнителей. Если известны стоимости с_ij исполнения i^ой работы j^ым исполнителем, то, используя транспортную модель, можно распределить исполнителей по работам, назначив одного исполнителя ровно на одну работу так, чтобы минимизировать общие затраты. Правда, теперь в рамках транспортной модели придется использовать т.н. булевы переменные

если i^я работа исполняется j^ым работником

в остальных случаях. i,j=

C участием этих переменных формируется оптимизационная задача

При небольших значениях величины n решение этой задачи можно получить простым перебором.

Пример 2. Пусть для 3^х работ и 3^х исполнителей матрица затрат имеет вид

С =

Здесь возможные назначения осуществляются одним из шести векторов (123), (132), (213), (231), (312), (321), координаты которых указывают на номер работы для 1^го, 2^го,3^го исполнителя, соответственно. Вычисляя с помощью матрицы С значение функции в каждой из шести точек, обнаруживаем, что оптимальное назначение имеет вид (1,3,2), т.е. первый исполнитель назначается на первую работу, второй – на третью, а третий – на вторую. Минимальные суммарные затраты теперь равны 4.

В общем случае без использования специальных методов приходится перебирать вариантов назначения.

Дата добавления: 2014-01-06