Математическое программирование
Покупка
Основная коллекция
Тематика:
Программирование и алгоритмизация
Издательство:
Новосибирский государственный технический университет
Автор:
Гусев Сергей Анатольевич
Год издания: 2023
Кол-во страниц: 134
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-7782-4996-7
Артикул: 875908.01.99
Учебное пособие составлено на основе курса лекций, который читается автором для студентов IV курса факультета бизнеса Новосибирского государственного технического университета. В нем излагаются такие разделы математического программирования, как линейное программирование, целочисленное линейное программирование и динамическое программирование. Пособие может быть полезно студентам других специальностей, изучающим методы оптимизации, а также специалистам, которые занимаются решением прикладных оптимизационных задач на основе математического моделирования.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ С. А. ГУСЕВ МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Утверждено Редакционно-издательским советом университета в качестве учебного пособия НОВОСИБИРСК 2023
УДК 519.85(075.8)
Г962
Рецензенты:
канд. экон. наук, науч. сотр. ИВМ и МГ СО РАН О. А. Ляхов
канд. техн. наук, доцент Г. Ы. Токтошов
Работа подготовлена кафедрой экономической информатики
для студентов, обучающихся по направлению 38.03.05
«Бизнес-информатика»
Гусев С. А.
Г962
Математическое программирование: учебное пособие /
С. А. Гусев. – Новосибирск: Изд-во НГТУ, 2023. – 134 c.
ISBN 978-5-7782-4996-7
Учебное пособие составлено на основе курса лекций, который читается автором для студентов IV курса факультета бизнеса Новосибирского государственного технического университета. В нем излагаются
такие разделы математического программирования, как линейное программирование, целочисленное линейное программирование и динамическое программирование. Пособие может быть полезно студентам
других специальностей, изучающим методы оптимизации, а также специалистам, которые занимаются решением прикладных оптимизационных задач на основе математического моделирования.
УДК 519.85(075.8)
ISBN 978-5-7782-4996-7
© Гусев С. А., 2023
© Новосибирский государственный
технический университет, 2023
ÂÂÅÄÅÍÈÅ Значительное число задач, возникающих в экономике, представляют собой оптимизационные задачи планирования производства, т. е. задачи, в которых при заданных условиях производства требуется определить параметры, обеспечивающие минимальные или максимальные значения некоторых показателей производственной деятельности. Как правило, оптимизационные задачи для нахождения оптимальных производственных планов ‒ это задачи минимизации затрат или максимизации прибыли. Для их решения математическими методами требуется сформулировать экономическую постановку на языке математики, т. е. построить математическую модель. В результате получаются задачи нахождения минимальных или максимальных значений некоторых функций при заданных ограничениях на переменные. Задачи такого типа относят к условно-экстремальным задачам. При определении оптимального производственного плана даже одного небольшого предприятия бывает необходимо учитывать и объединять в одно целое большое количество связей и числовых значений всевозможных характеристик. Соответственно при этом возникают довольно сложные математические задачи, решение которых аналитически возможно лишь в исключительных случаях, но может быть успешным в результате построения математических моделей и применения специально разработанных численных методов. Теория и численные методы решения многомерных экстремальных задач есть предмет изучения такой области математики, которая называется математическим программированием. Термин «программирование» связан с тем, что большинство решаемых задач определяет план (программу) функционирования экономической системы (ЭС). Большинство оптимизационных задач, решаемых методами математического программирования, есть задачи нахождения максимума
(минимума) некоторой заданной целевой функции ( , , ) n f x x , на переменные которой наложены ограничения вида 1 1 1 1 ( , , ) , ( , , ) , n m n m g x x b g x x b где 1, , n g g – некоторые заданные функции. В математическом программировании выделяют следующие основные разделы в зависимости от вида целевой функции и ограничений. Линейное программирование – целевая функция линейна, а множество, на котором ищется экстремум, задается системой линейных равенств и неравенств. Целочисленное программирование – на переменные накладывается условие целочисленности. Нелинейное программирование – целевая функция и ограничения нелинейные. К нелинейному программированию относятся следующие разделы. Выпуклое программирование – целевая функция выпукла, если решается задача минимизации, и вогнута, если решается задача максимизации, а множество, на котором ищется экстремум функции, – выпукло. Квадратичное программирование – целевая функция представляет собой квадратичную форму, а ограничения – линейные равенства и неравенства. Стохастическое программирование – задачи оптимизации, которые содержат случайные параметры в функциях, задающих ограничения. Приведем примеры некоторых задач, которые решаются методами математического программирования. 1. Задача о рационе. По заданному ассортименту продуктов при известном содержании в них питательных веществ и известной стоимости продуктов составить рацион, удовлетворяющий необходимым потребностям с минимальными затратами на покупку продуктов. Пусть имеется n продуктов и m питательных веществ. Пусть ij a – содержание j -го питательного вещества в единице веса i-го продукта;
через jb обозначим минимальную суточную потребность в j -м питательном веществе, а ic ‒ стоимость единицы веса i-го продукта. Обозначим ix – суточное потребление i-го продукта, которое нужно определить. Величина 1 n ij j i a x есть общее содержание j -го питательного вещества в рационе, которое не должно быть меньше минимальной потребности jb : 1 n ij i j i a x b , 1, , j m . Таким образом, задача выбора рациона состоит в минимизации линейной функции при ограничениях на переменные в виде неравенств. Найти 1 min n i i i c x при условиях: 1 n ij i j i a x b , 1, , j m , 0 ix , 1, , i n . Приведенная задача является задачей линейного программирования. 2. Транспортная задача. Общая постановка такой задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в n пунктов назначения. При этом критерием оптимальности обычно являются минимальные затраты на перевозку всего груза. Обозначим ij c – затраты на перевозку единицы груза из i-го пункта отправления в j -й пункт назначения, ia – запасы груза в i-м пункте отправления, jb – потребности в грузе в j -м пункте назначения, а ij x – количество единиц груза, перевозимого из i -го пункта отправления в j -й пункт назначения. Тогда математическая
постановка задачи будет состоять в определении минимального значения функции m n ij ij i j c x при условиях: 1 m ij j i x b , 1, , j n , 1 n ij i j x a , 1, , i m , 0 ij x , 1, , i m , 1, , j n . Приведенная задача, так же как и предыдущая, является задачей линейного программирования. 3. Задача о ранце. Турист готовится к походу. В рюкзаке он может нести груз, масса которого не более G кг. Этот груз может включать n видов предметов. Один предмет -го j вида имеет массу j g кг, 1, , j n . Для каждого вида предмета турист определяет его ценность jc во время похода. Обозначим jx – количество предметов j -го типа в рюкзаке. Задача состоит в таком наполнении рюкзака предметами указанных видов, чтобы общая ценность снаряжения была максимальной. Запишем математическую модель задачи: требуется найти 1 max n j j j c x при условиях: 1 n j j j g x G , 0 jx , jx – целое, 1, , j n Данная задача является задачей целочисленного программирования.
4. Задача распределения капиталовложений. Для увеличения объемов выпуска пользующейся повышенным спросом продукции предприятиям выделены капиталовложения в объеме S тыс. руб. Использование i-м предприятием ix тыс. руб. из указанных средств обеспечивает прирост выпуска продукции, определяемый значением нелинейной функции ( ) i i f x . Задача состоит в определении способа распределения капиталовложений между предприятиями, обеспечивающего максимальное увеличение выпуска продукции. Математическая постановка задачи состоит в определении 1 max ( ) n i i j f x при условиях: 1 n i i x S , 0 ix , 1, , i n Сформулированная задача является задачей нелинейного программирования.
1. ËÈÍÅÉÍÎÅ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈÅ 1.1. ÇÀÄÀ×È ËÈÍÅÉÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß Линейное программирование – это область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума линейной функции многих переменных при наличии линейных ограничений. В зависимости от вида ограничений и от того, какой экстремум линейной функции, минимум или максимум, надо найти, рассматривают различные формы задач линейного программирования (ЛП). Рассмотрим эти формы. Пусть 1, , n x x – упорядоченный набор n вещественных чисел. Этому набору можно поставить в соответствие n-мерный вектор 1 ) ( , , n X x x вещественного линейного пространства n R . Определение 1.1. Задачей ЛП в общей форме называется задача определения максимального (минимального) значения функции 1 ( ) n j j j z X c x (1.1) при условиях: 1 1 , 1, , , , 1, , , 0, 1, , ( ). n ij j i j n ij j i j j a x b i k a x b i k m x j l l n
Функция ( ) z X называется целевой функцией, а условия (1.2) – ограничениями задачи ЛП. Определение 1.2. Задача ЛП представлена в симметричной форме, если она имеет следующий вид: 1 ( ) max n j j j z X c x (1.3) при условиях: 1 , 1, , , 0, 1, , . n ij j i j j a x b i m x j n (1.4) В формуле (1.3) и далее символы « max» у целевой функции означают, что рассматривается задача максимизации целевой функции. Определение 1.3. Канонической формой задачи ЛП называют следующее ее представление: 1 ( ) max n j j j z X c x (1.5) при условиях: 1 , 1, , , 0, 1, , . n ij j i j j a x b i m x j n (1.6) Приведенные три формы задач ЛП эквивалентны в том смысле, что от одной из указанных форм можно перейти к любой другой с помощью несложных преобразований. Задачу нахождения минимума функции 1 ( ) n j j j z X c x легко свести к задаче нахождения максимума, если рассмотреть функцию 1 ( ) ( ) ( ) n j j j z X z X c x
Ограничение-неравенство 1 1 2 2 i i in n i a x a x a x b можно преобразовать в ограничение-равенство путем добавления новой неотрицательной переменной 1 n x к левой части этого неравенства: 1 1 2 2 1 i i in n n i a x a x a x x b . Ограничение-неравенство 1 1 2 2 i i in n i a x a x a x b можно преобразовать в ограничение-равенство путем вычитания новой неотрицательной переменной 1 n x из левой части этого неравенства: 1 1 2 2 1 i i in n n i a x a x a x x b . Если надо перейти от ограничений-равенств к ограничениям-неравенствам, то каждое ограничение-равенство 1 1 2 2 i i in n i a x a x a x b можно представить в виде пары неравенств: 1 1 2 2 1 1 2 2 , . i i in n i i i in n i a x a x a x b a x a x a x b Если на переменную kx не наложено условие неотрицательности, то вместо нее можно ввести две неотрицательные переменные k u и kv , полагая . k k k x u v 1.2. ÂÛÏÓÊËÛÅ ÌÍÎÆÅÑÒÂÀ Â n-ÌÅÐÍÎÌ ÏÐÎÑÒÐÀÍÑÒÂÅ Определение 1.4. Множество M в n-мерном пространстве n R называется выпуклым, если с любыми двумя точками ,a b M множеству M принадлежат также все точки отрезка, соединяющего a и b , т. е. [0,1] (1 ) a b М . Легко можно проверить, что множества 1 1 1 1 0 ( , , ) | n n n M x x a x a x a и 2 1 1 1 0 ( , , ) | n n n M x x b x b x b являются выпуклыми.