Шапорев С.Д. Дискретная математика - файл n14.doc

приобрести
Шапорев С.Д. Дискретная математика
скачать (1595.4 kb.)
Доступные файлы (14):
n1.doc1008kb.24.06.2000 17:47скачать
n2.doc580kb.29.02.2000 18:08скачать
n3.doc957kb.07.03.2000 15:50скачать
n4.doc492kb.24.06.2000 17:37скачать
n5.doc1198kb.19.04.2000 15:24скачать
n6.doc985kb.19.04.2000 21:35скачать
n7.doc771kb.07.05.2000 17:26скачать
n8.doc992kb.08.05.2000 16:38скачать
n9.doc217kb.08.05.2000 19:26скачать
n10.doc1581kb.26.03.2000 20:59скачать
n11.doc1011kb.31.03.2000 22:04скачать
n12.doc1025kb.31.03.2000 22:09скачать
n13.doc1691kb.05.04.2000 16:10скачать
n14.doc960kb.09.04.2000 12:05скачать

n14.doc





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

Первый шаг.

20 Рассмотрим промежу-

4 5 30 ток . Здесь рас-

20 5 6 положено четыре рабо-

3 4 50 ты: (1, 2), (1, 3), (1, 4) и

3 5 (2, 5). Для выявления

50 работ, подлежащих от-

2 5 срочке, прежде всего

30 упорядочим их. Выпи-

1 4 шем полные резервы

40 времени: ,

1 3 , ,

50 . В порядке

1 2 возрастания полного

резерва времени прис-

0 5 10 15 20 воим номера работам

70 40 120 120 120 100 50 30 (1, 3) - №1, (1, 4) - №2,

(1, 2) - №3, (2, 5) - №4.

шкала потребления ресурса В отведенный ресурс

укладываются только две работы №1. и №2. Поэтому работу №4, то есть работу (1, 2), а вслед за ней и работу (2, 5) сдвигаем до момента ; ресурс времени это позволяет, критический срок от этого не увеличится. Положение работ после первого шага показано на предыдущем рисунке.

Второй шаг.

20 Рассмотрим отрезок

4 5 30 . Здесь

20 5 6 , ,

3 4 50 , .

3 5 Номера работ по возрас-

50 танию полного резерва

2 5 времени: (3, 5) - №1,

30 (1, 2) - №2, (3, 4) - №2,

1 4 (4, 5) - №3. Предел ре-

40 сурса полностью выби-

1 3 рают первая и вторая

50 работы. Таким образом,

1 2 следует сдвинуть рабо-

ту (3,4), а вместе с ней

0 5 10 15 20 и работу (4, 5) на один

70 40 100 120 120 50 30 день вправо. Положение

работ комплекса после

шкала потребления ресурса второго шага показано

на рисунке слева.

Третий шаг.

20 . Полные резер-

4 5 30 вы времени работ на

20 5 6 этом отрезке равны

3 4 50 , ,

3 5 . Работа (1, 2)

50 уже длится, следовате-

2 5 льно сдвигать надо ра-

30 боту (3, 4) и следую-

1 4 щую за ней работу (4, 5).

40 Четвертый шаг.

1 3 . Работы (1, 2) и

50 (3, 5) уже длятся, у ра-

1 2 боты (3, 4) полный ре-

зерв времени равен ну-

0 5 10 15 20 лю. Тем не менее имен-

70 40 100 120 120 70 20 30 но эту работу необходи-

мо сдвигать на один

шкала потребления ресурса вправо. Вместе с ней

сдвинутся работы (4, 5) и (5, 6), тем самым критический срок будет увеличен на один день. Положение работ комплекса после четвертого шага изображено на предыдущем рисунке.

Пятый шаг.

20 . Ра-

4 5 30 боты (3, 5) и

20 5 6 (4, 5) уже длят-

3 4 50 ся, необходимо

3 5 сдвигать на че-

50 тыре дня вправо

2 5 работу (2, 5).

30 При этом на че-

1 4 тыре дня уве-

40 личится крити-

1 3 ческий срок.

50 Теперь ресурс

1 2 нигде не пре-

вышен, плани-

0 5 10 15 20 25 28 рование работ

70 40 100 70 50 30 комплекса за-

кончено. Ито-

шкала потребления ресурса говое положе-

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

По последнему линейному графику составлена следующая таблица со сроками начала и окончания работ комплекса (таблица приведена в начале следующей страницы).

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


Сроки

Работы

(1, 2)

(1, 3)

(1, 4)

(2, 5)

(3, 4)

(3, 5)

(4, 5)

(5, 6)



7

0

0

15

6

6

10

20



10

6

4

20

7

15

15

28


1). Анализируется шкала потребления ресурса, и выделяются отрезки, где это потребление превышает установленный предел.

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

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

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

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

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

В нашем примере работы, входящие в новый критический путь, есть:

(1, 3)-(3, 5)-(2, 5)-(5, 6), а его продолжительность увеличилась на пять дней. На практике обычно возникают еще более сложные задачи с дополнительными ограничениями на состав и сроки проведения работ. Для их решения разработаны более сложные алгоритмы сетевого планирования и составления расписаний.
Глава 6. Математическое программирование.

а). Линейное программирование.
§ 6.1. Специфика задач линейного программирования. Различные формы

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

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

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

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

Систематическое исследование задач линейного программирования и разработка общих методов их решения начаты в работах Л.В. Канторовича в 1939 году. Основной метод решения задач линейного программирования – симплексный метод – был опубликован в 1949 году Данцигом.

Приведем простейший пример составления математической модели задачи линейного программирования – задачу о «диете» (задачу о смеси). Все такие задачи могут быть отнесены к разряду экономико-математических, так как в них присутствует экономический показатель – стоимость.

Пусть известен перечень продуктов для составления диеты: Рассматриваются пищевые характеристики этих продуктов, например, витамины, жиры, белки, калорийность и тому подобное. Обозначим эти характеристики Пусть для каждого продукта известна его «разложимость» по пищевым характеристикам, то есть количественное содержание в одной единице измерения продукта указанных компонент Тогда можно составить следующую таблицу, элементы которой равны содержанию компоненты в единице продукта .

Пусть рацион – это набор продуктов на некоторый срок. Тог-



Канторович Л. В. (1-1 г.г.) - советский математик.

Данциг (1-1 г.г.) – немецкий математик.











































































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



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

Итак, математическая формулировка задачи выбора рациона состоит в следующем. Найти при условиях

(6.1.1)

Эта же задача еще компактнее может быть переписана в матричной форме так.

Найти (6.1.2)

где (6.1.3)

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

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

Пусть - количество единиц груза в -ом пункте отправления , - потребность в грузе в -ом пункте назначения , - стоимость перевозки единицы груза из -ого пункта в -ый, - планируемое для перевозки количество единиц груза из -ого пункта в -ый. Тогда - общая стоимость перевозок, - количество груза, вывезенного из -ого пункта, - количество груза, доставленного в -ый пункт. Сама задача в простейшем случае имеет вид: найти

(6.1.4)

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

а). Стандартная задача линейного программирования.

Найти

(6.1.5)

б). Каноническая задача линейного программирования.

Найти

(6.1.6)

Основной метод решения задачи линейного программирования – симплекс метод – разработан именно для канонической задачи.

б). Общая (смешанная) задача линейного программирования.

Найти

(6.1.7)

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

Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации