Задача № 328

 

 

        Для производства двух видов изделий А и В используются три типа технологического оборудования. Для производства единицы изделия А оборудование первого типа используется в течении 1 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 3 часа.

         Для производства единицы изделия В оборудование первого типа используется в течении 2 часа, оборудование второго типа – 3 часа, оборудование третьего типа – 1 час.

         На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часа, оборудование второго типа – 60 часов, оборудование третьего типа – 50 часов.

         Прибыль от реализации единицы готового изделия А составляет 4 денежные единицы, а изделия В – 2 денежные единицы.

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

         Решить задачу симплекс-методом путем преобразования симплекс-таблиц. Дать геометрическое истолкование задачи, используя для этого ее формулировку с ограничениями – неравенствами.

 

 

Решение.

 

        Перед нами – классическая задача линейного программирования. Под планом производства понимается ответ на простой вопрос: сколько изделий А и сколько изделий В надо выпустить, чтобы прибыль была максимальна.

         Прибыль рассчитывается по формуле: .

 

         Запишем математическую модель задачи:

 

 

         Чтобы проиллюстрировать применение симплекс-метода решения этой задачи, решим ее графически.

         Для этого построим на плоскости  области, описываемые ограничениями-неравенствами, и прямую , которая называется целевой функцией.

 

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

 

         График целевой функции (построен синим цветом) передвигается в направлении, обозначенном стрелкой (по-научному – в направлении своего градиента), до тех пор, пока не достигнет граничной точки многоугольника – в нашем случае это точка – (15 ; 5).  В этой точке целевая функция будет достигать максимума.

 

 

 

 

         А теперь решим эту задачу симплекс-методом. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам, введя дополнительные переменные .

 

 

   i         Базис                B

4

2

0

0

0

A1

A2

A3

A4

A5

1

2

3

A3

A4

A5

0

0

0

32

20

50

1

1

3

2

1

1

1

0

0

0

1

0

0

0

1

4

Fi - Ci

 

0

-4

-2

0

0

0

1

2

3

A3

A4

A1

0

0

4

46/3

10/3

50/3

0

0

1

5/3

2/3

1/3

1

0

0

0

1

0

-1/3

-1/3

1/3

4

Fi - Ci

 

200/3

0

-2/3

0

0

4/3

1

2

3

A3

A2

A1

0

2

4

7

5

15

0

0

1

0

1

0

1

0

0

-5/2

3/2

-1/2

1/2

1/2

1/2

4

Fi - Ci

 

70

0

0

0

1

3

 

 

         Симплекс-таблица составляется так:

         В графе Базис записываются вектора переменных, принимаемые за базисные. На первом этапе это – A3, A4, A5. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.

         В следующий столбец  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В столбец свободных членов. Далее идут столбцы коэффициентов Аi при  i й переменной.

         Под столбцом свободных членов записывается начальная оценка

 

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

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

 

         Преобразование симплекс-таблицы ведется следующим образом:

 

         Шаг 1: Проверяется критерий оптимальности, суть которого состоит в том, что все оценки  должны быть неотрицательны. В нашем случае этот критерий не выполнен, поэтому переходим ко второму шагу.

 

         Шаг 2: Для отрицательных оценок вычисляются величины:

 

 

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

 

        Шаг 3: Третья строка таблицы делится на 3 и вычитается из первой и второй строк. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса.

        Таким образом, новыми базисными переменными становятся A3, A4, A1.

 

 

        Возвращаемся к шагу 1 и повторяем весь процесс.

Под столбцом свободных членов записывается начальная оценка

 

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

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

 

         Опять проверяется критерий оптимальности. Отрицательная оценка только одна – в столбце А2.

 

         Вычисляем:

 

 

         Разрешающим элементом будет второй элемент второго столбца – 2/3.

 

         Новыми базисными переменными становятся A3, A2, A1

         Делим вторую строку на 2 и вычитаем из третьей.

         Умножаем вторую строку на 5/2 и вычитаем из первой.

 

 

 

        На этот раз отрицательных оценок нет, т.е. критерий оптимальности выполнен.

 

Таким образом, получается искомое значение целевой функции F(15; 5; 7; 0; 0) = 70, т.е. возвращаясь к системе неравенств, получаем:

 

 

        Ответы, полученные различными методами, совпадают.

 

 

ЛАА 2004