1 Теоретические сведения
Задача принятия решения в математической постановке часто сводится к отысканию оптимального значения функции на множестве ограниченных значений переменных или переменной. Термин «оптимальный» происходит от латинского optimus ― наилучший. Ограничения значений переменных задаются равенствами или неравенствами. Подобные задачи оптимизации с ограничениями называются задачами математического программирования.
Постановка задачи математического программирования состоит, например, в следующем: найти такие значения переменных xj (j =1, 2,…, n), которые, находясь в границах интервалов dj £ xj £ Dj, удовлетворяли бы граничным значениям bi функций ограничений gi (xj)£ bi (i =1, 2,…, m) и придавали бы целевой функции E = f (xj) оптимальное (наибольшее или наименьшее) значение. В большинстве практических задач переменные xj неотрицательные.
Формальное описание задачи математического программирования представляется критерием оптимизации (max или min)
Е = f (xj)®max (min), (1.1)
ограничениями
gi (xj)£ bi (1.2)
и граничными условиями
dj £ xj £ Dj. (1.3)
Число переменных и ограничений конечное: j =1, 2,…, n; i =1, 2,…, m.
Классификация задач математического программирования по видам переменных и зависимостей между переменными системы (1.1)-(1.3) представлена в таблице 1.1.
Таблица 1.1 ― Классификация задач математического программирования
| Признак классификации | Название класса задач | Методы оптимизации |
| Линейные алгебраические зависимости в целевой функции и ограничениях | Линейное программирование | Симплекс-метод |
| Дифференциальные зависимости между переменными в функции времени | Оптимальное управление или динамическая оптимизация | |
| Хотя бы одно ограничение или только целевая функция является нелинейной зависимостью | Нелинейное программирование | |
| Переменные принимают только дискретные значения | Дискретное, целочисленное программирование | Симплекс-метод+метод ветвей и границ Метод отсечений. Метод Баллаша |
| Целевая функция, ограничения содержат случайные величины | Стохастическое программирование |
Зависимости, в которых переменные или производные находятся в первой степени, называют линейными. Если в зависимости имеются переменные в степени выше первой или произведения нескольких переменных, то такие зависимости называют нелинейными.
Непрерывная переменная в заданном интервале граничных условий может принимать любые значения, а дискретная переменная ― лишь определённые значения. Целочисленная дискретная переменная принимает только целые значения. Целочисленная булева переменная принимает только два значения: 0 и 1.
Задача линейного программирования применительно к распределению ресурсов между объектами записываются, например, так:
С = 
®min, (1.4)
³ ri, i =1, 2,…, m, (1.5)
xj ³ dj, (1.6)
где С ― оценка получаемого результата; xj ― количество объектов вида j, на которые выделяется часть ресурсов; cj ― «вклад» объекта вида j в получаемый результат; ri ― предельное значение количества ресурсов вида i; rij ― количество ресурсов вида i, выделяемое объекту вида j; dj ― граничные значения количества объектов вида j; n ― количество видов объектов; m ― количество видов ресурсов.
Если не накладывается условие целочисленности переменных, то задача решается методами линейного программирования. В противном случае задача решается методами целочисленного программирования!
Задача линейного программирования решается симплекс-методом в Matlab с использованием функции linprog.
2 Задание и методические указания
Рацион питания человека составляется из четырёх видов продуктов (таблицы 2.1, 2.2). Количество продуктов xj вида j в рационе не менее dj. Стоимость единицы продуктов вида j составляет cj. Известно, что в продуктах содержатся два вида питательных веществ. В единице продуктов вида j содержится rij питательных веществ вида i. Человеку необходимо не менее ri питательных веществ вида i. Требуется оптимизировать симплекс-методом по критерию минимальной стоимости количество продуктов в рационе питания.
Таблица 2.1 ― Исходные данные
| Вид продуктов, j | Минимальное количество продуктов в рационе, dj | Стоимость единицы продуктов, cj | Минимальное количество питательных веществ необходимое человеку, ri | Содержание питательных веществ в единице продуктов, rij | ||
| r 1 | r 2 | r 1 j | r 2 j | |||
| Число условных единиц | ||||||
| d 1 | c 1 | |||||
| d 2 | c 2 | |||||
| d 3 | c 3 | |||||
| d 3 | c 4 |
Таблица 2.2 ― Варианты задания
| Вариант | ||||||||||||||||
| c 1 | ||||||||||||||||
| c 2 | ||||||||||||||||
| c 3 | ||||||||||||||||
| c 4 | ||||||||||||||||
| Значения d 1, d 2,, d 3, d 4 выбирать самостоятельно. |
Методические указания по выполнению практической работы:
а) изучить лекции по математическому программированию;
б) сформулировать ответы на контрольные вопросы;
в) изучить рекомендуемую литературу по теме занятия;
г) выполнить задание:
1) выполнить формальную постановку задачи линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями, для заданного варианта исходных данных;
2) представить описание синтаксиса функции linprog в табличной форме с комментариями;
3) обосновать выбор варианта синтаксиса функции linprog для решения поставленной задачи;
4) составить программу оптимизации диеты симплекс-методом с использованием функции linprog и графического интерфейса пользователя Matlab;
4) решить задачу для исходных данных, указанных в таблицах 2.1 и 2.2;
5) результаты решения задачи представить в табличной форме (таблица 2.3).
д) представить отчёт о работе в электронном виде преподавателю на очередном практическом занятии, ответить на контрольные вопросы.
Таблица 2.3 ― Рекомендуемая форма представления результатов оптимизации диеты
| Вид продуктов | Количество продуктов в рационе | Ограничения (минимальное количество питательных веществ) | Количество питательных веществ | Стоимость | |||||||||
| планируемое | оптимальное | в единице продуктов | в планируемом рационе | в оптимальном рационе | единицы продуктов | планируемого рациона | оптимального рациона | ||||||
| r 1 | r 2 | r 1 j | r 2 j | r 1П | r 2П | r 1О | r 2О | ||||||
| Число условных единиц | |||||||||||||
| d 1 | c 1 | ||||||||||||
| d 2 | c 2 | ||||||||||||
| d 3 | c 3 | ||||||||||||
| d 3 | c 4 | ||||||||||||
| å= | å= | å= | å= | å= | å= |
Интерфейсом пользователя предусматривается импортирование в рабочее пространство Matlab таблицы исходных данных (таблица 2.1) из архива по задаваемому адресу или ввод исходных данных в интерактивном режиме, ввод задания в форме, предусматриваемой синтаксисом функции linprog, представление результатов оптимизации в форме, предусматриваемой синтаксисом функции linprog, экспорт результатов оптимизации в архив по задаваемому адресу.
Отчёт о работе должен содержать титульный лист, задание, формальную постановку задачи линейного программирования, содержащую критерий оптимизации с ограничениями и граничными условиями, описание синтаксиса функции linprog, представление исходных данных и задания в форме, предусматриваемой синтаксисом функции linprog, текст программы Matlab с комментариями, результаты оптимизации в форме таблицы 2.3, выводы.
3 Рекомендуемая литература
1 Справочник по оптимизационным задачам в АСУ/ В.А. Бункин, Д. Колев, Б.Я. Курицкий и др. ― Л.: Машиностроение, 1984. ― 212 с.
2 Кетков Ю.Л., Кетков А.Ю., Шульц М.М. MATLAB 7: программирование, численные методы. ― СПб.: БХВ-Петербург, 2005. ― 752 с. Глава 16. Линейное программирование.
3 Решение задач линейного программирования в среде MATLAB / А.Н. Сергеев, Н.А. Соловьёва, Е.К. Чернэуцану [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: https://dha.spb.ru/PDF/MatLabLP.pdf. — Загл. с экрана.
4 Рыкин О.Р. Упражнения по дисциплине «Системный анализ и принятие решений» в среде пакета MАТЛАБ 6,5: методические указания. Редакция 28.02.03 [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: https://www.ii.spb.ru/material/methodical_m/m_3/Methodical_and_manuals_3_9.pdf. — Загл. с экрана.
5 Гольдштейн А.Л. Оптимизация в среде Matlab: учебное пособие / А.Л. Голдштейн. ― Пермь: Изд-во Перм. нац. исслед. политехн. ун-та, 2015. ― 192 с. Подробно описаны функции пакетов Toolbox Optimization и Toolbox Global Optimization Matlab с многочисленными примерами.
6 Реализация симплекс метода [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: https://www.studfiles.ru/preview/6008218/page:23/. — Загл. с экрана. Реализация симплекс-метода в Excel и Matlab.
+7 Колокольникова А.И., Киренберг А.Г. Спецразделы информатики: введение в MatLab: учебное пособие [Электронный ресурс]. — Электрон., текстовые дан. — Режим доступа: books.google.ru/books?id=MGQ5CwAAQBAJ&pg=PA51&lpg=PA51&dq=linprog+%D0%BC%D0%B0%D1%82%D0%BB%D0%B0%D0%B1+%D1%81%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%81&source=bl&ots=oLKkFGWH1c&sig=Mr42GZ388c8tjj7QSwJanaWTZ4o&hl=ru&sa=X&ved=0ahUKEwigmuXvr6fZAhUGDiwKHT0tB7kQ6AEIYzAG#v=onepage&q=linprog%20%D0%BC%D0%B0%D1%82%D0%BB%D0%B0%D0%B1%20%D1%81%D0%B8%D0%BD%D1%82%D0%B0%D0%BA%D1%81%D0%B8%D1%81&f=false. Содержит постановку и решение задачи оптимизации рациона питания в Matlab.
Контрольные вопросы и задания
1 Почему задачи вида (1.10) называются задачами линейного математического программирования.
2 Пояснить разницу между целевой функцией и критерием оптимизации.
3 Изобразить графически область допустимых решений для следующих ограничений:
;
;
.
4 Найти максимальное и минимальное значения целевой функции 
при ограничениях , , .