Распределительная матрица задачи №6.01

Станки	Ткани	Фонд времени , ч
В1	В2	В3	В4
А1	2 ( ) ( ) 24
А2
А3
Объем выпуска , м

ЦФ имеет смысл себестоимости выпуска запланированного количества ткани всех видов

Ограничения имеют вид

Преобразуем РЗ в ТЗ, т.е. представим исходную задачу в виде, когда ткани производит только один станок – базовый и все параметры задачи согласуем с его характеристиками. В качестве базового можно выбирать любой из станков. Мы выберем станок с максимальной производительностью, т.е. . По формуле (6.2) определим производительности станков , нормированные относительно производительности базового станка:

;

;

.

Таким образом, базовый станок работает в два раза быстрей второго станка и в три раза быстрей третьего.

Пересчитаем фонды времени станков по формуле (6.3):

[ч]; [ч]; [ч].

Из этих величин следует, что тот объем работ, который второй станок выполняет за свой фонд времени 220 ч базовый станок сможет выполнить за 110 ч. Аналогично объем работ, который третий станок выполняет за 180 ч базовый выполнит за 60 ч.

Пересчитаем плановое задание по формуле (6.4):

[ч]; [ч]; [ч]; [ч].

Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 50 ч, второго вида – за 30 ч и т.д.

Пересчет себестоимостей производим по формуле (6.5), например:

[руб./ч]; [руб./ч]; [руб./ч].

В полученной ТЗ условие баланса (4.2) не выполняется, т.к. суммарный фонд времени станков больше, чем это необходимо для выполнения плана по выпуску всех тканей (260 ч > 200 ч). Введем фиктивный столбец и запишем все пересчитанные параметры РЗ в транспортную матрицу (см. табл.6.3). Фиктивные тарифы для упрощения приравняем к нулю.

Таблица 6.3

Транспортная матрица задачи №6.01

Станки	Ткани	Фонд времени , ч
В1	В2	В3	В4	ВФ
А1
А2
А3
Объем выпуска , ч

Для упрощения вместо оптимального решения рассмотрим опорный план , найденный методом северо-западного угла.

[ч].

Преобразуем опорный план ТЗ в опорный план РЗ согласно (6.6)

[ч].

Таким образом, первый станок должен 50 ч производить ткань первого вида, 30 ч – ткань второго вида и 10 ч – ткань третьего вида. Второй станок должен 180 ч производить ткань третьего вида и 40 ч – ткань четвертого вида. А третий станок будет простаивать, не выпуская ткань вообще, т.к. согласно решению, его загрузка находится в фиктивном столбце ( ).

Определим, сколько метров ткани каждого вида должны произвести станки по формуле (6.7)

[м].

Определим общую себестоимость производства по формуле (6.1), используя вычисленные значения элементов матрицы

(руб.).

6.3. Варианты задач для самостоятельного решения

Задача №6.1

Решите РЗ, исходные данные которой приведены в табл.6.4.

Таблица 6.4

Распределительная матрица задачи №6.1

Производитель	Продукция	Фонд времени, ч
В1	В2	В3
А1	1 ( , руб./т) ( , т/ч) 6
А2
А3
А4
Объем выпуска, т

Задача №6.2

Некоторая фирма содержит три магазина, которым еженедельно следует доставлять товар: первому магазину – 1050 кг сыра, второму – 600 мешков муки, третьему – 2400 упаковок сока. Товары доставляются грузовыми машинами четырех транспортных предприятий. Количество машин на этих предприятиях составляет 65, 40, 45 и 20 машин. Все машины имеют различную грузоподъемность [ед.тов./маш.], в зависимости от типа машины и типа перевозимого груза

.

Стоимости использования машин [руб./маш.] в зависимости от дальности перевозки и емкости машины равны

.

Организуйте экономичную перевозку товаров (при решении используйте метод северо-западного угла). Будьте внимательны при определении исходных себестоимостей перевозок распределительной задачи.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Акоф Р., Сасиени М. Основы исследования операций. М.: Мир, 1971.

2. Акулич И.Л. Математическое программирование в примерах и задачах. М.: Высшая школа, 1986.

3. Зайченко Ю.П. Исследование операций. Киев: Вища школа, 1979.

4. Таха Х.А. Введение в исследование операций. В 2-х книгах. М.: Мир, 1985.

5. Таха Х.А. Введение в исследование операций. М.: Издательский дом "Вильямс", 2001.

6. Кузнецов А.В., Сакович В.А., Холод Н.И. и др. Сборник задач и упражнений по высшей математике. Математическое программирование. Минск: Вышэйшая школа, 1995.

7. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика: математическое программирование. Минск: Вышэйшая школа, 2001.

8. Эддоус М. , Стенсфилд Р. Методы принятия решений. М.: ЮНИТИ, 1997.

Часть III. СЕТЕВОЕ ПЛАНИРОВАНИЕ

ПОСТРОЕНИЕ СЕТЕВЫХ МОДЕЛЕЙ

Теоретическое введение

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

· действительной, т.е. требующей затрат времени;

· фиктивной, т.е. формально не требующей затрат времени.

Фиктивная работа может реально существовать, например, "передача документов от одного отдела к другому". Если продолжительность такой работы несоизмеримо мала по сравнению с продолжительностью других работ проекта, то формально ее принимают равной 0. Существуют фиктивные работы, которым в реальности не соответствуют никакие действия. Такие фиктивные работы только представляют связь между другими работами сетевой модели.

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

Взаимосвязь работ и событий, необходимых для достижения конечной цели проекта, изображается с помощью сетевого графика(сетевой модели). Работы изображаются стрелками, которые соединяют вершины, изображающие события. Начало и окончание любой работы описываются парой событий, которые называются начальным и конечным событиями. Поэтому для указания конкретной работы используют код работы , состоящий из номеров начального (i-го) и конечного (j-го) событий (рис.7.1).

Рис.7.1. Кодирование работы

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

7.2. Методические рекомендации по построению сетевых моделей

При построении сетевого графика необходимо следовать следующим правилам:

· длина стрелки не зависит от времени выполнения работы;

· стрелка может не быть прямолинейным отрезком;

· для действительных работ используются сплошные, а для фиктивных – пунктирные стрелки;

· каждая операция должна быть представлена только одной стрелкой;

· между одними и теми же событиями не должно быть параллельных работ, т.е. работ с одинаковыми кодами;

· следует избегать пересечения стрелок;

· не должно быть стрелок, направленных справа налево;

· номер начального события должен быть меньше номера конечного события;

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

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

· не должно быть циклов (рис.7.2).

Рис.7.2. Недопустимость циклов

Исходные данные для построения сетевой модели могут задаваться различными способами, например,

· описанием предполагаемого проекта. В этом случае необходимо самостоятельно разбить его на отдельные работы и установить их взаимные связи;

· списком работ проекта. В этом случае необходимо проанализировать содержание работ и установить существующие между ними связи;

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

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

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

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

Рис.7.3. Устранение параллельности двух работ

Задача №7.01

Постройте сетевую модель программы опроса общественного мнения, которая включает разработку (A; 1 день) и распечатку анкет (B; 0,5 дня), прием на работу (C; 2 дня) и обучение (D; 2 дня) персонала, выбор опрашиваемых лиц (E; 2 дня), рассылку им анкет (F; 1 день) и анализ полученных данных (G; 5 дней).

Решение

Из условия задачи нам известно содержание работ, но явно не указаны взаимосвязи между работами. Поэтому для их установления необходимо проанализировать смысл каждой конкретной работы и выяснить, какие из остальных работ должны ей непосредственно предшествовать. Исходной работой, начинающей сетевой график, в данном случае является "прием на работу" (С), поскольку все остальные работы должны выполняться уже принятыми на работу сотрудниками (рис.7.4). Перед выполнением всех работ по опросу общественного мнения сотрудников необходимо обучить персонал (D). Перед тем как разослать анкеты (F), их надо разработать (A), распечатать (B) и выбрать опрашиваемых лиц (E), причем работу с анкетами и выбор лиц можно выполнять одновременно. Завершающей работой проекта является анализ полученных данных (G), который нельзя выполнить без предварительной рассылки анкет (F). В результате этих рассуждений построим сетевую модель и пронумеруем события модели (см. рис.7.4).

Рис.7.4. Сетевая модель программы опроса общественного мнения

Задача №7.02

Постройте сетевую модель, включающую работы A, B, C, ..., L, которая отображает следующее упорядочение работ:

1) A, B и C – исходные операции проекта;

2) A и B предшествуют D;

3) B предшествует E, F и H;

4) F и C предшествует G;

5) E и H предшествуют I и J;

6) C, D, F и J предшествуют K;

7) K предшествует L.

Решение

В пункте 1) условия явно указано, что A, B и C являются исходными работами, поэтому изобразим их тремя стрелками, выходящими из исходного события 1. Пункт 2) условия означает, что стрелки работ A и B должны окончиться в одном событии, из которого выйдет стрелка работы D. Но поскольку стрелки работ A и B также и начинаются в одном событии, то имеет место параллельность работ, которая недопустима правилами построения сетевых моделей (см. рис.7.5).

Рис.7.5. Устранение параллельности работ A и B

Для ее устранения введем дополнительное событие 2, в которое войдет работа B, после чего соединим события 2 и 3, в которые входят работы A и B пунктирной стрелкой фиктивной работы. В данном случае фиктивная работа (2,3) не соответствует никакой реальной работе, а лишь отображает логическую связь между работами B и D. Дальнейшее построение рассмотрим с помощью рис.7.6

Рис.7.6. Сетевая модель задачи №7.02

Согласно пункту 3) условия задачи из события 2, выходят три стрелки работ E, F и H. Согласно пункту 4) условия задачи стрелки работ C и F должны войти в общее событие, из которого выйдет стрелка работы G. Проблема с параллельностью работ E и H [пункт 5) условия задачи] решается путем введения дополнительного события 5 и фиктивной работы (5,6). Для отображения в сетевой модели пункта 6) условия задачи введем стрелки работ D и J в событие 7, а связь работ F и C с работой K отобразим с помощью фиктивной работы (4,7). Стрелки работ F и C нельзя было напрямую вводить в событие 7, потому что после них должна следовать работа G, которая с работами D и J никак не связана. Стрелка работы L выходит из события 8, т.е. после окончания работы K в соответствии с пунктом 7) условия задачи.

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

7.3. Варианты задач для самостоятельного решения

Задача №7.1

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

Таблица 7.1

Исходные данные задачи №7.1

Работа	Непосредственно предшествующие работы	Время, ед. времени
A – cоставление сметы затрат	–
B – согласование оценок	A
C – покупка собственного оборудования	B
D – подготовка конструкторских проектов	B
E – строительство основного цеха	D
F – монтаж оборудования	C,E
G – испытание оборудования	F
H – определение типа модели	D
I – проектирование внешнего корпуса	D
J – создание внешнего корпуса	H,I
K – конечная сборка	G,J
L – контрольная проверка	K

Задача №7.2

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

Таблица 7.2

Исходные данные задачи №7.2

Содержание работы	Длительность, ед.времени
A – выбор музыкального произведения
B – разучивание музыки
C – размножение нотных партий
D – репетиции хора
E – получение канделябров в прокат
F – закупка свечей
G – установка канделябров со свечами
H – закупка декораций
I – установка декораций
J – заказ костюмов для хора
K – отглаживание костюмов
L – проверка системы усиления звука
M – настройка системы усиления звука
N – генеральная репетиция хора
O – банкет
P – проведение концерта

Задача №7.3

Постройте сетевую модель, используя упорядочение работ из табл.7.3.

Таблица 7.3

Исходные данные задачи №7.3

Название	Непосредственно предшествующие работы	Длительность, ед.времени
A	–
B	–
C	–
D	A,B
E	B,C
F	C
G	D,E
H	F,G

Задача №7.4

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

Таблица 7.4

Исходные данные задачи №7.4

Содержание работы	Непосредственно предшествующие работы	Длительность, ед. времени
A – оценка состава и содержания работ	–
B – осведомление потребителей электроэнергии о временном отключении системы	A	0,5
C – составление заявки на материалы и оборудование	A
D – обследование района проведения работ	A	0,5
E – доставка опор и материалов	C,D
F – распределение опор по точкам монтажа	E	3,5
G – увязка точек монтажа	D	0,5
H – разметка точек монтажа	G	0,5
I – рытье ям под опоры	H
J – монтаж опор	F,I
K – защита старых проводов	F,I
L – протяжка новых проводов	J,K
M – монтаж арматуры	L
N – выверка провиса новых проводов	L
O – подстрижка деревьев	D
P – обесточивание и переключение линий	B,M,N,O	0,1
Q – включение и фазировка новой линии	P	0,5
R – уборка строительного мусора	Q
S – снятие старых проводов	Q
T – демонтаж старых опор	S
U – доставка неиспользованных материалов на склад	I

Задача №7.5

Найдите нарушения правил построения сетевых графиков в сетевой модели на рис.7.7.

Рис.7.7. Сетевая модель задачи №7.5

Задача №7.6*

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

Таблица 7.5

Исходные данные задачи №7.6

Название	Непосредственно предшествующие работы	Длительность, ед.времени
A	–
B	D
C	B, F, G
D	–
E	B, F, G
F	A, N
G	–
H	C, L
I	B, G
J	I,M
K	H,I,M
L	I,M
M	D
N	–

Рис.7.8. Сетевая модель задачи №7.6