|
Меню сайта
Статистика
|
Решение задачи о раскрое фанерыРешение задачи о раскрое фанерыТеперь приступим к решению системы уравнений (3). Мы имеем три уравнения с пятью неизвестными. Поэтому два неизвестных будут свободными, а остальные три — зависимыми. Конечно, в качестве зависимых неизвестных нужно брать те, у которых абсолютная величина коэффициентов минимальна. Поэтому выберем в качестве свободных неизвестных х1 и х2 и выразим x3, х4, х5 через x1 и x2. Для этого значение х3=800-х1-x2 подставим в первые два уравнения, получим: x3 =800-х1-х2, х4=400+2х1-2х2, х5=200-2x1+х2. Теперь, давая x1 и x2 целые значения, получим всевозможные решения системы (3) в целых числах. Исследуйте самостоятельно, какие целые неотрицательные значения следует давать х1 и х2, чтобы х3, х4 и х5 также были неотрицательными. Ниже приведена таблица некоторых решений системы (3). Из таблицы видно,
образуются «лишние» заготовки еще для 100 изделий. В других случаях «лишние» заготовки будут некомплектными. Но нужно ли раскраивать все 800 листов? Ведь нужны заготовки для 1000 изделий, а не для 1100. Поэтому практический интерес представляет следующий дополнительный вопрос к этой задаче: какое наименьшее число / листов фанеры следует взять со склада и какими из указанных способов следует кроить взятые листы, чтобы выполнить заказ? Для ответа на этот вопрос из всех решений в целых неотрицательных числах системы уравнений
для которого f=x1+x2+x3 принимает наименьшее значение, или, как мы будем говорить дальше, удовлетворяет условию минимальности. Чтобы облегчить поиски, откажемся временно от требования, чтобы значения неизвестных были целыми. Попытаемся решить нашу задачу удачным выбором свободных неизвестных. Удобнее всего такими выбрать x4, х5 и какое-нибудь из неизвестных x1, x2, x3. Поэтому, исключая из уравнений (15) сначала, например, x1, а затем x2 и опуская промежуточные выкладки, будем иметь: 
При данном значении х3 наименьшее значение f мы получим, если неизвестным x4 и х5 дадим нулевое значение (это и понятно, ведь x4 и x5 — количество «лишних» заготовок!). Пусть x4=x5=0. Легко видеть, что при возрастании значений неизвестного х3 значение f будет убывать. Но рост х3 сдерживается требованием, чтобы значения неизвестных х1 и x2 были неотрицательными. Так как
то из равенств [см. (16) при x4=x5=0]:
Исключая из уравнений (15) неизвестные x2 и x3, найдем:
Легко видеть, что наименьшее значение f получим, если свободным неизвестным х1, x4 и x5 дадим нулевые значения. При этом для зависимых неизвестных получим положительные значения:
системы (15) удовлетворяет условию минимальности. Но нам требуется найти целочисленное решение в неотрицательных числах, удовлетворяющее условию минимальности. Из приведенных рассуждений следует, что для такого решения
или даже f ≥ 728, так как число должно быть целым. Можно ожидать, что искомое решение мы получим, если немного изменим значение неизвестных. Положим, например, х1=0, х2=91, х3=637. Тогда:
А это убеждает нас, что целочисленное решение с условием минимальности найдено. Итак, со склада достаточно взять лишь 728 листов фанеры и 91 из них кроить по второму, а остальные по третьему способу.
Решенная нами задача о раскрое фанеры относится к числу задач, составляющих предмет теории линейного программирования. В этой теории рассматривают задачи следующего типа: из всех решений в неотрицательных числах некоторой системы уравнений первой степени найти решение, удовлетворяющее условию минимальности. Иногда, как в задаче о раскрое фанеры, выдвигают дополнительное требование, чтобы значения неизвестных были целыми числами. Весьма многие проблемы экономики страны, в частности вопросы планирования производства и перевозок, приводят к этим задачам.
|
ПОИСК
Block title
|
что листов фанеры достаточно и что самый выгодный способ раскроя будет при x1=0, x2=100, х3=700. В этом случае 
