Математическое программирование
Методическое пособие - Компьютеры, программирование
Другие методички по предмету Компьютеры, программирование
) yj - величина запаса к началу j-го месяца (Это число не содержит изделий, производимых в j-й месяц, величина запаса к началу 1-го месяца (y1) и к концу последнего (yn+1) заданы);
) dj - число изделий, которые должны быть отгружены в j-й месяц;
) - функция затрат на производство xj изделий в j-м месяце (может иметь и другой вид);
) hj - затраты на хранение единицы запаса, переходящей из месяца j в месяц (j+1);
) - функция затрат на производство и хранение в j-м месяце.
Задача состоит в определении плана производства (х1,х2,…,хn), компоненты которого удовлетворяют условиям материального баланса
xj +yj -dj = yj+1
и минимизируют суммарные затраты за весь период
.
По смыслу , ,. Заметим, что:
1)для любого месяца j величина запаса к концу месяца должна удовлетворять ограничениям
,
то есть объем производимой продукции xj в j-м месяце может быть настолько велик, что запас yj+1 удовлетворяет спрос на всех последующих месяцах, но не имеет смысла иметь yj+1 больше суммарного спроса всех последующих месяцев;
) из балансового уравнения получим .
Если учесть, что xj и yj должны быть целыми и неотрицательными, то имеем задачу целочисленного нелинейного программирования.
Составим функциональные уравнения. Пусть Fk(yk+1) - минимальные затраты за первые k месяцев.
Для k = 1:
при и . На начальном этапе при фиксированном значении y1 исходного запаса каждому значению y2 отвечает только одно значение x1.
Для k 2 :
при , и .
Применив процедуру динамического программирования, на последнем шаге k = n определяется значение xn* оптимального решения, а остальные компоненты определяются в результате прямого хода по формуле
.
Пример.
Лекция 16, 17
Программирование на сетях
Вопросы:
1. Основные понятия теории графов.
. Матричное задание графов. Упорядочение вершин.
. Сети и потоки на сетях. Постановка задачи о максимальном потоке.
. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о максимальном потоке.
. Элементы сетевого планирования.
1. Основные понятия теории графов
Теория графов - область дискретной математики, особенностью которой является геометрический подход к изучению объектов.
Основным объектом является граф и его обощения. Синонимами графа являются карта, диаграмма, сеть, лабиринт.
Результаты и методы теории графов используются в физике, химии, электротехнике, биологии, экономике, социологии и т.п. В экономике методы теории графов применяются при решении транспортных задач о перевозках, задач о назначениях, в календарном и сетевом планировании, при моделировании сложных технологических процессов, в решении задач массового обслуживания и задач управления динамическими процессами и т.п.
Формально граф определяется заданием двух (конечных) дискретных множеств: множеством вершин Х = {х1, …, хn} и множеством линий связи между ними
U = {u1,…,um}.
Линии связи ui называют ребрами, если не указана их ориентация, и - дугами, если задано направление связи.
Граф с дугами называют ориентированным графом (орграфом), - с ребрами - неориентированным.
Пример. а) орграф б) неориентированный граф
Вершины хi и хj, связанные дугой/ребром uk, называют концевыми вершинами этой дуги/ребра. Если концевые вершины совпадают, то дуга/ребро называется петлей. Дуги/ребра с одинаковыми концевыми вершинами называются параллельными. Граф без петель и параллельных линий связи называют простым.
Концевые вершины хi и хj одной дуги/ребра или дуги up и uq с общей вершиной называют смежными.
Если вершина хi является концевой для дуги/ребра uk, то эти xi и uk инцидентны: вершина хi инцидентна дуге/ребру uk, а дуга/ребро uk - вершине хi.
Т.о., смежность - отношение связанности между однородными элементами (вершинами или дугами/ребрами), а инцидентность - между разнородными (вершинами и дугами/ребрами).
Вершина, не имеющая отношений смежности, называется излированной.
Графы с одинаковым отношением инцидентности называются изоморфными.
Пример.
Изоморфные графы отличаются только геометрической конфигурацией.
Число дуг/ребер, инцидентных вершине хi, называют степенью этой вершины P(xi). В орграфе различают полустепень захода P+(xi) и полустепень исхода P-(xi) вершины хi, равные соответственно числу заходящих в хi и исходящих из хi дуг. P+(xi) + P-(xi) = P(xi).
В ряде случаев дугам ставятся в соответствие числовые характеристики (длина пути, время смены состояний, пропускная способность связи и т.д.), называемые весом дуг/ребер, а графы с такими числами называют взвешенными.
Граф называют простым, если он не содержит петель и параллельных дуг/ребер. Простой граф, в котором каждая пара вершин смежна, называют полным.
Путь в орграфе - последовательность неповторяющихся дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь, проходящий через все вершины только по одному разу, называется гамильтоновым. Путь, содержащий все дуги только по одному разу, называют эйлеровым. Конечный путь, у которого начальная вершина совпадает с конечной, называют контуром. В неориентированном графе путь называют цепью, а контур - циклом.
Орграф (неориентированный граф) называют связным, если любые две его вершины можно соединить путем (цепью). В противном случае - несвязным. Связный орграф называют сильно связным, если для любых двух вершин хi и хj сущ