Решение задачИ СИМПЛЕКСНЫМ МЕТОДОМ

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

Из первого уравнения системы ( 7.1 ) видно, что дополнительное неизвестное в него вводить не нужно, так как неизвестное Х₄ входит только в одно уравнение. Разница между этими неизвестными состоит только в том, что для получения единичной подматрицы искусственное неизвестное вводится с коэффициентом, равным единице, а коэффициент при неизвестном Х₄ равен 10. Для устранения этого различия разделим обе части этого уравнения на 10 и получим равенство: 3/l0Х₁ + 2/5Х₂ + 1/2Х₃ + 1Х₄ = 24.

Остальные уравнения преобразуем в симплексные, в результате получим систему:

24 = 3/l0Х₁ + 2/5Х₂ + 1/2Х₃ + 1Х₄ + 0Х₅ + 0Х₆

100 = 2Х₁ + 0Х₂ + 1Х₃ + 0Х₄ + 1Х₅ + 0Х₆ ( 7.7 )

80 = 1Х₁ + 2Х₂ + 1Х₃ + 0Х₄ + 0Х₅ + 1Х₆

При решении задач на минимум целевой функции коэффициенты при искусственных неизвестных в целевой функции принимаются равными числу М (очень большому числу). В нашем примере коэффициенты, равные числу М, будут иметь искусственные неизвестные X₅ и Х₆, а для неизвестного Х₄, выполняющего роль искусственного в первом уравнении, коэффициентом должна быть величина отходов при данном способе раскроя, т.е. нулевая величина, с которой данное неизвестное входит в целевую функцию.

В симплексную таблицу уравнение целевой функции должно быть включено в следующем виде:

F = 200Х₁ + 400Х₂ + 200Х₃ + 0Х₄ + МХ₅ + МХ₆ ( 7.8 )

Симплексная система уравнений ( 7.7 ) записывается в симплексной табл. 7.2, а затем по расчетному алгоритму выполняется решение задачи. Оптимальное решение получается на второй итерации (табл. 7.4). Оно предусматривает раскрой 68 листов картона, в том числе первым способом (Х₁) 50 листов, вторым (Х₂) 15 листов и четвертым (Х₄) 3 листа.

Таблица 7.2

Таблица 7.3

Первая итерация

Подставив полученные значения неизвестных в систему исходных уравнений ( 7.7 )

3*50 + 4*15 + 10*3 = 240

2*50 = 100 ( 7.9 )

1*50 + 2*15 = 80

убеждаемся, что решение правильное и обеспечивает получение минимальной величины отходов: F = 200*50 + 400*15 = 16000, ( 7.10 )

что составляет к общему размеру разрезаемых листов картона 3,9 %. Размер остающихся кусков меньше, чем размер самой маленькой заготовки, и они не могут быть использованы.

Таблица 7.4

Вторая итерация (оптимальное решение)