Министерство образования республики беларусь белорусский государственный университет гуманитарный факультет Кафедра информационных технологий

Приложение 5 Целочисленное программирование

Пример. Задача о ранце. Имеется m-вектор ограниченных ресурсов , которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз обладает следующими свойствами: 1) неделимостью; 2) полезностью ; 3) расходом i-го ресурса для перевозки единицы j-го груза  . Выбрать такой номер груза для перевозки, при котором максимизируется

Составим математическую модель задачи. Обозначим через количество выбранных для транспортировки предметов. Требованию неделимости соответствует условие

целые, 

. (13.3)

Частным случаем задачи (13.1) – (13.2) является задача о ранце, в которой любой из заданного набора предметов

найти максимум функции

Решим задачу геометрически (рис. 13.1). Область поиска экстремума – многоугольник OABCD. Так как линия уровня целевой функции параллельна стороне BC многоугольника, экстремум достигается в вершинах  и , а также в любой точке отрезка BC и равен 7. Нас интересуют лишь точки с целочисленными координатами, поэтому ни B, ни C не являются допустимым решением задачи. Округлив значение координат точек B и C, получим точку (4; 3), не принадлежащую области поиска. Легко показать, что целочисленный оптимум достигается в точках M(2; 3) и N(3; 2) и равен 5. Обе точки находятся внутри области поиска.

Приложение 6. Краткое описание MatLab

• 
  панель инструментов с кнопками и раскрывающимся списком;
  
• 
  окно с вкладками Launch Pad и Workspace, из которого можно получить доступ к различным модулям ToolBox и к содержимому рабочей среды;
  
• 
  окно с вкладками Command History и Current Directory, предназначенное для просмотра и повторного вызова ранее введенных команд, а также для установки текущего каталога;
  
• 
  командное окно, в котором находится приглашение к вводу » и мигающий вертикальный курсор;
  
• 
  строку состояния.
  
• 
  
  

1. 
   открывает журнал в файле exampl-1.txt; 
   
2. 
   производит вычисления; 
   
3. 
   сохраняет все переменные в MAT файле work-1.mat; 
   
4. 
   сохраняет журнал в файле exampl-1.txt в подкаталоге work корневого каталога MatLab и закрывает MatLab;