Симплекс-метод. Определение оптимальной производственной программы предприятия

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

В результате симплексных преобразований получают симплексную таблицу, в которой:

• 1) если в строке целевой функции F имеется хотя бы один отрицательный коэффициент и в столбце, соответствующем этому коэффициенту, имеется хотя бы один положительный коэффициент, то решение может быть улучшено;
• 2) если в строке целевой функции F имеется хотя бы один отрицатель ный коэффициент, но в столбце, соответствующем этому коэффициенту, нет положительных коэффициентов, то задача не имеет решения;
• 3) если в строке целевой функции F нет ни одного отрицательного коэффициента, то получено оптимальное решение задачи.

Это правило применяется при решении задач на максимум.

При решении задач симплекс-методом исходным моментом является определение начального допустимого базисного решения (начального опорного плана). Все задачи, решаемые симплекс-методом, по способу нахождения начального опорного плана можно отнести к трем группам:

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

Рассмотрим решение задачи из каждой группы.

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

Таблица 1.6

Требуется найти такую программу производства, при которой достигается максимум прибыли от реализации продукции.

Решение

Пусть Xj - количество выпускаемой продукции і-го вида, тогда система неравенства, отражающих ограничения на имеющийся объем ресурсов по каждому виду, будет следующей

5х J + 7х ₂ + 4х ₃ <24;

lOXj +5х₂ +20х₃ <80;

• 5xj +2х₂ + х₃ <10;
• 2xj +х₂ +х₃ <6.

Общая прибыль составит

F = 18xj +12х₂ +8х₃ —>шах.

Переменные х | не могут быть меньше нуля, так как выпуск продукции не может быть отрицательным

Xj>0 (І = ЇЗ).

Прежде чем решить задачу симплекс-методом, необходимо математическую постановку данной задачи привести к общей постановке задачи линейного программирования (канонической форме), т.е. от ограничений-неравенств перейти к ограничениям-равенствам. Для этого в каждое из неравенств ВВОДИТСЯ ПО ОДНОЙ дополнительной переменной: WpW₂,W₃,W₄. В результате получаем

• 5xj +7х₂ +4х₃ 4-Wj =24;
• 10х J +5х₂ +20х₃ +w₂ =80;
• 5xj +2х₂ +х₃ +w₃ =10;
• 2xj +х₂ +х₃ +w₄ =6.

С экономической точки зрения дополнительные переменные Wj характеризуют объем неиспользуемого в плане ресурса і-го вида.

Для построения первой симплекс-таблицы необходимо определить начальное допустимое базисное решение. Данная задача относятся к задачам линейного программирования с явно выраженным начальным опорным планом. В качестве начальной выбирается ситуацию, когда предприятие ничего не выпускает, т.е. х^ =0, х₂ =0, х₃ =0. Эти значения переменных можно принять за начальное допустимое базисное решение. При этом все имеющиеся ресурсы не расходуются, т.е. w₁=24,w₂=80,w₃=10,w₄=6. Переменные ХрХ₂, х₃ называются свободными, a w_1?w₂,w₃,w₄ - базисными. При решении задачи линейного программирования симплекс-методом свободные переменные всегда равны нули, а базисные переменные - больше нуля (в некоторых случаях базисная переменная может принимать нулевое значение, тогда такой базис называется вырожденным).

Для заполнения первой симплекс-таблицы необходимо представить математическую постановку задачи линейного программирования (ограничения-равенства и целевую функцию F) в удобном для этого виде

Wj =24-(5х₁ +7х₂ +4х₃); w₂ = 80 — (10х j +5х₂ +20х₃ ); w₃ =10-(5xj +2х₂ + х₃); ^w4 =6-(2Х| +х₂ +х₃);

F = 0-(-18X| -12х₂ -8х₃)—>шах.

Первая симплекс-таблица имеет вид, представленный в табл. 1.7.

Таблица 1.7

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

Для получения новой симплекс-таблицы необходимо воспользоваться следующим алгоритмом:

• 1. Выбирается генеральный столбец, т.е. столбец с наибольшим по модулю отрицательным коэффициентом в строке F.
• 2. В генеральном столбце определяется генеральный коэффициент по минимуму отношения где а_і0 - і-й коэффициент в столбце "Свободный член";

а- - і-й коэффициент в генеральном столбце.

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

Используя вышеприведенный алгоритм, устанавливается, что генеральным будет столбец, соответствующий свободной переменной X j , а генеральный коэффициент находится в строке, соответствующей базисной переменной W₃, т.е. і = 3, j = 2. Поменяв местами переменные и w, (базисная переменная w ₃ становится свободной, а свободная переменная х - базисной) по рассмотренному выше алгоритму, выстраивается вторая симплекс-таблица (табл. 1.8).

Таблица 1.8

Анализируя полученные значения коэффициентов при свободных переменных в строке целевой функции F, устанавливаем, что данное решение еще не является оптимальным, так как есть отрицательные значения коэффициентов (-24//, следовательно, необходимо продолжить решение задачи. Повторив указанные выше действия, выстраивается третья симплекс-таблица (табл. 1.9)

Таблица 1.9

Далее строится четвертая симплекс-таблица (табл. 1.10).

Таблица 1.10

Все значения коэффициентов при свободных переменных в строке целевой функции F неотрицательны, следовательно, получено оптимальное базисное решение (план)

Х| =1, Х2 =1, х^ =3, W] =0, W2 =5, Wj =0, =0, F = 54.

Таким образом, при выпуске предприятием продукции вида А в объеме 1 ед., вида В - 1 ед., вида С - 3 ед. максимальная прибыль составит 54 тыс.руб. При этом материалы, оборудование I и II групп используется полностью, а рабочая сила на 5 человек недоиспользуется.

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

Таблица 1.11

зо

Требуется организовать такую программу производства, при которой достигается максимум прибыли от реализации продукции, причем изделий вида А необходимо изготовить не менее 30 шт., вида В - не более 30 шт., вида С - ровно 10 шт., видов Е и F - в комплектности 1:3 и вида G - не менее 10 шт. и не более 50 шт.

Решение

Решение задачи начинается с математической постановки задачи. Все условия (ограничения) данной задачи можно разделить на две группы:

• 1) ограничения по ресурсу
• 2xj + 2х ₂ + х₃ +4х₄+2х₅+х₆ + Зх_? < 1100;
• 4xj + х₂ + 6х₃ + 2х₄ + х₅ + 2х₆ + 2х₇ < 1800;

Зх₂ + 8х₃ + х₄ + Зх₅ + х₆ + 2х₇ < 1500,

где Х| - количество выпускаемой продукции і-го вида, Xj > 0 (і = 1,7).

2) ограничения по ассортименту

х J > 30 (ограничение снизу);

х₂<30 (ограничение сверху);

х₃ = 10 (жесткое ограничение);

х₅ : х₆ =1:3 (условие комплектности);

10 < х₇ <50 (двустороннее ограничение).

Целевая функция для данной задачи имеет вид

F = 4xj +6х₂ +7х₃ +5х₄ +4х₅ +2х₆ +8х₇ —>шах.

Одно из ограничений по ассортименту является жестким. Это позволяет исключить из дальнейшего рассмотрения изделия вида С (т.е. условие выполняется, изделий вида С выпущено ровно 10 шт.), что повлечет за собой корректировку фонда времени работы оборудования. Математическая постановка задачи примет следующий вид:

• - ограничения по ресурсу
• 2xj + 2х₂ + 4х₄ + 2х₅ + х₆ + Зх₇ < 1090;
• 4xj + х₂ + 2х₄ + х₅ + 2х₆ + 2х₇ < 1740;

Зх₂ + х₄ + Зх₅ + х₆ + 2х₇ < 1420;

- ограничение по ассортименту

х, >30, х₇ <30, х^=10, х₄-:х_А=1:3, 10<х₇<50;

• 1 ’ 2 ’ э ⁷ э о ’ / ’
• - целевая функция

F = 70 + 4xj +6х₂ +5х₄ +4х₅ +2х₆ +8х₇ —>тах.

Данная задача не имеет явно выраженного начального допустимого базисного решения. Действительно, если осуществить переход от ограничений-неравенств к ограничениям-равенствам путем введения дополнительных переменных Wj и принять неизвестные Xj в качестве свободных переменных, т.е. равными нулю, то некоторые базисные переменные Wj будут отрицательными, что невозможно (все переменные должны быть неотрицательными). Данная ситуация наблюдается во всех неравенствах вида «>». В рассматриваемой задаче таких неравенств два

Xj >30 и х₇ >10.

Для нахождения начального допустимого базисного решения таких задач можно использовать простые алгебраические преобразования. Метод простых алгебраических преобразований для нахождения начального опорного плана используется в задачах, содержащих неравенства вида «>», которые связывают только одну переменную Xj. В рассматриваемой задаче это условие соблюдается.

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

Xj >30, Xj-30>0, х₁-30 = у₁ => У} >0, X] =y_t +30;

х₂<30, *₂=У₂ => У2-ЗО;

х₄=у₄;

^х5^:х6^=1:3’ ^х5=?5 => ^Х6⁼³У5-

10<х₇<50, 0<х₇-10<40, х₇-10 = у₇ => у₇ <40, х₇=у₇+10.

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

• - ограничения по ресурсу
• 2у₁ + 2у₂ + 4у₄ + 5у₅ + Зу₇ < 1000;
• 4_У1 + у₂ + 2у₄ + 7у₅ + 2у₇ < 1600;
• 3У₂ + У4 ^{+ 6}У5 ^{+ 2}У? - ^1400;
• - ограничения по ассортименту

у₂<30;

У₇<40;

_Уі>0 (і = 1, 2, 4,5,7);

- целевая функция

F = 270 + 4y₁ +6у₂ +5у₄ + 10у₅ + 8у₇ -^-тах.

Путем введения дополнительных переменных WpW₂,w₃,w₄,w₅ осуществляется переход от ограничений-неравенств к ограничениям-равенствам

• 2yj + 2у₂ + 4у₄ + 5у₅ + Зу₇ + Wj = 1000;
• 4у J + у₂ + 2у₄ + 7у₅ + 2у₇ + w₂ = 1600;

Зу₂ + у₄ + 6у₅ + 2у ₇ + w₃ = 1400;

У 2 +^w₄ = 3°;

у₇ + w₅ =40.

Начальное допустимое базисное решение будет иметь вид

У1 =0, у₂ =0, у₄ =0, у₅ =0, у₇ =0 (свободные переменные);

W| =1000, w₂ =1600, w₃ =1400, w₄ =30, =40 (базисные переменные).

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

Wj = 1000 - (2yj + 2у₂ + 4у₄ + 5у₅ + Зу₇);

w₂ = 1600 - (4у₁ + у₂ + 2у₄ + 7у₅ + 2у₇);

w₃ = 1400 - (Зу₂ + у₄ + 6у₅ +2у₇);

^w4 = ³⁰ “ У2^;

^w₅ = 4° - у₇;

F = 270 - (-4yj - 6у₂ - 5у₄ - 10у₅ - 8у₇ ) -> max.

Для получения оптимального решения задачи построим симплекс-таблицы (табл. 1.12- 1.15).

Таблица 1.12

Таблица 1.13

Таблица 1.14

Таблица 1.15

В последней симплекс-таблице (табл. 1.15) содержится оптимальное решение

У1=°, у₂=30, У₄=О, у₅ =164, у₇=40.

Затем осуществляется переход к старым переменным

х, =30, х₇ =30, х, =0, Хг =164, Хх =492, х₇ =50.

1 ’2 ’ 4 ’ э ’о ’ /

Таким образом, при выпуске изделия вида А в объеме 30 шт., вида В -30 шт., вида С - 10 шт., изделия вида D не выпускаются, вида Е - 164 шт., вида F - 492 шт., вида G - 50 шт. будет получена максимальная прибыль в размере 2410 тыс.руб.

Для планирования объемов производства характерны также задачи на минимум. Они имеют некоторые особенности. Например, при структуре ограничений, изображенной на рис. 1.1, не имеет смысла решать задачу на минимум, поскольку целевая функция всегда будет проходить через начало координат и равняться нулю. Если же среди ограничений будут неравенства вида «>», получаем иную структуру области допустимых решений и оба типа оптимизации экономически содержательны (рис. 1.3).

Рис. 1.3. Графическое представление оптимальных планов задач на минимум и максимум:

Fj, F₂ - целевые функции для решения задач на минимум и максимум;

Aj, А₂ - точки оптимума для задач обоих типов;

^xlmin ’ ^x2min ’ ^Xlmax ’ ^Х2пих " ^{оптимальные} планы задач обоих типов

Смысл ограничения вида “>” поясним в нижеследующих задачах.

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

Таблица 1.16

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

Решение

Осуществляем математическую постановку задачи.

Пусть Xj - количество выпускаемой продукции і-го вида:

Х(>0 (і = й).

Тогда ограничения по ресурсу

^х1 + ^х2 + Зх₃ < 900;

• 2xj + 4х₂ + 2х₃ < 1000;
• 7xj + 9х₂ + 6х₃ > 1800

и целевая функция

F = 4х | + 5х ₂ + 2х ₃ —> min .

Данная задача так же, как и задача из примера 1.5, не имеет явно выраженного допустимого базисного решения, так как имеется ограничения вида «>». Однако это ограничение-неравенство связывает более чем одну переменную х-, поэтому простые алгебраические преобразования не приведут к желаемому результату. В таких случаях необходимо воспользоваться методом искусственного базиса. Для этого следует перейти от ограничений-неравенств к ограничениям-равенствам путем введения в неравенства дополнительных переменных

X] + ^х2 + Зх₃ + Wj = 900;

• 2Х] + 4х₂ + 2х₃ + w₂ =1000;
• 7Х| + 9х₂ + 6х₃ - w₃ =1800.

Если принять переменные Х| равными нулю (т.е. свободными), то переменная w₃ будет отрицательной, что недопустимо. Согласно методу искусственного базиса в ограничение-равенство с переменной w₃ вводится еще одна переменная w₄

7xj +9x₂ +6x₃ -w₃ +w₄ =1800.

Также как переменная w₄ вводится в равенство, то необходимо, чтобы она равнялась нулю. Однако если переменные Х| и w₃ принять равными нулю, то переменная w₄ будет равна 1800. Для того чтобы привести её к нулю, формируется ещё одна целевая функция f, имеющая вид

f = w₄ —>min .

Тогда математическая постановка задачи будет следующей

^Х1 ^{+ х}2 ⁺3x₃+W! =900;

• 2Х|+4х₂+2х₃+w₂ =1000;
• 7Х] +9x₂+6x₃-w₃+w₄ =1800;

F = 4x₁ +5х₂ +2х₃ -H>min ;

f = w₄ —>min .

Переменные Xj и w₃ принимаются равными нулю, т.е. являются свободными, тогда переменные Wj,w₂,w₄ будут базисными. Однако целевая функция не может содержать базисные переменные, поэтому

f = w₄ =1800 -(7Х| +9х₂ +6х₃ - w₃)—>min.

Для того чтобы воспользоваться алгоритмом на максимум, умножим обе целевые функции на -1

• -F = -4xj -5х₂ -2х₃ —>тах;
• -f = -1800 -(-7xj -9х₂ -6х₃ + w₃ )—>тах .

Затем базисные переменные следует выразить через свободные переменные и представить ограничения-неравенства и целевые функции в виде, удобном для заполнения симплекс-таблицы

Wj = 900 - (Xj + х₂ +3х₃);

w₂ =1000-(2Х| +4х₂ +2х₃ );

w₄ =1800-(7xj +9х₂ + 6х₃ -w₃);

• -F = 0-(4xj +5х₂ +2х₃)—>max;
• - f = -1800 -(-7хJ -9х₂ -6х₃ + w₃ ) —>max .

В первых двух симплекс-таблицах (табл. 1.17, 1.18) предпоследняя строка отводится для целевой функции -F, а последняя строка - -f. Решение ведётся по последней строке -f. Завершается применение метода искусственного базиса лишь в том случае, если значение целевой функции -f и коэффициентов при свободных переменных в этой функции станут равными нулю, за исключением коэффициента при переменной w ₄, который будет иметь значение 1.

Таблица 1.17

Таблица 1.18

Из табл. 1.18 следует, что

-f = 0-(0-Xj +w₄ + 0-х₃ +0-w₃), f = W₄ =0.

Поэтому завершается применение метода искусственного базиса, который позволил привести к нулю переменную w ₄, добавленную в ограничение-равенство, и получить начальное допустимое базисное решение, имеющее вид х^ =0, х₂ =200, х₃ =0, Wj =700, w₂ =200, w₃=0.

Зная начальное допустимое базисное решение, можно найти оптимальное решение данной задачи (табл. 1.19, 1.20).

Таблица 1.19

Таблица 1.20

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

Х| =0, х₂ =0, х₃ =300, W] =0, w₂ =1000, w₃ =0, F = 600.

Таким образом, выпуская продукцию вида С в объеме 300 шт. и не выпуская продукцию видов А и В, предприятие достигнет минимума затрат на производство и выполнит директивный уровень плана.

Задача 1.9. В механическом цехе машиностроительного предприятия на пяти операциях обрабатывается четыре вида изделия. При известной трудоёмкости обработки изделий на каждой операции и имеющемся фонде времени работы оборудования необходимо составить программу выпуска изделий, позволяющую получить максимум прибыли (табл. 1.21).

Таблица 1.21

Задача 1.10. Определить оптимальную производственную программу предприятия, обеспечивающую минимальную себестоимость выпускаемых изделий, при условии полного использования ресурсов. Объём ресурсов, норма затрат на единицу продукции представлены в табл. 1.22.

Таблица 1.22

Задача 1.11. Предприятие располагает четырьмя группами технологического оборудования, на котором может изготавливаться шесть видов изделий. Трудоёмкость обработки, стоимость каждого из шести видов изделий, а также фонд времени работы оборудования приведены в табл. 1.23.

Таблица 1.23

Требуется организовать такую программу производства, при которой достигается максимальная стоимость продукции, причем изделий вида А необходимо изготовить не более 60 шт., вида В - не менее 20 шт. и не более 50 шт. видов С и D - в комплектности 2:3, вида Е - ровно 30 шт. и вида F - не менее 10 шт.

Задача 1.12. Предприятие располагает тремя видами основных производственных ресурсов, используя которые можно изготовить шесть видов изделий. Норма затрат ресурсов, себестоимость каждого вида изделий, а также объем каждого вида ресурсов представлены в табл. 1.24.

Таблица 1.24

Требуется организовать такую программу производства, при которой обеспечивались бы минимальные затраты на производство при условии полного использования ресурсов. Необходимо произвести изделий вида А не менее 200 шт. и не более 500 шт., вида В - не более 400.шт., видов С, D и Е - в комплектности 2:1:2 и вида F - не менее 200 шт.

Задача 1.13. Месячная производственная программа механического цеха предприятия состоит из трех видов изделий. Изделия проходят обработку на четырех операциях. Трудоемкость обработки, себестоимость, оптовая цена изделия каждого вида, а также фонд времени работы оборудования приведены в табл. 1.25.

Таблица 1.25

Требуется определить такую программу производства, при которой достигается минимум затрат на производство при условии выполнения директивного уровня плана, составляющего 2400 тыс.руб.

Задача 1.14. Месячная производственная программа предприятия состоит из трех видов изделий. Изделия проходят обработку на трех операциях. Трудоемкость обработки, прибыль от реализации, оптовая цена изделия каждого вида, а также фонд времени работы оборудования представлены в табл. 1.26.

Таблица 1.26

Требуется определить такую программу производства, при которой достигается максимум прибыли от реализации при условии выполнения директивного уровня плана, составляющего 2800 тыс.руб.

Задача 1.15. Цех мебельного комбината выпускает трельяжи, трюмо и тумбочки. Норма расхода материала в расчёте на одно изделие, плановая себестоимость оптовая цена предприятия, плановый (месячный) ассортимент и трудоемкость единицы продукции приведены в табл. 1.27, Запас ДСП досок еловых и березовых 90, 30 и 14 м³ соответственно. Плановый фонд рабочего времени 16800 чел.-ч.

Таблица 1.27

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

Задача 1.16. На приобретение оборудования для нового производственного участка выделено 300 тыс.руб. Его предполагается разместить на площади 45 кв.м. Участок может быть оснащен оборудованием трех видов: машинами стоимостью 6 тыс.руб. за 1 шт., каждая машина размещается на площади 9 кв.м, и производит за смену 8 тыс.ед. продукции; машинами стоимостью 3 тыс.руб., занимающим площадь 4 кв.м, каждая, и производительно стью 4 тыс.ед. продукции за смену; машинами стоимостью 2 тыс.руб., занимаемая одной машиной площадь 3 кв.м., производительность 3 тыс.ед. продукции за смену.

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

Задача 1.17. В плановом году строительные организации города, переходят к сооружению домов четырех типов. Данные о количестве квартир разного типа в каждом из указанных типов домов, их плановая себестоимость представлены в табл. 1.28. Годовой план ввода жилой площади составляет соответственно 800, 1 000, 900, 2000 и 7000 квартир указанных типов.

Таблица 1.28

Исходя из необходимости выполнения плана ввода квартир (возможно перевыполнение), определить план строительства на год, минимизирующий себестоимость всех вводимых домов.