Предположим, что требуется проанализировать проект с точки зрения минимальных временных затрат на его выполнение. Для этого проект разбивают на отдельные работы, или действия, оценивают время, необходимое на проведение каждой из них, и записывают последовательность операций, показывающую, какие работы должны быть закончены, прежде чем начнутся другие. Затем вычерчивается диаграмма работ, на которой каждая работа изображается направленным ребром, и определяется критический путь, имеющий наибольшую общую продолжительность. Он и определяет минимум временных затрат на выполнение проекта.
Покажем, как делается временная оценка проекта, на примере строительства небольшого загородного дома.
В табл. 1 и 2 указаны работы, их продолжительность и последовательность выполнения.
Таблица 1
Работа | Продолжительность | Работа | Продолжительность |
A | 2 | F | 2 |
B | 7 | G | 6 |
C | 15 | H | 8 |
D | 8 | I | 2 |
E | 10 | J | 3 |
Здесь А — заливка фундамента, В — изготовление оконных рам и дверей, С — изготовление встроенных шкафов и мебели, D — монтаж водопроводной системы, Е — возведение стен, F — оштукатуривание стен, G — возведение крыши, Н — благоустройство территории, I — установка встроенных шкафов и мебели, J — покраска. Продолжительность работ указана в днях.
Таблица 2
| Таблица 3
|
Перенумеруем последовательно все работы, не имеющие предшествующих.
В данном случае это работы А — (a1), В — (а2) и С — (a3).
Затем последовательно нумеруем остальные работы таким образом, чтобы все предшествующие им были уже занумерованы:
Е — (а4) (следует за (a1) и (а2)),
D — (а5) (следует за (а4)),
G — (а6) (следует за (а4)),
F — (а7) (следует за (а5) и (а6)),
Н — (а8) (следует за (а6)),
I — (а9) (следует за (а3), (а7) и (а8)),
J — (а10) (следует за (а9)).
В результате получаем табл. 3. Составим диаграмму работ.
В верхней части рис. 2.18 каждая работа представлена на временной шкале (точка отсчета совпадает с началом работ) горизонтальным отрезком. Длины этих отрезков пропорциональны продолжительности соответствующих работ, а положения их левых концов определяются возможностью их выполнения (см. табл. 3).
Рис. 2.18
В нижней части рис. 2.18 изображена направленная сеть, построенная по данным табл. 3 и в более наглядной форме показывающая, как именно связаны между собой работы по проекту и в какой очередности их следует выполнять. Ребра, обозначенные пунктиром, необходимы для соблюдения правильной последовательности операций.
Ж
ирным выделен критический путь (направленный путь из начального события в конечное, имеющий наибольшую общую продолжительность).
Подсчитаем временные затраты на критическом пути. Имеем:
7 + 10 + 6 + 8 + 2 + 3 = 36.
Отсюда следует, что анализируемый проект может быть реализован за 36 дней и ни днем раньше.
Замечание. Всякая работа на критическом пути называется критической (малейшая задержка с началом ее выполнения увеличивает общую продолжительность работ). В данном случае критическими являются работы
а2, а4, а6, а8, а9, а10, и
ли, возвращаясь к исходным обозначениям,
В, Е, G, H, I, J.
Определение всех таких работ важно для эффективного составления проекта. В отличие от критической работы момент начала работы, не входящей в критический путь, может быть несколько сдвинут (вперед) без увеличения общей продолжительности. Важно, чтобы сдвинутая некритическая работа была завершена до начала критических работ, которым она предшествует.
Тема 3. Линейное программирование.
План темы.
Понятие линейности и линейного программирования. Общая задача линейного программирования. Графический и симплекс-методы решения задач линейного программирования. Задача о выпуске продукции. Транспортная задача.Линейные модели являются одним из наиболее активно используемых классов математических моделей.
Линейность – это свойство математических выражений и функций. Выражение вида 
, где x и y – переменные величины, а a и b – постоянные числа, называется линейным относительно переменных x и y.
В случае если переменных больше двух – x1, x2, … , xn, линейное выражение относительно этих переменных имеет вид 
, где а1, а2, …, аn – постоянные числа.
Линейное программирование является наиболее известным и одним их наиболее широко используемых инструментов в научном менеджменте. Программирование в данном термине имеет смысл планирования. Линейное же означает, что ищется экстремум линейной целевой функции при линейных ограничениях (линейных уравнениях и линейных неравенствах).
Приведем область задач, где наиболее широко используется линейное программирование:
- задачи о составлении смеси, цель которых заключается в выборе наиболее экономичной смеси ингредиентов (руды, нефти, пищевых продуктов и др.) при учете ограничений на физический или химический состав смеси и на наличие необходимых материалов;
- задачи производства, целью которых является подбор наиболее выгодной производственной программы выпуска одного или нескольких видов продукции при условии некоторого числа ограничений на сырье;
- задачи распределения, цель которых состоит в том, чтобы организовать доставку материалов от некоторого числа источников к некоторому числу потребителей так, чтобы оказались минимальными либо расходы по этой доставке, либо время, затрачиваемое на нее, либо некоторая комбинация того и другого. В простейшем виде эта задача о перевозках (транспортная задача).
Наиболее распространенным методом решения задач линейного программирования является симплекс-метод. В простейшем случае, когда число переменных равно двум, удобен простой и наглядный графический метод.
Общая задача линейного программирования
Стандартная математическая формулировка общей задачи линейного программирования выглядит так:
Требуется найти экстремальное значение показателя эффективности (целевой функции) 
,
(линейной функции элементов решения x1, x2, …, xn) при линейных ограничительных условиях, накладываемых на элементы решения:
;
;
,
, 
, …, 
, где аik, bk, ci – заданные числа.
Кратко запись общей программы линейного программирования выглядит следующим образом:
,
, i = 1, 2, … , m,
, k = 1, 2, … , n.
Двумерные задачи линейного программирования решаются графически. В общем виде, когда в задаче участвуют N-неизвестных, можно сказать, что область допустимых решений, задаваемая системой ограничивающих условий, представляется выпуклым многогранником в n-мерном пространстве и оптимальное значение целевой функции достигается в одной или нескольких вершинах. Решить данные задачи графически, когда количество переменных более 3 весьма затруднительно. Существует универсальный способ решения задач линейного программирования, называемый симплекс-методом.
Симплекс-метод является основным в линейном программировании. Решение задачи начинается с рассмотрений одной из вершин многогранника. Если исследуемая вершина не соответствует максимуму (минимуму), то переходят к соседней, увеличивая значение функции цели при решении задачи на максимум и уменьшая при решении задачи на минимум. Таким образом, переход от одной вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов гарантируется нахождение оптимального значения или установление того факта, что задача неразрешима.
Этот метод является универсальным, применимым к любой задаче линейного программирования в канонической форме. Система ограничений здесь - система линейных уравнений, в которой количество неизвестных больше количества уравнений. Если ранг системы равен r, то мы можем выбрать r неизвестных, которые выразим через остальные неизвестные. Для определенности предположим, что выбраны первые, идущие подряд, неизвестные X1, X2, ..., Xr. Тогда наша система уравнений может быть записана как
,
,
………………………………………………..
К такому виду можно привести любую совместную систему, например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные свободными.
Придавая определенные значения свободным переменным и вычисляя значения базисных (выраженных через свободные), получаются различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Интерес представляют особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменные X1, X2, ..., Xr, то решение {b1, b2,..., br, 0, ..., 0} будет опорным при условии, что b1, b2,..., br ≥ 0.
Имея систему ограничений, приведенную к общему виду, то есть к системе m линейных уравнений с n переменными (m < n), находят любое базисное решение этой системы, заботясь только о том, чтобы найти его как можно проще.
Если первое же найденное базисное решение оказалось допустимым, то проверяют его на оптимальность. Если оно не оптимально, то, осуществляется переход к другому, обязательно допустимому базисному решению.
Симплексный метод гарантирует, что при этом новом решении линейная форма, если и не достигнет оптимума, то приблизится к нему. С новым допустимым базисным решением поступают так же, пока не находят решение, которое является оптимальным.
Если первое найденное базисное решение окажется недопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, которые приближают нас к области допустимых решений, пока на каком-то шаге решения либо базисное решение окажется допустимым и к нему применяют алгоритм симплексного метода, либо мы убеждаемся в противоречивости системы ограничений.
Таким образом, применение симплексного метода распадается на два этапа: нахождение допустимого базисного решения системы ограничений или установление факта ее несовместности; нахождение оптимального решения.
При этом каждый этап может включать несколько шагов, соответствующих тому или иному базисному решению. Но так как число базисных решений всегда ограниченно, то ограниченно и число шагов симплексного метода.
Приведенная схема симплексного метода явно выражает его алгоритмический характер (характер четкого предписания о выполнении последовательных операций), что позволяет успешно программировать и реализовать этот метод на ЭВМ. Задачи же с небольшим числом переменных и ограничений могут быть решены симплексным методом вручную.
Вычисления по симплекс-методу организуются в виде симплекс-таблиц, которые являются сокращенной записью задачи линейного программирования в канонической форме. Перед составлением симплекс-таблицы задача должна быть преобразована, система ограничений приведена к допустимому базисному виду, c помощью которого из целевой функции должны быть исключены базисные переменные. Вопрос об этих предварительных преобразованиях мы рассмотрим ниже. Сейчас же будем считать, что они уже выполнены и задача имеет вид:
,
,
………………………………………………..
.
, i= 1, 2,…, n.
Здесь для определенности записи считается, что в качестве базисных переменных можно взять переменные X1, X2, ..., Xr и что при этом b1, b2,..., br ≥ 0 (соответствующее базисное решение является опорным).
Для составления симплекс-таблицы во всех равенствах в условии задачи члены, содержащие переменные, переносятся в левую часть, свободные оставляются справа, т. е. задача записывается в виде системы равенств:
x1 – a/1,r+1xr+1 - …- a/1nxn = b/1,
x2 – a/2,r+1xr+1 - …- a/2nxn = b/2,
........................................
xr – a/r, r+1xr+1 - …- a/rnxn = b/r,
Z - γr+1xr+1 - … - γnxn = γ0.
Далее эта система оформляется в виде симплекс-таблиц:
Баз. перем. | Своб. члены | X1 | X2 | …. | Xr | Xr+1 | Xr+2 | …. | Xn |
X1 | b/1 | 1 | 0 | …. | 0 | -a1,r+1 | -a1,r+2 | …. | - |
X2 | b/2 | 0 | 1 | …. | 0 | -a2,r+1 | -a2,r+2 | …. | -a2n |
…. | …. | …. | …. | …. | …. | …. | …. | …. | …. |
Xr | b/r | 0 | 0 | …. | 1 | -ar, r+1 | -ar, r+2 | …. | -arn |
Z | γ0 | 0 | 0 | …. | 0 | -γr+1 | -γr+2 | …. | -γn |
Примечание. Названия базисных переменных здесь взяты лишь для определенности записи и в реальной таблице могут оказаться другими.
Задача о выпуске продукции
Фирма выпускает два вида древесно-стружечных плит – обычные и улучшенные. При этом проводятся две основные операции – прессование и отделка. Требуется рассчитать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы:
Затраты | Партия из 100 плит | Имеющиеся ресурсы на месяц | |
Обычные | Улучшен-ные | ||
Древесина, м кв Время на прессование, часы Время на отделку, часы Прочие затраты, долл. | 20 4 4 30 | 40 6 4 50 | 4000 900 600 6000 |
За каждые 100 обычных плит фирма получает прибыль, равную 80 долл., а за каждые 100 плит улучшенного вида – 100 долл.
Решение. Пусть x – количество партий в 100 плит обычного вида, а y – то же для плит улучшенного качества. Тогда ожидаемую прибыль можно записать так:
.
Для изготовления x партий в 100 плит обычного вида и y партий в 100 плит улучшенного вида требуется
20x +40y
м кв. древесины. Ясно, что полученное число не может превосходить количество материала, имеющегося в наличии, т. е. 4000 м кв. Тем самым ограничения на материал имеют вид:
20x + 40y £ 4000.
Подобным же образом записываются ограничения на время изготовления и затраты:
Прессование: 4x + 6y £ 900,
Отделка: 4x + 4y £ 600,
Затраты: 30x + 50y £ 6000.
Подведем итог: требуется найти такие значения x и y, которые бы соответствовали следующим условиям:
20x + 40y £ 4000,
4x + 6y £ 900,
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 |
