Детская энциклопедия

Меню сайта











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

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

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

x3 =800-х12,

х4=400+2х1-2х2,

х5=200-2x1+х2.

Теперь, давая x1 и x2 целые значения, по­лучим всевозможные решения системы (3) в целых числах.

Исследуйте самостоятельно, какие целые неотрицательные значения следует давать х1 и х2, чтобы х3, х4 и х5 также были неотрицатель­ными.

Ниже приведена таблица некоторых решений системы (3).

Из таблицы видно,

что листов фанеры до­статочно и что самый выгодный способ раскроя будет при x1=0, x2=100, х3=700. В этом случае

образуются «лишние» заготовки еще для 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]:




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

Исключая из уравнений (15) неизвестные x2 и x3, найдем:

 

 

 

 

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

 

 

 

 

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

 

или даже f 728,

так как число должно быть целым. Можно ожидать, что искомое решение мы получим, если немного изменим значение неизвестных. Поло­жим, например, х1=0, х2=91, х3=637. Тогда:

 

 

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

 

Решенная нами задача о раскрое фанеры относится к числу задач, составляющих пред­мет теории линейного програм­мирования.

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





 
Календарь
«  Декабрь 2016  »
ПнВтСрЧтПтСбВс
   1234
567891011
12131415161718
19202122232425
262728293031

Новые статьи
Каталог статей
Как подготовить ребенка к школе
Освоение навыков чтения
Природные материалы на уроках труда

Статистика




 
Адрес почты Вопросы по рекомендациям, размещению рекламы и обратных ссылок обращайтесь pochta@enciklopediya1.ru
2013 © 2016