Министерство образования Российской Федерации

САНКТ-ПЕТЕРБУРСКИЙ ГОСУДАРСТВЕННЫЙ

ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ

филиал в г. Чебоксары

Кафедра высшей математики

Математическое программирование.

Учебное пособие

по изучению дисциплины «Математика»

для студентов второго курса всех специальностей

Чебоксары 2008

Рецензенты:

Составители: канд. физико-математических наук Т.А. Санаева.

Обсуждено

На заседании кафедры высшей математики

Учебное пособие предназначено для студентов очной, заочной формы обучения составлено в соответствии с рабочей программы учебной дисциплины «Математика». В учебном пособии приведены методические рекомендации по построению математических моделей и решению задач исследования операций, рассмотрены примеры решения задач, предложены задачи для самостоятельного решения.

Рекомендовано к изданию Научно-методическим советом филиала Санкт-Петербургского государственного инженерно-экономического университета г. Чебоксары.

Введение

Учебное пособие составлено в соответствии с действующим государственным стандартом по курсу высшей математики для специальностей СПбГИЭУ, в программу которого входит курс высшей математики.

Данное пособие предназначено для студентов второго курса очной, заочной форм обучения. Пособие охватывает материал по линейному программированию, теории игр, балансовые модели. В нем предложен теоретический материал: основные понятия, определения, теоремы; формулы необходимые для решения задач. Приведены решения типовых задач, задачи для самостоятельного решения, контрольные работы, предназначенные для закрепления, самостоятельного освоения пройденного материала.

Особое внимание в учебном пособии было уделено вопросам построения математических моделей как основополагающему и наиболее творческому этапу решения задач.

Предложен список литературы, рекомендуемый для самостоятельного изучения по данным темам.

1. Целочисленное программирование

По смыслу части экономических задач, относящихся к задачам линейного программирования, компоненты решения должны выражаться в целых числах, т.е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при загрузке оборудования, число вычислительных машин в управляющем комплексе и многие другие.

Если требование целочисленности накладывается на все переменные, имеющиеся в математической модели задачи (включая все остаточные и избыточные переменные, вводимые в модель при ее приведении к стандартной форме), то такая задача называется полностью целочисленной. Если требование целочисленности накладывается лишь на некоторые переменные, то задача называется частично целочисленной.

Задача линейного целочисленного программирования формулируется следующим образом: найти такое решение Х=(х₁, х₂,…, х_n), при котором линейная функция

(1.1)

принимает максимальное или минимальное значение при ограничениях

(1.2)

Иногда задачи целочисленного программирования решают приближенно. Отбросив условие целочисленности, решают задачу методом линейного программирования, затем в полученном оптимальном решении округляют переменные до целых чисел. Такой прием можно использовать, если значения переменных достаточно велики и погрешностью округления можно пренебречь. Если значения переменных невелики, то округление может привести к значительному расхождению с оптимальным решением. Существует основные методы решения задач целочисленного программирования – метод Гомори и метод ветвей и границ.