Волкова Е.М., Карчик В.Г.. Производственный менеджмент

эффициенты затраты ресурсов на выпуск каждого изделия – aij. Производственная система заинтересована в максимизации прибыли, поэтому в качестве критерия оптимальности используется прибыль на одно изделие cj. В качестве неизвестных примем выпуск изделий xj.

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

3x1 + 4x2 + 3x3 + 1x4 = max F; 2x1 + 4x2 + 0x3 + 8x4 ≤ 12; 7x1 + 2x2 + 2x3 + 8x4 ≤ 8; 5x1 + 8x2 + 4x3 + 3x4 ≤ 48; x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0.

1. Построение канонической формы. Для каждого ограничения вводим хj ≥ 0 – дополнительную переменную. Поскольку у нас три ограничения, необходимо ввести три дополнительные переменные: х5, х6, х7. В результате имеем систему уравнений относительно ограничений и неравенств относительно переменных:

2х1 + 4X2 + 0х3 + 8х4 + 1х5 + 0х6 + 0х7 = 12; 7х1 + 2х2 + 2х3 + 8х4 + 0х5 + 1х6 + 0х7 = 8; 5х1 + 8х2 + 4х3 + 3х4 + 0х5 + 0х6 + 1х7 = 48;

х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0, х5 ≥ 0, х6 ≥ 0, х7 ≥ 0.

2. Строится базис допустимого плана относительно этих переменных. Для этого приравняем к нулю значения всех переменных относительно возможного выпуска изделий 1, 2, 3, 4-го вида, т. е. х1 = х2 = х3 = х4 = 0. Тогда имеем план выпуска изделий 5-го вида в количестве 12 машиночасов/1 ч на единицу = 12 единиц, соответственно изделий 6-го вида составит 8 единиц, 7-го вида – 48 единиц.

На основе базиса допустимого плана построим специальную форму для решения задачи симплекс-методом (табл. 4.4). Здесь в столбце ci приведены показатели целевой функции переменных, входящих в базис задачи: с5 = 0, с6 = 0, с7 = 0, в столбце pi – наименования самих показателей, х5, х6, х7. В столбце хi приведены значения показателей: х5 = 12, х6 = 8, х7 = 48. Первая строка таблицы содержит значения показателей cj. Вторая строка содержит наименования переменных канонической формы. Последняя, индексная, строка содержит данные коэффициентов, рассчитываемых в п. 3.

20

Остальные показатели на белом фоне представляют затраты машинного времени на выпуск единицы продукции.

3. Рассчитываются симплекс-множители (zj) и показатели индексной строки z j c j , где z j рассчитывается по формуле:

Рассмотрим табл. 4.4, полученную на шаге 2, и заполним последнюю строку (табл. 4.5). Начнем с клетки относительно переменной x1: z1 с5 a51

×48 = 0.

4.1.Выполняется проверка решения на оптимальность. Для задач на максимум целевой функции должно выполняться условие z j c j ≥ 0. В на-

шей таблице условие оптимальности не выполняется.

5.1. Выбор ключевого столбца. По данным индексной строки выбираем показатель z2 – c2 = –4 как имеющий наибольшее отклонение от условия оптимальности. Это ключевой столбец. Соответствующая переменная, х2, на следующей итерации войдет в базис задачи. Выберем ключевую строку из отношения: min{xi /a i2} = {12/4;8/2;48/8} = 12/4. Следовательно,

строка с переменной x5 является ключевой. Клетка на пересечении ключе-

21

вой строки (x5) и ключевого (х2) столбца называется ключевой. Ее значение равно 4.

6.1. Выполняются симплекс-преобразования по формулам (4.4) и (4.5). Начнем преобразование таблицы с клеток ключевой строки x5. Все ее элементы разделим на значение, равное 4, ключевой клетки. В связи с этим имеем: 12/4 = 3; 2/4 = 1/2; 4/4 = 1; 0/4 = 0; 8/4 = 2; 1/4 = 1/4 и т. д. Занесем

эти значения в клетки первой строки для переменной х2 табл. 4.6. Рассчитаем значения клеток для строки с переменной х6: 8 –12 2/4 = 2;

7 – 2 2/4 = 6; 2 – 4 2/4 = 0 (все элементы этого столбца оказываются равны-

ми нулю); 2 – 0 2/4 = 2 (все элементы ключевого столбца оказываются равными прежнему значению, кроме значения ключевой клетки, которая равна

единицу); 6 – 8 2/4 = 2; 0 – 1 2/4 = –1/2; 1 – 0 2/4 = 1 (все элементы этого столбца оказываются равными прежнему значению), и т. д.

Далее выполняются аналогичные расчеты для всех остальных клеток.

4.2. Выполняется проверка решения на оптимальность. В нашей таблице условие оптимальности для показателей индексной строки относительно переменных x3 и x1 не выполняется.

5.2. По данным индексной строки выбираем показатель z3 – c3 = –3, как имеющий наибольшее отклонение от условия оптимальности. Это ключевой столбец. Соответствующая переменная, х3, на следующей итерации войдет в базис задачи. Выберем ключевую строку: min{xi/ ai3} = = {2/2;24/4} = 2/2. Обратим внимание на то, что не рассматриваются коэффициенты меньшие или равные нулю. Итак, строка с переменной x6 явля-

ется ключевой. Клетка на пересечении ключевой строки и ключевого столбца будет на этот раз ключевой (2). Теперь необходимо ввести переменную х3 в базис задачи и вывести переменную x6.

6.2. Для ранее рассчитанной таблицы выполняются уже знакомые сим- плекс-преобразования относительно всех элементов. Получаем табл. 4.7.

22

4.3. Выполняется проверка решения на оптимальность.

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

Анализ оптимального плана решения задачи

1. Рассмотрим содержание оптимального плана. Как следует из него, необходимо выпускать изделия второго (х2) и третьего (х3) вида в количестве 3 и 1 единиц. Это обеспечивает массу прибыли в 15 у.е. Остальные изделия в оптимальный план не попали. Значения соответствующих переменных х1 = х4 = 0.

Вернемся к исходной модели:

2х1 + 4х2 + 0х3 + 8х4 ≤ 12; 7х1 + 2х2 + 2х3 + 8х4 ≤ 8; 5х1 + 8х2 + 4х3 + 3х4 ≤ 48; х1 ≥ 0, х2 ≥ 0, х3 ≥ 0, х4 ≥ 0.

Подставим значения неизвестных в оптимальном плане в систему не-

равенств модели. Имеем: 12 = 12; 8 = 8; 28 < 48; х1 = 0, х2 > 0, х3 > 0, х4 = 0.

Как видно из расчетов, первые два неравенства выполняются как равенства, т. е. ресурсы используются полностью, а третье неравенство выполняется как строгое – имеются излишние ресурсы в количестве: 48 – 28 = 20.

Этому соответствует значение дополнительной переменной х7 = 20. Если в базисе оптимального плана имеются дополнительные переменные со значениями более нуля, то они всегда указывают на соответствующий излишек ресурсов (машино-часов).

2. Рассмотрим показатели индексной строки относительно переменных х1, х2, х3, х4. Если переменная находится в базисе оптимального плана, то значение соответствующего коэффициента в индексной строке равно нулю, что мы и видим для переменных х2 и х3. Экономический смысл пока-

зателей индексной строки для переменных, не вошедших в оптимальный

23

план, выражается в потерях, которые может иметь производство, если захочет изготавливать соответствующие изделия. Иными словами, если производство первого изделия войдет в базисный (уже неоптимальный) план, то мы понесем убыток в 8 единиц прибыли: F = 15 – 8 = 7 у. е.

3. Коэффициенты в индексной строке для дополнительных переменных характеризуют эффективность используемых ресурсов и называются двойственными оценками ресурсов. Чем выше оценка, тем эффективнее используется ресурс. Двойственная оценка характеризует прирост прибыли на единицу прироста соответствующего ресурса. Например, ресур-

сы второго вида наиболее эффективны для производства. Каждая единица прироста этого ресурса обеспечивает увеличение целевой функции на 3/2 единицы. Если ресурсы второго вида увеличатся на две единицы, то значение F составит 15 + 2 3/2 = 18 у. е. Двойственная оценка недоиспользуемых ресурсов всегда равна нулю, что и видно для нашего третьего ресурса. Прирост ресурсов третьего вида привел бы к росту их недоиспользуемых остатков.

Библиографический список

1.Производственный менеджмент. Теория и практика : учебник для бакалавров / И. Н. Иванов, А. М. Беляев [и др.] ; под ред. И. Н. Иванова. –

М. : Юрайт, 2014. – 574 с.

2.Хейзер Дж. Операционный менеджмент / Дж. Хейзер, Б. Рендер ; пер. с англ. под ред. А. Чернова. – 10-е изд. – СПб. : Питер, 2015. – 1056 с.

3.Фатхутдинов Р. А. Организация производства : учебник / Р. А. Фатхутдинов. – М. : ИНФРА-М, 2011. – 544 с.

4.Попов А. М. Экономико-математические методы и модели : учебник для бакалавров / А. М. Попов, В. Н. Сотников ; под ред. А. М. Попова. – 2-е изд., испр. и доп. – М. : Юрайт, 2013. – 479 с.

5.Попов В. Л. Управление производством и операциями : учеб. пособие / В. Л. Попов, Д. А. Марков, Е. Г. Гуреева, А. В. Крутова ; под ред. проф. В. Л. Попова. – Пермь : Изд-во Перм. нац. исслед. политехн. ун-та, 2012. – 342 с.

24