Менеджмент: конспект лекций

Простой перебор . Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2 Х 1 + 5 Х 2 ≤ 10, то, очевидно, 0 ≤ Х 1 ≤ 10/2 = 5 и 0 ≤ Х 2 ≤ 10/5 = 2. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его «обращенную» к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед (подробнее см. Шевчук Д.А. Управление качеством. – М.: ГроссМедиа: РОСБУХ, 2008).

Проведем перебор точек параллелепипеда с шагом 1/10 n последовательно при n =2,3,…, вычисляя значения целевой функции и проверяя выполнение ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10 n .)

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно – с помощью т. н. метода случайного поиска) менять ее координаты на определенную величину ∆, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения—неравенства переходят в равенства)… Остановка – в вершине линейного многогранника. Решение найдено (Более строго выражаясь, найдено с точностью до ∆. Если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ∆/2, ∆/4 и т. д.).

Симплекс—метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в то время как методы простого и направленного перебора могут быть применены для решения практически любой задачи оптимизации. Симплекс—метод был предложен американцем Г. Данцигом в 1951 г. Основная его идея состоит в продвижении по выпуклому многограннику ограничений от вершины к вершине, при котором на каждом шаге значение целевой функции улучшается до тех пор, пока не будет достигнут оптимум. Разберем пример на основе данных табл.2.

Рассмотрим задачу линейного программирования, сформулированную выше при рассмотрении оптимизации номенклатуры и объемов выпуска:

F = 15 Х 1 + 12 Х 2 + 14 Х 3 → max.

Х 1 / 200 + Х 2 / 300 + Х

3 / 120 ≤ 100,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 ≤ 100,

Х 3 / 80 ≤ 100.

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

В соответствии с симплекс—методом введем т. н. «свободные переменные» Х 4, Х 5, Х 6, соответствующие недоиспользованным мощностям, т. е. от системы неравенств перейдем к системе уравнений:

Х 1 / 200 + Х 2 / 300 + Х 3 / 120 + Х 4 = 100,

Х 1 / 300 + Х 2 / 100 + Х 3 / 100 + Х 5 = 100,

Х 3 / 80 + Х

6 = 100,

15 Х 1 + 12 Х 2 + 14 Х 3 = F .

У этой системы имеется очевидное решение, соответствующее одной из вершин многогранника допустимых значений переменных:

Х 1 = Х 2 = Х 3 = 0, Х 4 = Х 5 = Х 6 = 100, F = 0.

В терминах исходной задачи это означает, что ничего не надо выпускать. Такое решение приемлемо только на период летних отпусков.

В соответствии с симплекс—методом выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х 1.

Сравниваем частные от деления свободных членов в первых трех уравнениях на коэффициенты при только что выбранной переменной Х 1:

100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ∞.

Выбираем строку из системы уравнений, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере – это первая строка, которой соответствует отношение 20000.

Умножим первую строку на 200, чтобы получить Х 1 с единичным коэффициентом:

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000.

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, чтобы исключить член с Х 1, получим

7/900 Х 2 + 4/900 Х 3 – 2/3 Х 4 + Х 5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F , получим:

2 Х 2 – 11 Х 3 – 3000 Х 4 = F – 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х 1 входит только в первое уравнение:

Х 1 + 2/3 Х 2 + 2/1,2 Х

3 + 200 Х 4 = 20000,

7/900 Х 2 + 4/900 Х 3 – 2/3 Х 4 + Х 5 = 100/3,

Х 3 / 80 + Х 6 = 100,

2 Х 2 – 11 Х 3 – 3000 Х 4 = F – 300000.

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее другой вершине выпуклого многогранника в шестимерном пространстве:

Х 1 = 20000, Х 2 = Х 3 = Х 4 = 0, Х 5 = 100/3, Х 6 = 100, F = 300000.

В терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.