РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОЙ ОПТИМИЗАЦИИ МАТЕМАТИЧЕСКИМ МЕТОДОМ
учебно-методический материал по алгебре (10 класс)

Задача.

Для производства двух видов изделий A и B используются три типа технологического оборудования. Для производства одного изделия A оборудование первого типа используется в течение 1 часа, оборудование второго типа – 3 часов, оборудование третьего типа – 3 часов. Для производства одного изделия B оборудование первого типа используется в течение 2 часов, оборудование второго типа – 3 часов, оборудование третьего типа – 1 часа. На изготовление всех изделий предприятие может использовать оборудование первого типа не более чем 32 часов, оборудование второго типа – не более 60 часов, оборудование третьего типа – не более 50 часов. Прибыль от реализации одного готового изделия A составляет 4 денежных единиц, а изделия В - 2 денежных единиц. Составить план производства изделий A и B, обеспечивающий максимальную прибыль от их реализации.

Решение.

Определим максимальное значение целевой функции F(X) = 4x1+2x2 при следующих условиях-ограничений.

x1+2x2≤32
3x1+3x2≤60
3x1+x2≤50
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных.

В 1-м неравенстве смысла (≤) вводим базисную переменную x3.

В 2-м неравенстве смысла (≤) вводим базисную переменную x4.

В 3-м неравенстве смысла (≤) вводим базисную переменную x5.

x1+2x2+x3 = 32

3x1+3x2+x4 = 60

3x1+x2+x5 = 50

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Полагая, что свободные переменные равны 0, получим первый опорный план:
X0 = (0,0,32,60,50)

Базисное решение называется допустимым, если оно неотрицательно.

Вычислим значения Di по строкам как частное от деления: bi / ai1
и из них выберем наименьшее:
min (32 : 1 , 60 : 3 , 50 : 3 ) = 162/3
Следовательно, 3-ая строка является ведущей.
Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x5 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x5 плана 0 на разрешающий элемент РЭ=3. На месте разрешающего элемента получаем 1.

В остальных клетках столбца x1 записываем нули.

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

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.
Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:

Определение новой свободной переменной.
Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:
min (151/3 : 12/3 , 10 : 2 , 162/3 : 1/3 ) = 5
Следовательно, 2-ая строка является ведущей.
Разрешающий элемент равен (2) и находится на пересечении ведущего столбца и ведущей строки.

Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.
Таким образом, в новом плане 2 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.
Представим расчет каждого элемента в виде таблицы:

Получаем новую симплекс-таблицу:

 Проверка критерия оптимальности.

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи.

Окончательный вариант симплекс-таблицы:

Оптимальный план можно записать так:
x1 = 15, x2 = 5
F(X) = 4*15 + 2*5 = 70
Анализ оптимального плана.
В оптимальный план вошла дополнительная переменная x3. Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 2-го вида в количестве 7
Значение 0 в столбце x1 означает, что использование x1 - выгодно.
Значение 0 в столбце x2 означает, что использование x2 - выгодно.