В. А. Лелюк менеджмент операционных систем: анализ и развитие учебное пособие

Вид материала

Учебное пособие

Содержание Оптимизация плана методом 1. Определить план производства одного из двух видов продукции при ресурсных ограничениях и целевых функциях, приведенных в табл Таблица 3.1 – Исходные данные для планирования Таблица 3.2 – Варианты плана производства продукции Варианты плана 3.2. Метод выполнения Т2 (вариант 2), то ресурса 1 Т1 в количестве 11единиц, или продукцию Т2 Комбинированное планирование. Оптимальное планирование. 3.3. Анализ и выводы 3.4. Контрольные вопросы и тест

Подобный материал:

• Direct Memory Access dma. Драйверы литература, 56.37kb.
• Н. Ю. Каменская оценка, анализ иуправление рисками Учебное пособие, 1625.75kb.
• 1. Лекция: Введение, 344.47kb.
• 1. Лекция: Введение, 365.84kb.
• Курс лекций. Учебное пособие / В. Е. Карпов, К. А. Коньков, 68.87kb.
• Государственное образовательное учреждение высшего профессионального образования Волго-Вятская, 71.1kb.
• Что такое “Linux”. Возможности одной из самых динамично-развивающихся свободных операционных, 250.8kb.
• М. И. Ковальская Корпоративный менеджмент на железнодорожном транспорте Учебное пособие, 2787.11kb.
• Операционные системы и оболочки, 47.59kb.
• О. Ю. Якубовская 2011 г. Дисциплина: Операционные системы (2 часть из 2) Специальность:, 45.21kb.

Глава 3


^ ОПТИМИЗАЦИЯ ПЛАНА МЕТОДОМ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ


3.1. ЗАДАНИЕ, ЦЕЛЬ И ИСХОДНЫЕ УСЛОВИЯ

^ 1. Определить план производства одного из двух видов продукции при ресурсных ограничениях и целевых функциях, приведенных в табл. 3.1, 3.2. Рассчитать объем неиспользуемых при этом ресурсов. 2. Найти варианты планов, позволяющие увеличить количество выпускаемой продукции за счет производства двух ее видов. Для каждой целевой функции выбрать удовлетворяющий ее вариант плана. Результаты поиска и выбора вариантов записать в табл.3.3. 3. Найти и записать в табл.3.4 оптимальные, по приведенным целевым функциям, планы производства продукции с использованием линейных математических моделей ограничений, сформированных по исходным данным табл. 3.1.

Цель. Освоение студентом методологии оптимального операционного планирования с учетом ограничений по многим ресурсам с использованием математических методов.

Исходные условия. На рис.3.1 представлена схема процесса производства двух видов продукции Т1 и Т2.
Ресурс 1

Ресурс 2

Производство

продукции Т2

Продукция
Т1

Продукция
Т2
Для каждого вида продукции в табл. 3.1 заданы значения удельных расходов ресурсов, требуемых для производства единицы продукции.

Ресурс 1

Ресурс 2

Производство

продукции Т1

Производство

продукции Т2

Продукция
Т1

Продукция
Т2


Рис.3.1. Схема процесса производства продукции

^ Таблица 3.1 – Исходные данные для планирования

Наименование	Обозначение	Ресурс 1	Ресурс 2
Уд. расходы ресурсов по Т1, ед /ед.пр	а1j	10	4
Уд. расходы ресурсов по Т2, ед /ед.пр	a2j	5	8
Возможный объем поставки, ед.ресурс	Vj	110	80

^ Таблица 3.2 – Варианты плана производства продукции

Вариант плана	Max x x= x1 + x2	MaxП П = 2x1 + 3x2	MaxC C= 2x1 + 1,5x2	MinЗ З=1,8x1 + 2,2x2
Вариант 1 x1=? x2=0	x = x1
Вариант 2 x1=0 x2=?	x = x2
Выбранный план: xi =?	x = xi
Вариант 3 x1=? x2=?
Вариант 4 x1=? x2=?
Выбранный план: x1=? x2=?

Таблица 3.3 – Планирование с использованием линейного метода

^ Варианты плана	Максимум количества x = x1 + x2	Максимум прибыли П= 3x1 + 5x2	Минимум затрат З = 2x1+5x2	Минимум затрат З = 5x1+2x2
Вариант 1 x11= ? x21=?	x = x11 + x21
Вариант 2 x12 =? x22=?	x = x12 + x22
Вариант 3 x13 =? x23=?	x = x13 + x23
Оптимальный план: x1=? x2=?	x = x1 + x2

^ 3.2. МЕТОД ВЫПОЛНЕНИЯ


Альтернативное планирование. Цель пункта 1 задания состоит в том, чтобы студент понял, к какому результату при разных целевых функциях приводит выбор одного из двух альтернативных варианта плана:

Вариант 1. Выпускается только продукция вида Т1.

Вариант 2. Выпускается только продукция вида Т2.

Надо определить, какую продукцию – Т1 или Т2, и в каком количестве выгодно выпускать.

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

Из допустимых вариантов плана надо выбрать вариант по критерию оптимальности целевой функции, выражающей интересы предприятия и определяющей условие оптимальности плана. Выбранный вариант плана может называться оптимальным, если имеется математическое обоснование того, что он является наилучшим по заданному критерию оптимальности.
Для выполнения данного пункта задания используется эвристический метод. Глядя на таблицу, видно, что для реализации варианта 1 плана хватит заданного возможного объема ресурса 1 только на x₁ =110/10 = 11 изделий вида Т1, а ресурса 2 – только на x₁ = 80/4 = 20 изделий.

Очевидно, что допустимым планом производства продукции Т1, т.е. планом, удовлетворяющим ограничению по двум видам ресурса, является минимальная из двух величина. x₁ = 11, так как для большей величины (x₁ = 20) не хватит ресурса 1: его требуется 20×10 = 200, а имеется только 110.

Если же выпускать только продукцию ^ Т2 (вариант 2), то ресурса 1 может хватить для производства только x₂ = 110/5 = 22 изделий вида Т2, а ресурса 2 – только для x₂ = 80/8 = 10 изделий. Здесь результатом выбора плана по минимальной величине будет x₂ =10, так как для большей величины (x₂=22) не хватит ресурса 2: его требуется 22×8=176, а имеется только 80.

Таким образом, по п. 1 задания имеем ситуацию: или выпускать продукцию ^ Т1 в количестве 11единиц, или продукцию Т2 в количестве 10 единиц. Оптимальным по критерию MАХ x = x₁ + x₂ будет план x₁ = 11.

При этом потребность в ресурсе 2 будет 11×4 = 44. При возможной поставке в объеме 80 единиц неиспользованными окажутся 36 единиц ресурса 2.

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

Обобщив рассмотренный способ выполнения п.1 задания, получим следующий метод альтернативного планирования:

1. Найти при x₂ = 0 максимально возможное значение x₁₁^* = V₁ /a₁₁ при заданном объеме V₁ поставки ресурса 1, а затем - максимально возможное значение x₁₂^* = V₂ /a₁₂ при заданном объеме V₂ поставки ресурса 2.

2. Выбрать из найденных значений x₁₁^*, x₁₂^* минимальное значение:
x₁ = min {x₁₁^* , x₁₂^*} = min { V₁ /a₁₁ , V₂ /a₁₂ } = min { V_j /a_1j : jÎ{1,2}} , (3.1)

где j – вид ресурса, V_J – возможный объемы поставок ресурсов 1,2, a_1j – удельные расходы ресурса на единицу продукции Т1.

3. Найти при x₁ = 0 максимально возможное значение x₂₁^* = V₁ /a₂₁ при заданном объеме поставки ресурса 1, а затем - максимально возможное значение x₂₂^* = V₂ /a₂₂ при заданном объеме поставки ресурса 2.

4. Выбрать из найденных значений x₂₁^*, x₂₂^* минимальное значение:
x₂ = min {x₂₁^* , x₂₂^*}= min { V₁ /a₂₁ , V₂ /a₂₂ } = min { V_j /a_2j : jÎ{1,2}} . (3.2)

Предыдущие действия можно записать кратко так:

Найти значения x_i = min { V_j /a_ij : i, jÎ{1,2}}, (3.3)

где i – вид продукции.

Далее из значений x_i надо выбрать значение, удовлетворяющее заданному критерию оптимальности. Для критерия max x = x₁ + x₂ правило выбора для данного случая можно записать так:
x = max{ x₁, x₂ }= max{ x_i }= max{ min { V_j /a_ij : i, jÎ{1,2}}}. (3.4)

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

^ Комбинированное планирование. При выполнении 2-го пункта задания тоже используется эвристический метод. Студент должен найти два более рациональных варианта плана, при которых обеспечивается больший суммарный объем производства, чем в п.1, за счет производства двух видов продукции. Иными словами, надо уйти от альтернативных вариантов и определить комбинации объемов выпуска по видам продукции.

Таким вариантом может быть, например: x₁ = 10, x₂ =2. В этом случае целевая функция max x = x₁ + x₂ будет иметь значение x = x₁ + x₂ = 10+2=12. Проверим, допустимый ли этот план. Потребность в ресурсе 1 здесь для продукции Т1: 10×10=100, для продукции Т2: 5×2=10. Итого 100+10=110, что приемлемо. Потребность в ресурсе 2: 10×4+ 2×8 =56. Остается неиспользованный объем 80-56=24ед. С точки зрения критерия оптимальности max x = x₁ + x₂ этот вариант лучше предыдущего.

При варианте x₁ = 9 получим потребность для него в ресурсе 1: 9×10=90. Остаток ресурса 1: 110-90=20. Его хватит для производства 20/5=4 продукции Т2. Потребность в ресурсе 2: 9×4+4×8=68 ед. Остается излишек 16 ед. Целевая функция x = x₁ + x₂ имеет значение 9+4=13.

Теперь для этих вариантов надо рассчитать значения других целевых функций и выбрать итоговое решение по плану для вариантов 1-4. При этом возникают вопросы: - Нет ли лучших вариантов? - Как формировать варианты? - Как из них выбирать наилучший?

Рассмотрим решение этих вопросов с помощью оптимальных математических методов.

^ Оптимальное планирование. Для оптимизации плана необходимо:

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

- найти особые допустимые варианты плана;

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

Математическая постановка задачи включает в себя ограничения и целевую функцию. Как видно из табл. 3.1, в данной задаче ограничена возможная поставка ресурсов для производства продукции, что может быть записано следующим образом:

1) 10x₁ + 5x₂ ≤ 110,
2) 4x₁ + 8x₂ ≤ 80. (3.5)
Обобщенная математическая запись ограничений для двух видов продукции и двух видов ресурсов будет иметь следующий вид:

a₁₁ x₁ + a₂₁ x₂ ≤ V₁ (1-е ограничение),

a₁₂ x₁ + a₂₂ x₂ ≤ V₂ (2-е ограничение). (3.6)

Кроме этого, для математической полноты надо записать такое очевидное требование к плану:

x₁ , x₂ ≥ 0 (3-е ограничение). (3.7)

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

Модель и решение задачи хорошо иллюстрирует их графическая интерпретация, представленная на рис. 3.2. Здесь область всех допустимых вариантов решений ограничена четырехугольником АВС0. Особыми допустимыми вариантами плана являются приведенные на рисунке координаты точек А, В, С. Эти варианты нужно записать в 1-ю графу табл.3.3.

Находящееся среди них оптимальное решение можно найти, определив для каждого варианта значение целевой функции и выбрав в качестве плана то значение, которое удовлетворяет критерию оптимальности. Для критерия max x = x₁ + x₂ оптимальным вариантом плана будет x₁=8, x₂=6 (точка В на графике), так как он обеспечивает наибольший выпуск продукции по сравнению с вариантами, соответствующими точкам А, С.



x₁

x₂

0

20

11

10

22

8

6

А(x₁=11, x₂=0)

С(x₁=0, x₂=10)

В(x₁=8, x₂=6)

Рис. 3.2. Геометрическая интерпретация модели задачи


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

Реальные задачи планирования на уровнях предприятий и отраслей оперируют десятками, сотнями и тысячами переменных. Именно для решения таких задач применение линейного программирования дало наибольший эффект. Признанием этого факта явилось присуждение в 1975 г. Нобелевской премии Л. В. Канторовичу, разработавшему в СССР в 1939 г. теорию решения подобных задач для планирования работ на картонажной фабрике, и зарубежному ученому Дж. Данцигу, который сформулировал в 1947 г. симплекс-метод линейного программирования.

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

Она формулируется так [18]. Имеется m предприятий, производящих некоторый продукт, который доставляется на n складов. Объем производства предприятия в единицу времени равен v_i (i = 1,…,m), a объем потребности на складе равен w_j (j = 1,…,n). Стоимость перевозки единицы продукта с предприятия i на склад j равна с_ij и не зависит от объема перевозки.

Обычно предполагается, что весь продукт вывозится, и все требования удовлетворяются.

Надо найти количество продукта x_ij , которое надо перевозить с предприятия i на склад j, при котором обеспечивается

Min ΣΣ с_ij x_ij (3.8)


при условиях 1) Σx_ij = v_i , 2) Σx_ij = w_j , 3) x_ij ≥ 0. (3.9)

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

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


^ 3.3. АНАЛИЗ И ВЫВОДЫ


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

2. Решение, основанное на, так называемом, здравом смысле («потратить ограниченные ресурсы на производство только той продукции, которая выгодна»), оказывается менее рациональным в данных условиях, чем решение выпускать комбинацию разных видов продукции. Во-первых, оно хуже относительно целевой функции, а, во-вторых, в результате реализации такого решения остается неиспользованной часть объемов ресурсов;
3. Решение не может быть оптимальным абсолютно, т.е. без всяких условий. Оно всегда привязано к целевой функции, определяющей правило, каким должно быть наилучшее решение. Выполнив задание, студент должен убедиться, что оптимальное решение по одной целевой функции, не является оптимальным по другой целевой функции, т.е. разные целевые функции могут давать разные результаты. При этом надо помнить, что слово оптимальное является синонимом слова наилучшее. Поэтому неграмотно говорить слова «самое оптимальное», подразумевая, что это самое лучшее. Оптимальное решение не просто лучшее, а самое лучшее по заданному критерию.

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

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

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

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

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

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


^ 3.4. КОНТРОЛЬНЫЕ ВОПРОСЫ И ТЕСТ



1. Какое назначение целевой функции?
2. Что дает использование математических теорий, моделей и методов решения задач планирования при ограниченных ресурсах?
3. В чем состоит особенность линейных моделей задач?
4. Каковы отличия всевозможных, допустимых и оптимальных вариантов операционной системы при заданном критерии оптимальности и ограничениях?
5. Что дает выделение особых точек в области допустимых вариантов решений?
6. В чем состоит ограниченность математических методов решения задач и, в частности, методов линейного программирования?
7. Какие имеются разновидности и взаимоотношения критериев оптимальности, как они взаимосвязаны с ограничениями и как они вместе с ограничениями влияют на выбор решений?


ТЕСТ


Т4.1. Что является общим у математических и эвристических методов?

1. Применение математической теории. 2. Учет ограничений по многим ресурсам.

3.Поиск оптимальной очередности заказов. 4. Возможность улучшения качества процесса.


Т4.2. Целевая функция в задаче оптимизации процесса предназначена для расчета:

1. Результатов решения задачи. 2. Оценочного показателя качества процесса.

3. Ограничений по ресурсам. 4. Потребности в ресурсе.

Т4.3. Целью применения математических методов в менеджменте не является:

1. Сертификация продукции. 2. Гарантия оптимальности полученного решения.

3. Ускорение процесса решения задачи. 4. Использование готовых программ.


Т4.4. Допустимые варианты плана удовлетворяют:

1. Требованиям целевой функции. 2. Требованиям качества продукции.

3. Требованиям ограничений. 4. Потребности в ресурсах.


Т4.5. Оптимальный план при ограниченных ресурсах удовлетворяет:

1. Только ограничениям. 2. Только целевой функции.

3. Потребности в ресурсах. 4. Ограничениям и целевой функции.


Т4.6. Что не препятствует применению метода линейного программирования?

1. Несоответствие критерия оптимальности реальным интересам предприятия.

2. Нелинейность ограничений и/или целевой функции. 3. Необходимость выбора
очередности выполнения заказов. 4.Наличие ограничений ресурсов.