Математическое программирование

3) d_j - число изделий, которые должны быть отгружены в j-й месяц;

4) - функция затрат на производство x_j изделий в j-м месяце (может иметь и другой вид);

5) h_j - затраты на хранение единицы запаса, переходящей из месяца j в месяц (j+1);

6) - функция затрат на производство и хранение в j-м месяце.

Задача состоит в определении плана производства (х₁,х₂,…,х_n), компоненты которого удовлетворяют условиям материального баланса

x_j +y_j -d_j = y_j+1

и минимизируют суммарные затраты за весь период

.

По смыслу , ,. Заметим, что:

1) для любого месяца j величина запаса к концу месяца должна удовлетворять ограничениям

,

то есть объем производимой продукции x_j в j-м месяце может быть настолько велик, что запас y_j+1 удовлетворяет спрос на всех последующих месяцах, но не имеет смысла иметь y_j+1 больше суммарного спроса всех последующих месяцев;

2) из балансового уравнения получим .

Если учесть, что x_j и y_j должны быть целыми и неотрицательными, то имеем задачу целочисленного нелинейного программирования.

Составим функциональные уравнения. Пусть F_k(y_k+1) - минимальные затраты за первые k месяцев.

Для k = 1:

при и . На начальном этапе при фиксированном значении y₁ исходного запаса каждому значению y₂ отвечает только одно значение x₁.

Для k 2 :

при , и .

Применив процедуру динамического программирования, на последнем шаге k = n определяется значение x_n* оптимального решения, а остальные компоненты определяются в результате прямого хода по формуле

.

Пример.

Лекция 16, 17

Программирование на сетях

Вопросы:

1. Основные понятия теории графов.

2. Матричное задание графов. Упорядочение вершин.

3. Сети и потоки на сетях. Постановка задачи о максимальном потоке.

4. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке.

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

1. Основные понятия теории графов

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

Основным объектом является граф и его обощения. Синонимами графа являются карта, диаграмма, сеть, лабиринт.

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

Формально граф определяется заданием двух (конечных) дискретных множеств: множеством вершин Х = {х₁, …, х_n} и множеством линий связи между ними

U = {u₁,…,u_m}.

Линии связи u_i называют ребрами, если не указана их ориентация, и - дугами, если задано направление связи.

Граф с дугами называют ориентированным графом (орграфом), - с ребрами - неориентированным.

Пример. а) орграф б) неориентированный граф

Вершины х_i и х_j, связанные дугой/ребром u_k, называют концевыми вершинами этой дуги/ребра. Если концевые вершины совпадают, то дуга/ребро называется петлей. Дуги/ребра с одинаковыми концевыми вершинами называются параллельными. Граф без петель и параллельных линий связи называют простым.

Концевые вершины х_i и х_j одной дуги/ребра или дуги u_p и u_q с общей вершиной называют смежными.

Если вершина х_i является концевой для дуги/ребра u_k, то эти x_i и u_k инцидентны: вершина х_i инцидентна дуге/ребру u_k, а дуга/ребро u_k - вершине х_i.

Т.о., смежность - отношение связанности между однородными элементами (вершинами или дугами/ребрами), а инцидентность - между разнородными (вершинами и дугами/ребрами).

Вершина, не имеющая отношений смежности, называется излированной.

Графы с одинаковым отношением инцидентности называются изоморфными.

Пример.

Изоморфные графы отличаются только геометрической конфигурацией.

Число дуг/ребер, инцидентных вершине х_i, называют степенью этой вершины P(x_i). В орграфе различают полустепень захода P⁺(x_i) и полустепень исхода P^-(x_i) вершины х_i, равные соответственно числу заходящих в х_i и исходящих из х_i дуг. P⁺(x_i) + P^-(x_i) = P(x_i).

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

Граф называют простым, если он не содержит петель и параллельных дуг/ребер. Простой граф, в котором каждая пара вершин смежна, называют полным.

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

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

Пример.

2. Матричное задание графа. Упорядочение вершин

При большом числе вершин и дуг/ребер изображение графа теряет наглядность. В этих случаях для задания графов и работы с ними используют матрицы.

1. Граф без петель, имеющий n вершин и m дуг/ребер можно задать матрицей инциденций, строки которой соответствуют вершинам, а столбцы - дугам. Элементы матрицы, размерности nm, определяются по формуле

+1, если дуга uj входит в вершину xi,



Для неориентированного графа вместо ”-1” ставится 1.

Пример.

2. Граф можно матрицей смежности вершин, строки и столбцы которой соответствуют вершинам графа. Элементы матрицы S_ij равны числу дуг/ребер, идущих из х_i в х_j. Матрица смежности для неориентированного графа будет симметричной.

Пример.

Аналогично может быть задана матрица смежности дуг/ребер.

Расчеты в задачах, связанных с графами, заметно упрощаются, если их элементы упорядочены.

Если существует путь из х_i в х_j, то вершина х_i называется предшествующей вершине х_j, а х_j - последующей х_i.

Упорядочение вершин связного графа без контуров означает разбиение его вершин на группы так, чтобы:

1) вершины 1-й группы не имели предшествующих, а вершины последней - последующих;

2) вершины любой другой группы не имели предшествующих в следующей группе;

3) вершины одной и той же группы не соединялись с дугами.

Графический способ упорядочения вершин (алгоритм Фалкерсона).

1. Находятся вершины графа, в которые не входит ни одна дуга. Такие вершины образуют 1-ю группу.

2. Вершины и выходящие из них дуги установленной группы исключаются из дальней- шего рассмотрения.

3. Устанавливается следующая группа вершин, в которые не входит ни одна дуга.

4. Если процесс упорядочения не окончен, то переход п. 2.

5. В полученном графе, изоморфном исходному, перенумеровываются вершины.

3. Сети и потоки на сетях. Постановка задачи о максимальном потоке

Сеть - конечный взвешенный связный орграф без контуров и петель, ориентированный в одном общем направлении от вершины I (исток, вход) к вершине S (сток, выход).

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

Максимальное количество r_ij вещества, которое может пропустить за единицу времени ребро (i, j), называется его пропускной способностью. В общем случае r_ij ? r_ji. Если вершины не соединены, r_ij = 0. Т.к. нет петель, то r_ii = 0. Пропускную способность можно задать квадратной матрицей.

Количество х_ij вещества, проходящего по ребру (i, j) в единицу времени, называется потоком по ребру (i, j). Предполагается, что если из х_i в х_j направляется поток х_ij , то из x_j в x_i направляется поток (-х_ij)

x_ij = - x_ji . (1)

Поток по каждому ребру не превышает его пропускную способность

x_ij r_ij (i = ; j = ) . (2)

Количество вещества, притекающее в вершину, равно количеству вещества, вытекающего из неё

 (i I, S ). (3)

Совокупность Х = потоков по всем рёбрам сети называют потоком по сети. Общее количество вещества вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.

F = x_Ij = x_iS. (4)

Функцию F называют мощностью потока.

Если на сети задан поток Х = , то ребро (i,j) называется насыщенным, если поток x_ij по нему совпадает с его пропускной способностью r_ij (x_ij = r_ij) , и ненасыщенным, если x_ij < rij .

Задачу о максимальном потоке можно сформулировать следующим образом: найти совокупность Х* = {x*_ij} потоков x*_ij по всем рёбрам сети, которая удовлетворяет условиям (1) - (3) и максимизирует линейную функцию (4) . Это типичная ЗЛП.

Замечание. Не всякие n² чисел могут задавать поток по сети. Только такие n² чисел x_ij задают поток, которые удовлетворяют условиям (1) - (3) .

Пример.

4. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке

Пусть дана некоторая сеть. Разобьём множество вершин сети на два непересекающихся множества А и В так, чтобы исток I попал в А, а сток S - в В. В этом случае на сети задан разрез. Совокупность ребер (i,j), начальные вершины которых принадлежат А, а конечные - В, называется разрезом сети (А/B).

Пропускной способностью разреза называют сумму пропускных способностей всех рёбер разреза R (A/B) = r_ij.

Сумма всех потоков x_ij по всем рёбрам разреза называется потоком через разрез

X(A/B) = x_ij.

Теорема Форда-Фалкерсона: на любой сети максимальная величина потока равна минимальной пропускной способности разреза.

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

Алгоритм решения задачи о максимальном потоке.

1. Построить начальный поток Х = (чем больше величина выбранного потока, тем быстрее решается задача).

2. На основе заданной сети строится новая сеть:

а) каждая дуга, для которой остаётся в новой сети с первоначальной r_ij;

б) каждая дуга для которой заменяется на две:

- одна дуга того же направления с пропускной способностью r_ij-;

- вторая дуга противоположенного направления с пропускной способностью .

3. Если в новой сети можно найти ненулевой поток из I в S, то этот поток прибавляет-ся к начальному. В результате получается новый поток и переходят к п. 2.

Если же в новой сети отсутствуют ненулевые потоки из I в S, то максимальный поток сети построен.

Пример.

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

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

Пример.

Составление сетевого графика требует выполнения определённых организационных и формальных правил.

Организационные правила:

1) составляется подробный перечень всех работ от отправного момента до целевого результата;

2) определяется продолжительность всех работ;

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

Формальные правила:

1) сетевой график должен иметь только одно исходное событие - исток и только одно завершающее - сток;

2) любые два события должны быть связанны не более чем одной работой и, наоборот, каждая работа должна заключаться между двумя событиями;

3) сеть не должна иметь контуров, петель, изолированных участков, не связанных работами с её остальной частью;

4) сетевой график должен быть упорядочен по вершинам.

Замечание: для выполнения формальных правил и учёта ряда технологических процессов вводят фиктивные события и работы. В частности.

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

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

3. Если следует учесть зависимость событий, не связанных реальными работами (различные работы a и b выполняются на одном оборудовании), то вводится фиктивная работа c:

В случаях 1) - 3) фиктивные работы не имеют протяжённости во времени.

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

К основным параметрам сетевого графика относятся:

1) продолжительность t* критического пути, т.е. наиболее протяжённого во времени пути от истока к истоку;

2) резервы времени событий R(i),определяющие предельно допустимые задержки событий i, не приводящие к изменению t*;

3) полный резерв времени промежуточной работы R_ij, определяющий максимальный запас времени, на который можно задержать начало работы или увеличить её продолжительность, не изменяя t*;

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

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

Если события i дают начало работам, продолжающимся t_ij ед. времени и завершающимся событием j, то ожидаемый (ранний) срок t_i наступления j-ого события равен

, (1)

(1-е событие - «исток»),

где t_i - ожидаемый (ранний) срок i - го события (i<j).

Наиболее поздний срок наступления i - го события

T_i = min(T_j - t_ij), i =

T_n = t_n = t* (n-e coбытие - «сток») (2)

Т =

Резерв времени наступления i-го события

(3)

Свободный резерв времени работы (i,j)

(4)

Полный резерв времени работы (i,j)

(5)

Расчёты параметров сетевого графика проводят в 5 этапов, изображая события кружками с четырьмя секторами, которые заполняются по ходу выполнения этапов:

1) находят все t_i по формулам (1), при этом перемещаются по сетевому графику согласно номерам событий слева направо;

2) находят T_i по формулам (2), при этом перемещаются по сетевому графику от стока влево по мере убывания номеров событий;

3) определяю R_i по формуле (3)

4) выделяют критический путь;

5) вычисляют все остальные параметры.

Пример.

Замечания:

1. Резерв времени наступления события R_i позволяет варьировать сроки готовности события i в пределах t_i T_i.

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

3. Полные резервы времени использовать одновременно удаётся не всегда.

Правила построения двойственной задачи.

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

Свойства двойственных задач (правила).

9. Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу неизвестных прямой задачи.

10. Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.

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

12. Свободные члены ограничений двойственной задачи являются коэффициентами целевой функции прямой задачи.

13. Если ограничения прямой задачи записаны со знаком меньше или равно (), то ограничения двойственной задачи записываются со знаком больше или равно ( ).

14. Если ограничение прямой задачи задано в виде уравнения, то соответствующее неизвестное двойственной задачи не ограничено знаком.

15. Если какое-либо неизвестное прямой задачи не ограничено знаком, то соответствующее ограничение двойственной задачи будет задано в виде равенства.

16. Если целевая функция прямой задачи сформулирована на максимум, то целевая функция двойственной задачи будет сформулирована на минимум.

Существует много различных комбинаций ограничений и целевой функции для записи исходной задачи. Для упрощения задачи построения двойственной задачи запишем прямую задачу в некотором стандартном виде прямой задачи. Этот вид предполагает, что:

4) все ограничения имеют знак ;

5) целевая функция сформулирована на максимум;

6) все неизвестные неотрицательны.

Чтобы записать прямую задачу в стандартном виде, необходимо:

5) неравенство со знаком умножить на (-1);

6) равенство заменить на два неравенства противоположных знаков, одно из которых следует умножить на (-1);

7) формулировку целевой функции меняют заменой знаков коэффициентов на противоположные;

8) если переменное x_j не ограничено знаком, его можно представить в виде разности двух неотрицательных переменных.

Пример. Составить двойственную задачу к исходной.

 .

программирование симплекс матричный граф

Решение. 1) Стандартный вид прямой задачи.

2) Двойственная задача:

Задачу можно записать в виде, соответствующем исходной прямой задаче, если заменить: а) - не ограничена знаком,

б) два последних ограничения соответствуют равенству.

.

Размещено на Allbest.ru