Файл: Теория систем2.pdf

47

Каждая отливка для детали А стоит 2 $, для детали В – 3$. Продажная цена деталей равна соответственно 5 и 6 $. Стоимость часа станочного времени составляет по трем типам используемых станков 20, 14 и 17,5 $ соответственно. Предполагая, что можно выпускать для продажи любую комбинацию деталей A и B, нужно найти план выпуска продукции, максимизирующий прибыль.

Рассчитаем прибыль на одну деталь.

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

Z=1,2 x + 1,4 y.

Так как отрицательные значения х и у не имеют смысла, должно удовлетворяться ограничение x ≥ 0, y ≥ 0.

Величины x и y нельзя выбирать произвольно, так как необходимо учесть ограничения по мощности оборудования. Следовательно, должны выполняться неравенства:

49

Основной результат теории, позволяющий решить эту задачу, заключается в утверждении, что эта точка (x,y), в которой прибыль достигает максимума, должна находиться в одной из вершин многоугольника ОАВС.

Видно, что максимум прибыли достигается в точке В. Таким образом, наилучший производственный план заключается в том, чтобы выпускать 16, 93 детали А в час и 12, 9 детали в час. (Эти величины надо рассматривать как средние нормы выпуска).

2.4.2. Симплексный метод

Гораздо проще иметь дело с равенствами, чем с неравенствами. Поэтому ограничения преобразуют в уравнения путем введения свободных переменных u, v, w. Эти переменные представляют собой разность между левой и правой частями неравенств. Тогда получим:

40x + 25y + u =1000 ,

35x + 28y + v = 980 ,

25x + 35y + w = 875 ,

u, v,w ≥ 0 .

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

50

отличны от нуля, а n равны нулю, называется допустимым решением

(опорным планом).

На практике расчеты производят в табличной форме. Составим таблицу, в которых строки, обозначенные P3, P4, P5 соответствуют первому набору значений ненулевых переменных u, v, w. Столбцы, обозначенные P1, P2, P3, P4, P5 соответствуют переменным x, y, u, v, w. Добавляем еще один столбец P0, соответствующий правым частям уравнений, и строку , в которой проставлены коэффициенты функции Z.

Пустые клетки соответствуют нулям. Воспользуемся следующим алгоритмом.

Шаг 1. Выбрать столбец с наибольшим положительным элементом в строке . Это столбец P2 c элементом 1,4.

Шаг 2. Разделить элементы столбца P0 на соответствующие положительные элементы столбца, выбранного на шаге 1 и выбрать наименьший результат. (В нашем примере элементы столбца P0 делим на соответствующие элементы столбца P2). Тогда для каждой строки таблицы получаем:

Наименьший результат соответствует строке P5. Поэтому на втором шаге выбирается строка P5.

51

Определение. Элемент, стоящий на пересечении столбца, выбранного на шаге 1 и строки, выбранной на шаге 2, называется направляющим элементом.

Шаг 3. Разделить строку, выбранную на шаге 2 на направляющий элемент. Результат обозначить символом столбца. (В нашем случае элементы строки P5 делятся на 35 и результат получает обозначение

P2).

Новая строка P2 будет выглядеть так:

найдено. В противном случае нужно вернуться к шагу 1.

(В нашем примере строка P2 умножается на 25 и результат вычитается из строки P3, затем P2 умножаем на 28 и вычитаем из P4, и P2 умножаем на 1,4 и вычитаем из ).

вернуться к шагу 1.