Материал: УП - Методы оптимальных решений

В. Ф. Казак, Е. В. Морозова, И. Э. Симонова

Методы

оптимальных решений

МИНОБРНАУКИ РОССИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

КАМЫШИНСКИЙ ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО БЮДЖЕТНОГО ОБРАЗОВАТЕЛЬНОГО

УЧРЕЖДЕНИЯ ВЫСШЕГО ОБРАЗОВАНИЯ

«ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ»

В. Ф. Казак, Е. В. Морозова, И. Э. Симонова

Методы

оптимальных решений

Учебно-методическое пособие

Волгоград

2016

УДК

Рецензенты:

Печатается по решению редакционно-издательского совета

Волгоградского государственного технического университета

Казак, В. Ф.

Методы оптимальных решений: учебно-методическое пособие / В. Ф. Казак, Е. В. Морозова, И.Э. Симонова; ВолгГТУ. – Волгоград, 2016. – 110 с.

ISBN

Излагается теоретическое обоснование методов математического моделирования (основные понятия, теоремы, алгоритмы) и приводятся примеры их применения.

Предназначено в помощь студентам, изучающим дисциплины «Методы оптимальных решений», «Теория принятия решений» и др..

Ил.: 28. Табл.: 42. Библиогр.: 7 назв.

ISBN  Волгоградский

государственный

технический

университет, 2016

Оглавление

1. Предмет математического программирования. Линейное программирование

1.1. Введение. Предмет математического программирования

Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных ва­риантов в условиях рыночных отношений приходится находить наилуч­шие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. До недавнего времени большинство таких задач решалось, исходя из здравого смысла и опыта лиц, принимающих решения или просто «на глаз». При таком подходе не было и не могло быть никакой уверенности, что найденный вариант наи­лучший, а при современных масштабах производства даже незначитель­ные ошибки оборачиваются громадными потерями. В связи с этим воз­никла необходимость применять для анализа экономической ситуации математические методы и вычислительную технику. Такие методы объе­диняются под общим названием математическое программирование или математическое моделирование.

Математическое программирование − область математики, раз­раба­тывающая теорию и численные методы решения многомерных экстре­мальных задач с ограничениями, т. е. задач на экстремум функции мно­гих переменных с ограничениями на область определения этих перемен­ных. Функция, экстремальное значение которой нужно найти в условиях экономических возможностей, называется целевой функцией или показа­телем эффективности, или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это со­ставляет математическую модель задачи.

Математическая модель задачи – это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математиче­ского программирования включает:

_{1) совокупность неизвестных величин , действуя} на которые, систему можно совершенствовать. Её называют планом задачи (вектором управления, решением, стратегией, поведением и т. д.);

2) целевую функцию (она позволяет выбирать наилучший вариант из множества возможных). Её обозначают Z = Z (х). Это может быть прибыль, объем выпуска или реализация продукции, затраты производства, издержки и т. д.;

3) условия (или систему ограничений), налагаемые на неизвестные величины; эти условия могут быть материальные, финансовые, трудовые ресурсы, возможности технического и научного потенциала. Математические ограничения выражаются в виде уравнений и нера­венств. Их совокупность образует область допустимых решений (ОДР). Если ОДР обозначим за q, то модель задачи математического программи­рования примет вид:

mах (min) Z = Z ( },  Q.

Или в развернутом виде: найти план = (х₁ ... х_n), доставляющий экстремальное значение це­левой функции z при ограничениях _i (х₁ ... х_n) =  B_i. Из экономиче­ских соображений на план задачи налагаются условия неотрицательности х_i  0, иногда целочисленности. Допустимый план, доставляющий функ­ции цели экстремальное значение, называется оптимальным.

Начало ма­тема­тического программирования было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем. Составными частями ма­тематического программирования являются линейное, нелинейное, дискретное, ди­намическое программирование, а также теория игр и графов.

1.2. Линейное программирование. Общие понятия

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

Таким образом, задачи линейного программирования относятся к за­дачам на условный экстремум функции. Казалось бы, что для исследова­ния линейной функции многих переменных на условный экстремум дос­таточно применить хорошо разработанные методы математического ана­лиза. Однако, невозможность их применения показывают простейшие примеры. Пусть необходимо исследовать на экстремум линейную функцию Z = Z (x₁; x₂;…x_n) = при линейных ограничениях

Так как Z – линейная функция, то в общем случае , а, следовательно, внутри области экстремальных точек не существует. Значит, min (mах) значения линейной функции находятся на границе области, которая образована системой ограничений. Для отыскания этих значений потре­бовалось создание специальных методов. Особенно широкое распростра­нение математическое программирование получило в экономике, так как исследование зависимостей между величинами, встречающимися во мно­гих экономических задачах, приводит к линейной функции с линейными ограничениями.

1.3. Построение математических моделей простейших экономических задач

1. Задача использования сырья

Пусть некоторая производственная единица (цех, завод и т. д.), исходя из конъюнктуры рынка, технических возможностей может выпускать п различных видов продукции. Предприятие при их производстве должно ограничиться каким-то количеством различных видов ресурсов (сырье, полуфабрикаты, рабочая сила, оборудование, электроэнергия и т. д.). Пусть их число равно т.

Рассмотрим задачу на конкретном примере. Для изготовления двух видов продукции Р₁, Р₂ используют три вида сырья S₁, S₂, S₃. Запасы сырья, количество единиц продукции, а также величина прибыли, получаемая oт реализации единицы продукции, приведены в табл. 1.

Таблица 1

Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.

Обозначим через х₁ – количество изготовленных единиц продукции Р₁, х₂ – количе­ство изготовленных единиц продукции Р₂. Тогда, учитывая количество единиц сырья, идущих на изготовление единицы продукции, а также запасы сырья, получим систему ограничений: _{(количество сырья, идущего на изготовление продукции, не должно превышать запасы сырья).}

Также на х₁ и х₂ должно быть наложено ограничение неотрицатель­ности х₁  0, х₂  0. Конечную цель решаемой задачи – получение макси­мальной прибыли при реализации продукции, выразим как функцию цели Z = 50х₁ + 40х₂ (руб.). Числа х₁, х₂ могут быть и дробными, так как в задаче не оговорены условия целочисленности.

Итак, мы построили ма­тематиче­скую модель задачи использования сырья (ресурсов): найти max значение целевой функции Z = 50 х₁ + 40 х₂ при ограничениях

Обобщим эту задачу (табл. 2).

Таблица 2

Математическая модель задачи

Пусть дан план = x₁, x₂, … x_n где x_j – количество изготовленной единиц j продукции. Тогда требуется найти целевую функцию Z = c₁x₁ + c₂x₂ + … + c_nx_n при ограничениях (условиях):

2. Задача о смесях.

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

При откорме каждое животное ежедневно должно получить не менее 9 единиц питательного вещества S₁, не менее 8 единиц вещества S₂ и не менее 12 единиц вещества S₃. Для составления рациона используют два вида корма. Содержание количества единиц питательных веществ в 1 кг каждого вида корма и стоимость 1 кг корма приведены в табл. 3.

Таблица 3

Необходимо составить дневной рацион нужной питательности, причем затраты на него должны быть min.

Для составления математической модели обозначим через x₁, x₂ – количество килограммов корма соответственно 1 и 2 в дневном рационе:

Цель данной задачи – добиться min затрат на дневной рацион, поэтому общую стоимость рациона можно выразить целевой функцией Z = 4x₁ + 6x₂.

Задачу составления рациона можно обобщить, если предусмотреть в рационе т видов питательных веществ в количестве не менее В_i (i= ) и использовать n видов кормов. Обозначим через а_ij − количество единиц i-го питательного вещества, содержащего-ся в единице j-го корма, c_j − стоимость единицы j корма, x_j – количество единиц j-го корма в дневном рационе. Тогда, требуется найти min Z = с₁х₁ + с₂х₂ + … + с_n х_n, при ограничениях:

Помимо этих задач, можно привести примеры задач о раскрое мате­риалов, о размещении заказа, транспортной задачи и т. д.