2i.SU
Математика

Математика

Содержание раздела

Простейшие неопределенные уравнения

Решение задачи о раскрое фанеры

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

Поэтому выберем в качестве свободных неизвестных x1 и х2 и выразим х3, х4, x5 через х1 и х2. Для этого значение x3 = 800 - х1 - х2 подставим в первые два уравнения, получим:

21700-6.jpg

Теперь, давая х1 и х2 целые значения, получим всевозможные решения системы уравнений (3) в целых числах. Исследуйте самостоятельно, какие целые неотрицательные значения следует давать х1 и x2, чтобы x3, x4 и x5 также были неотрицательными. Ниже приведена таблица некоторых решений системы (3).

Из таблицы видно, что листов фанеры достаточно и что самый выгодный способ раскроя будет при x1 = 0, x2 = 100, x3 = 700. В этом случае образуются "лишние" заготовки еще для 100 изделий. В других случаях "лишние" заготовки будут некомплектными. Но нужно ли раскраивать все 800 листов? Ведь нужны заготовки для 1000 изделий, а не для 1100.

Поэтому практический интерес представляет следующий дополнительный вопрос к этой задаче: какое наименьшее число f листов фанеры следует взять со склада и какими из указанных способов следует кроить взятые листы, чтобы выполнить заказ? Для ответа на этот вопрос из всех решений в целых неотрицательных числах системы уравнений

21700-7.jpg

нужно выбрать такое решение (x1, x2, x3, x4, x5), для которого f = x1+x2+x3 принимает наименьшее значение, или, как мы будем говорить дальше, удовлетворяет условию минимальности.

Чтобы облегчить поиски, откажемся временно от требования, чтобы значения неизвестных были целыми. Попытаемся решить нашу задачу удачным выбором свободных неизвестных. Удобнее всего такими выбрать x4, х5 и какое-нибудь из неизвестных х1, x2, x3. Определяя из уравнений (15) сначала, например, х1, а затем x2 и опуская промежуточные выкладки, будем иметь:

21700-8.jpg

При данном значении х3 наименьшее значение f мы получим, если неизвестным x4 и x5 дадим нулевое значение (это и понятно, ведь x4 и x5 - количество "лишних" заготовок!). Пусть х4 = х5 = 0. Легко видеть, что при возрастании значений неизвестного х3 значение f будет убывать. Но рост x3 сдерживается требованием, чтобы значения неизвестных х1 и x2 были неотрицательными. Так как

21700-9.jpg

то из равенств (16) (при x4=x5 =0)

21700-10.jpg

видно, что при возрастании х3 отрицательные значения прежде всего будет принимать неизвестное х1. Поэтому естественно неизвестное х1 сделать свободным, а неизвестное x3 - зависимым.

Определяя из уравнений (15) неизвестные х2 и x3, найдем:

21700-11.jpg

Легко видеть, что наименьшее значение f получим, если свободным неизвестным х1, x4 и х5 дадим нулевые значения. При этом для зависимых неизвестных получим положительные значения:

21700-12.jpg

Следовательно, решение

21700-13.jpg

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

21700-14.jpg

или даже f>=728, так как число f должно быть целым. Можно ожидать, что искомое решение мы полуним, если немного изменим значения неизвестных. Положим, например, x1=0, x2 = 91, x3 = 637. Тогда

21700-15.jpg

 

х1 0 0 0 100 100 100 100 200 200 200 300 300
х2 0 100 200 0 100 200 300 200 300 400 400 500
Х3 800 700 600 700 600 500 400 400 300 200 100 0
Х4 400 200 0 600 400 200 0 400 200 0 200 0
X5 200 300 400 0 100 200 300 0 100 200 0 100

А это убеждает нас, что целочисленное решение с условием минимальности найдено. Итак, со склада достаточно взять лишь 728 листов фанеры и 91 из них кроить по второму, а остальные по третьему способу.

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

Весьма многие проблемы экономики, в частности вопросы планирования производства и перевозок, приводят к этим задачам.

перейти к началу страницы


2i.SU ©® 2015 Яндекс.Метрика Рейтинг@Mail.ruРейтинг@Mail.ru