Этапами разработки сетевого графика являются:
- сбор технической и технологической информации;
- составление таблицы работ и ресурсов в технологической последовательности, в которой указывается характеристика и объем работ, время, потребные ресурсы, порядок проведения (очередность);
- составление сетевого графика;
- определение критерия оптимизации (по экономии материальных, трудовых ресурсов, срокам, минимальной стоимости и т.п.);
- определение оптимального пути решения[1, c.85].
3.2. Методы линейного и динамического программирования
Линейное программирование объединяет методы решения задач, которые описываются линейными уравнениями. Данный метод основан на решении системы линейных уравнений, когда зависимость между изучаемыми явлениями строго функциональна. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий. Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу – значит выбрать из всех допустимых вариантов лучший, оптимальный.
Для решения задач линейного программирования могут быть использованы средства, включенные в состав электронных таблиц для персональных компьютеров. Из числа таких средств наиболее распространены таблицы программ MS Excel.
Постановка задачи линейного программирования состоит в формулировке целевой функции и ограничений – уравнений или неравенств.
Пример. Фирма производит продукцию двух видов – Х и У. Имеются следующие данные о производстве продукции:
Цех | Продукция | Максимально возможная загрузка в неделю, час | |
Х | У | ||
Сборочный | 2 шт/час | 4 шт/час | 100 |
Отделочный | 3 шт/час | 2 шт/час | 90 |
Прибыль | 25 тыс.р./шт | 40 тыс.р./шт | Максимум |
Целевой функцией в данном случае является прибыль, которую необходимо максимизировать:
ВП = 25 * Х + 40 * У.
Имеются ограничения по производительности сборочного и отделочного цехов:
2 * Х + 4 * У меньше или равно 100;
3 * Х + 2 * У меньше или равно 90,
а также требование неотрицательности элементов – Х, У больше 0.
Решается методом итераций (подбора значений). После каждого шага проверяется соблюдение ограничений. В результате получаем решение Х=20, У = 15. Максимальная прибыль составит 1100 тыс.р. при полной загрузке обоих цехов.
В задачах линейного программирования может представлять интерес вопрос, имеет ли смысл увеличивать объем доступного ресурса. Например, какова цена увеличения рабочего времени в сборочном цехе на один час в неделю. Эта цена – добавочная валовая прибыль, которая может быть получена, называется двойственной оценкой данного ресурса. Двойственную оценку можно рассматривать как упущенную выгоду или как прибыль, недополученную в результате нехватки ресурса. Если в приведенном примере рабочую неделю в сборочном цехе увеличить на восемь часов, то новое оптимальное решение будет выглядеть следующим образом:
Х = 18;
У = 18.
Валовая прибыль при этом составит 1170 тыс.р.
Решение задач линейного программирования может проводиться графическим методом. Для этого найдем в плоскости координат область, соответствующую всем ограничениям.
Первые два ограничения можно представить в виде:
У ≤ 25 – 0,5 * Х;
У ≤ 45 – 1,5 * Х.
Двум оставшимся ограничениям соответствуют сами оси Х и У.
На рисунке линия номер один соответствует первому ограничению, линия номер два соответствует второму ограничению. Очевидно, что допустимая область решений находится в зоне, ограниченной пересечением двух прямых и осей координат.
Какая же точка этой области соответствует оптимальному решению? Целевая функция описывается выражением ВП = 25 * Х + 40 * У или У = ВП – 0,625 * Х .
Переменная ВП должна быть максимальна. График этой функции можно представить несколькими линиями при разных значениях ВП. На рисунке представлены три штриховые линии, соответствующие ВП = 5, 10, 15.
2
25 15 10 1 5 8 16 24 30 50Рис. 3.1. Решение задачи линейного программирования
Нетрудно заметить, что чем дальше от центра координат находится прямая, тем больше значение ВП. Это означает, что функция 25 * Х + 40 * У примет максимально значение в точке пересечении прямых 1 и 2. Координаты этой точки можно найти, решив систему линейных уравнений:
У = 25 – 0,5 * Х У = 15;У = 45 – 1,5 * Х Х = 20.
Методы динамического программирования применяются при решении задач оптимизации, которая описывается нелинейными функциями. Типичным примером является разновидность транспортной задачи, когда необходимо загрузить транспортное средство различными видами товаров, которые к тому же имеют различный вес, таким образом, чтобы стоимость груза являлась максимальной. Если обозначить:
в – масса одного предмета каждого вида;
с – стоимость предмета каждого вида;
к – количество предметов каждого вида ,
тогда задача может быть описана уравнением
S к * с = макс при ограничении S к * в < В,
сумма от 1 до Н при этом Н – ассортимент загружаемой продукции. Задача решается в Н этапов, причем на первом этапе определяется максимальная стоимость груза из продукции первого типа, затем – первого и второго типов и так далее.
3.3. Математическая теория игр
Теории игр – это теория математических моделей принятия решений в условиях конфликта или неопределенности. Другими словами, теория игр исследует оптимальные стратегии в ситуациях игрового характера, когда результат деятельности нашего предприятия зависит от стратегии другого «игрока», намерения которого нам неизвестны.
Это ситуации, связанные с решением производственных задач, выбор оптимальных объемов, качества и ассортимента продукции в изменяющихся внешних условиях, либо при изменении какого-либо внутреннего фактора. Кроме того, теория игр может быть применена при расчетах оптимального количества запасов ТМЦ на предприятии. Теория игр позволяет двум противоборствующим игрокам (предприятие и поставщики, предприятие и погода) выбрать стратегию, которая была бы выгодна обеим. В качестве примера можно рассмотреть следующую ситуацию:
Фирма выпускает два вида продукции (П1 и П2). В зависимости от поведения конкурента она может продать различное количество продукции, а именно:
- если конкуренты будут ориентированы на продукцию П1, наша фирма сможет продать 500 единиц продукции П1 и 1000 единиц продукции П2;
- если конкуренты будут ориентированы на продукцию П2, наша фирма сможет продать 900 единиц продукции П1 и 600 единиц продукции П2.
Себестоимость производства единицы продукции П1 – 8 р., цена 10 р. Себестоимость производства единицы продукции П2 6 р., цена 11 р. Рассмотрим вероятный результат при изменении поведения конкурента. Обозначим стратегии: ориентация на продукцию П1 – «А» для нашего предприятия и «Б» для конкурента, ориентация на продукцию П2 – «В» для нашего предприятия и «Г» для конкурента. Если мы выбираем разные стратегии, то наше предприятие сможет продать всю произведенную продукцию:
Прибыль (стратегии А - Г) = 500 * (10-8) + 1000 * (11-6) = 6000 р.
Прибыль (стратегия В - Б) = 900 * (10-8) + 600 * (11-6) = 4800 р.
В случае совпадения наших интересов, мы сможем продать только часть продукции, а часть останется нереализованной, хотя издержки на ее производство наше предприятие понесет:
Прибыль (стратегии А-Б) = 500 * (10-8) + 600 * (11 – 6) – (900-500) * 8 = 800 р.
Прибыль (стратегии В-Г) = 500 * (10-8) + 600 * (11 –6) – (1000-600) * 6 =1600 р.
Таким образом, при совпадении стратегий наше предприятие получит меньше прибыли. Предугадать поведение конкурента сложно. Нужно применять смешанную стратегию. Обозначим частоту применения стратегии «А» за Х. Значит, частота применения стратегии «В» – (1-Х). Приравняем вероятные суммы прибыли, которую получит наше предприятие в том ли ином случае:
6000 * Х + 1600 * (1-Х) = 800 * Х + 4800 * (1-Х).стратегия конкурента - Г стратегия конкурента – Б
Решаем данное уравнение:
6000*Х – 1600 *Х - 800*Х + 4800*Х = 4800 – 1600,
8400 *Х = 3200,
Х = 3200 / 8400 = 0,38,
(1-Х) = 0,62.
Рассчитываем ассортимент продукции:
0,38 * (900 П1 + 600 П2) + 0,62* (500 П1 + 1000 П2) = 342 П1 + 228 П2 + 310 П1 + 620 П2 = 652 П1 + 848 П2.
Выпуская такой ассортимент продукции, мы получим одинаковую прибыль при любом поведении конкурента. При этом прибыль будет меньше максимальной, но больше минимальной.
3.4. Теория массового обслуживания
Называется также теорией очередей и используется для решения задач оптимизации обслуживания. Рассматривает вероятные модели реальных систем обслуживания. Она используется для минимизации издержек в сфере обслуживания, в производстве, в торговле.