Приложение 5 Целочисленное программирование
Приведем примеры целочисленных задач линейного программирования.
Пример. Задача о ранце. Имеется m-вектор ограниченных ресурсов , которые можно использовать для перевозки различных по своим характеристикам грузов. Каждый j-й груз обладает следующими свойствами: 1) неделимостью; 2) полезностью ; 3) расходом i-го ресурса для перевозки единицы j-го груза . Выбрать такой номер груза для перевозки, при котором максимизируется общая полезность рейса (суммарная стоимость перевезенных за рейс грузов).
Составим математическую модель задачи. Обозначим через количество выбранных для транспортировки предметов. Требованию неделимости соответствует условие
целые, (13.1)
Сопоставление расходов ресурсов каждого типа для транспортировки единицы груза и их наличия приводит к ограничению
(13.2)
Общая полезность рейса определяется значением функции
. (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. Обе точки находятся внутри области поиска.
Рисунок 13.1
Несостоятельность округления подчеркивается также следующими соображениями. Несмотря на то, что целочисленные переменные обычно выражают количество неделимых предметов, возможны и другие типы спецификации этих переменных. Так в задаче о ранце решение представляется булевой переменной (x = 0 или x = 1). В этом случае бессмысленно оперировать дробными значениями величины x и процедура округления является логически неприемлемой.
Из приведенного примера видно, что для решения задач целочисленного программирования необходимо рассмотреть особые методы оптимизации. Кроме того, оптимальное решение задач целочисленного программирования не обязательно принадлежит границе многогранника (многоугольника) условий, что характерно для задач линейного программирования.
Приложение 6. Краткое описание MatLab
А. Начало работы в MatLab
Начало работы в MatLab начинается с запуска самой программы.
1) Для этого нажмите на иконку
2) Должна открыться рабочая среда MatLab
3) Рабочая среда MatLab содержит следующие элементы:
-
панель инструментов с кнопками и раскрывающимся списком;
-
окно с вкладками Launch Pad и Workspace, из которого можно получить доступ к различным модулям ToolBox и к содержимому рабочей среды;
-
окно с вкладками Command History и Current Directory, предназначенное для просмотра и повторного вызова ранее введенных команд, а также для установки текущего каталога;
-
командное окно, в котором находится приглашение к вводу » и мигающий вертикальный курсор;
-
строку состояния.
-
4) Команды следует набирать в командном окне:
Символ »
, обозначающий приглашение к вводу командной строки, набирать не нужно. Для просмотра рабочей области удобно использовать полосы скроллинга или клавиши Home, End, для перемещения влево или вправо, и PageUp, PageDown для перемещения вверх или вниз. Если вдруг после перемещения по рабочей области командного окна пропала командная строка с мигающим курсором, просто нажмите Enter.
Важно помнить, что набор любой команды или выражения должен заканчиваться нажатием на Enter, для того, чтобы программа MatLab выполнила эту команду или вычислила выражение.
В. Простейшие вычисления в MatLab
1) Наберите в командной строке 1+2 и нажмите Enter.
В результате в командном окне MatLab отображается следующее:
MatLab сначала вычислила сумму 1+2, затем записала результат в специальную переменную ans и вывела ее значение, равное 3, в командное окно.
Ниже ответа расположена командная строка с мигающим курсором, обозначающая, что MatLab готов к дальнейшим вычислениям.
Можно набирать в командной строке новые выражения и находить их значения.
Если требуется продолжить работу с предыдущим выражением, например, вычислить (1+2)/4.5, то проще всего воспользоваться уже имеющимся результатом, который хранится в переменной ans.
Пример:
Наберите ans/4.5 (при вводе десятичных дробей используется точка) и нажмите Enter, получается:
C. Эхо команд в MatLab
1) Выполнение каждой команды в MatLab сопровождается эхом.
В приведенном выше примере — это ans = 0.6667.
Эхо затрудняет восприятие работы программы и тогда его можно отключить.
2)Отключение эхо. Для этого команда должна завершаться символом точка с запятой.
Например:
D.Cохранение MatLab файлов
1) Сохранить все значения переменных — использовать в меню File-> пункт Save Workspase As.
При этом появляется диалоговое окно Save Workspase Variables, в котором следует указать каталог и имя файла.
По умолчанию предлагается сохранить файл в подкаталоге work основного каталога MatLab.
Программа сохранит результаты работы в файле с расширением mat. Теперь можно закрыть MatLab.
2) В следующем сеансе работы для восстановления значений переменных следует открыть этот сохраненный файл при помощи File-> Open . Теперь все переменные, определенные в прошлом сеансе, опять стали доступными. Их можно использовать во вновь вводимых командах.
E.Как вести журнал работы в MatLab
1) В MatLab имеется возможность записывать исполняемые команды и результаты в текстовый файл, который потом можно прочитать или распечатать из текстового редактора.
Для начала ведения журнала служит команда diary.
В качестве аргумента команды diary следует задать имя файла, в котором будет храниться журнал работы.
Набираемые далее команды и результаты их исполнения будут записываться я в этот файл, например последовательность команд:
2) производит следующие действия:
-
открывает журнал в файле exampl-1.txt;
-
производит вычисления;
-
сохраняет все переменные в MAT файле work-1.mat;
-
сохраняет журнал в файле exampl-1.txt в подкаталоге work корневого каталога MatLab и закрывает MatLab;
3) Посмотрите содержимое файла exampl-1.txt в каком-нибудь текстовом редакторе. В файле окажется следующий текст:
F.Окно справки(Помощь)
1) Окно справки MatLab появляется после выбора Help-> Help Window ( или нажатием кнопки вопроса на панели инструментов).
2)Эта же операция может быть выполнена при наборе команды helpwin.
3) Для вывода окна справки по отдельным разделам, наберите helpwin topic. Окно справки предоставляет Вам такую же информацию, как и команда help, но оконный интерфейс обеспечивает более удобную связь с другими разделами справки.
3) Используя адрес Web-страницы фирмы Math Works.
|
