МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

СЫКТЫВКАРСКИЙ ЛЕСНОЙ ИНСТИТУТ (ФИЛИАЛ)

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

ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

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

ЛЕСОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ С. М. КИРОВА»

Кафедра автоматизации технологических процессов и производств Б. М. Шифрин

МЕТОДЫ ОПТИМИЗАЦИИ

Учебное пособие Утверждено учебно-методическим советом Сыктывкарского лесного института в качестве учебного пособия для студентов направления бакалавриата 110300 «Агроинженерия»

и специальностей 110301 «Механизация сельского хозяйства», 110302 «Электрификация и автоматизация сельского хозяйства»

всех форм обучения Самостоятельное учебное электронное издание Сыктывкар СЛИ УДК 330. ББК 65. Ш Печатается по решению редакционно-издательского совета Сыктывкарского лесного института Ответственный редактор:

Е. Ю. Сундуков, кандидат экономических наук, доцент Шифрин, Б. М.

Ш65 Методы оптимизации [Электронный ресурс] : учебное пособие : самост. учеб. электрон. изд. / Б. М. Шифрин ; Сыкт. лесн. ин-т. – Электрон. дан. – Сыктывкар : СЛИ, 2013.

– Режим доступа: http://lib.sfi.komi.com. – Загл. с экрана.

В издании помещены материалы для освоения дисциплины «Методы оптимизации».

Предназначено для студентов направления бакалавриата 110300 «Агроинженерия» и специальностей 110301 «Механизация сельского хозяйства», 110302 «Электрификация и автоматизация сельского хозяйства» всех форм обучения, преподавателей, практических работников.

УДК 330. ББК 65. Темплан 2013 г. Изд. № 5.

Самостоятельное учебное электронное издание ШИФРИН Борис Маркович, кандидат технических наук, доцент

МЕТОДЫ ОПТИМИЗАЦИИ

Электронный формат – pdf. Объем 2,2 уч.-изд. л.

Сыктывкарский лесной институт (филиал) федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Санкт-Петербургский государственный лесотехнический университет имени С. М. Кирова» (СЛИ), 167982, г. Сыктывкар, ул. Ленина, 39, [email protected], www.sli.komi.com Редакционно-издательский отдел СЛИ. Заказ № © Шифрин Б. М., © СЛИ,

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Общая постановка задачи линейного программирования и пример задачи выбора оптимального ассортимента

1.2. Графический способ решения задач линейного программирования

1.3. Решение задач линейного программирования с помощью MS Excel

1.4. Анализ оптимального решения на чувствительность

2. ОСНОВНЫЕ ВИДЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ, СВОДЯЩИХСЯ К ЗАДАЧАМ

ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

2.2. Задача оптимального раскроя материала

2.3. Задача коммивояжера

2.4. Транспортная задача

ЗАДАНИЯ ДЛЯ ПРАКТИЧЕСКИХ РАБОТ

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

ВВЕДЕНИЕ

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

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

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

Оптимизацией называется задача поиска экстремальных значений (минимума или максимума) целевой функции (ЦФ) среди множества ее возможных значений, определяемых ограничениями.

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

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

В зависимости от свойств ЦФ и функции ограничений все задачи математического программирования делятся на два основных класса:

• задачи линейного программирования;

• задачи нелинейного программирования.

Если ЦФ и функции ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования.

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

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи: рационального использования сырья и материалов; задачи оптимизации раскроя; оптимизации производственной программы предприятий; оптимального размещения и концентрации производства; составления оптимального плана перевозок, работы транспорта; управления производственными запасами; и многие другие, принадлежащие сфере оптимального планирования. Так, по оценкам американских экспертов, около 75 % от общего числа применяемых оптимизационных методов приходится на линейное программирование.

Преимущество этого класса задач в том, что разработаны универсальные алгоритмы для решения таких задач большой размерности. Впервые задача линейного программирования была сформулирована в 1939 г. Л. В. Канторовичем 1, который применил математическую модель этой задачи в экономике и разработал метод решения. С этого момента линейное программирование стало важным инструментом в методах оптимизации. Именно изучение задач линейного программирования (ЗЛП) и рассматривается в данном учебном пособии.

Канторович Л. В. Математические методы организации и планирования производства. Л. :

ЛГУ, 1939.

1. ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.1. Общая постановка задачи линейного программирования и пример задачи выбора оптимального ассортимента Линейное программирование – раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. Особенностью задач линейного программирования является то, что экстремума ЦФ достигает на границе области допустимых решений. Общей ЗЛП 2 называют задачу поиска экстремума ЦФ F при ограничениях:

где n – количество управляющих переменных xj; m – количество ограничений (m1 – количество ограничений вида, m2 – количество ограничений вида ); cj – коэффициенты ЦФ; aij – коэффициенты ограничений; bi – правые части ограничений.

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

Проанализируем задачу выбора оптимального ассортимента. Остальные типы задач будут рассмотрены в последующих разделах.

Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать различные виды продукции. Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнерТурчак Л. И. Основы численных методов. М. : Наука, 1987.

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

Рассмотрим конкретный пример.

Пусть предприятие планирует в будущем месяце изготавливать два продукта (А и В), прибыль по которым оценивается в 2500 и 3500 руб. соответственно.

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд (табл. 1.1). На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Прогнозируется, что в следующем месяце будет предоставлено 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

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

Таблица1.1 – Использование и предоставление ресурсов Наименование ресурса на единицу продукта объем ресурсов Линейная модель может быть построена в четыре этапа.

Этап 1. Определение переменных.

Существует целевая переменная F, которую необходимо оптимизировать.

Предприятие стремится максимизировать прибыль, следовательно, целевая переменная F – суммарная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных, чьи значения необходимо определить для получения оптимальной величины ЦФ, которая, в нашем случае является суммарной прибылью. Эта прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

x1 – количество единиц продукта А, произведенных в следующем месяце.

x2 – количество единиц продукта В, произведенных в следующем месяце.

Этап 2. Построение целевой функции.

В нашем примере каждый изготовленный продукт А приносит 2500 руб.

прибыли, а при изготовлении x1 единиц продукта А прибыль составит 2500x1.

Аналогично прибыль от изготовления x2 единиц продукта В составит 3500x2.

Таким образом, суммарная прибыль, полученная в следующем месяце за счет производства x1 единиц продукта А и x2 единиц продукта В, то есть целевая переменная F, составит:

Предприятие стремится максимизировать этот показатель. Таким образом, ЦФ в нашей модели:

Этап. 3. Определение ограничений.

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (т. е. значения x1 и x2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено x1 единиц, то будет потрачено 3x1, часов этого ресурса. Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено x2 продуктов, то потребуется 10x2 часов. Таким образом, общий объем машинного времени, необходимого для производства х1 единиц продукта А и х2 единиц продукта В, составляет 3x + 10x2. Это общее значение машинного времени не может превышать 330 часов.

Математически это записывается следующим образом:

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап 4. Запись условий неотрицательности.

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств x1 0 и x2 0. В нашем примере второе условия является избыточным, так как выше было определено, что x2 не может быть меньше 12.

Полная модель линейного программирования для нашей задачи может быть записана в виде:

Решение ЗЛП может быть найдено графически, с использованием надстройки MS Excel «Поиск решения» или с помощью специализированных компьютерных программ. Мы остановимся на первых двух способах, характеризующихся простотой и наглядностью.

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

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

Рассмотрим графический метод решения ЗЛП на нашем примере.

Оси на графике представляют собой две искомые переменные (рис. 1.1).

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

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

Рисунок 1.1 – Оси графика линейного программирования Первое ограничение в наше задаче определяется прямой 10 x1 + 20 x2 = 110, проходящей, например, через точки ( x1 = 3; x2 = 4) и ( x1 = 1; x2 = 5). Естественно, что для построения прямой на плоскости достаточно найти подстановкой две любые точки, принадлежащие этой прямой.

Графически первое ограничение отражено на рис. 1.2.

Рисунок 1.2 – Построение прямой для первого ограничения Аналогично отражаем на графике остальные ограничения (рис. 1.3).

Рисунок 1.3 – Построение прямых для всех ограничений Для определения, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку, например ( x1 = 0; x2 = 0). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Очевидно, в нашем случае относительно первых трех ограничений нужно выделять нижние полуплоскости, относительно четвертого ограничения – правую полуплоскость. Направление полуплоскости показывается на чертеже (рис. 1.4) штриховкой.

Общая часть (пересечение) всех этих полуплоскостей будет представлять собой ОДЗ данной задачи (EABCD).

В общем случае при построении ОДЗ в зависимости от конкретного вида системы ограничений на переменные 3 может встретиться одна из четырех ситуаций (рис. 1.5).

1. ОДЗ пустая, что соответствует несовместности системы неравенств; решений нет.

Алексеева Е. В. Построение математических моделей целочисленного линейного программирования. Новосибирск : НГУ, 2012.

2. ОДЗ изображается одной точкой А, что соответствует единственному решению системы.

3. ОДЗ ограниченная, изображается в виде выпуклого многоугольника.

Допустимых решений множество, множество оптимальных решений конечно.

4. ОДЗ неограниченная, в виде выпуклой многоугольной области. Допустимых решений множество, множество оптимальных решений может быть бесконечным в зависимости от ЦФ.

Рисунок 1.5 – Возможные случаи при построении ОДЗ В нашем примере, очевидно, случай 3.

Теперь в области допустимых решений необходимо определить значения х1 и х2, которые максимизируют F. Для этого сначала проводят вектор от точки ( x1 = 0; x2 = 0) к точке ( x1 = c1; x2 = c2 ), который указывает направление ЦФ. Потом строят линию уровня ЦФ, проходящую через ( x1 = 0; x2 = 0) перпендикулярно вектору (рис. 1.6).

Далее передвигают линию уровня ЦФ в направлении вектора до крайней точки ОДЗ (рис. 1.7). Как видно из чертежа, это точка С, находящаяся на пересечении линий: 3x1 + 10x2 = 330 и 6x1 + 6x2 = 240. Решение этой системы уравнений дает: x1 = 10, x2 = 30, F(x1 = 10, x2 = 30) = 130000.

Таким образом, предприятие должно запланировать на следующий месяц производство 10 изделий А и 30 изделий В, что позволит ему получить прибыль в размере 130 тыс. руб.

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

1. Начертите на графике две оси, представляющие собою два параметра решения; нарисуйте только I-й квадрант.

2. Определите координаты точек пересечения всех граничных условий с осями, подставляя в уравнения граничных условий поочередно значения х1 = и х2 = 0.

3. Нанесите линии ограничений модели на график.

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

5. Постройте вектор направления ЦФ от точки (х1 = 0; х2 = 0) к точке, координатами которой являются коэффициенты ЦФ.

6. Постройте линию уровня ЦФ, проходящую через точку (х1 = 0; х2 = 0) перпендикулярно этому вектору.

7. Далее передвигайте эту линию уровня в направлении вектора. Первая точка пересечения с ОДЗ будет соответствовать минимуму ЦФ, последняя – максимуму.

Рисунок 1.7 – Линия ЦФ достигла максимума в пределах ОДЗ (в точке С) 1.3. Решение задач линейного программирования Ручные методы решения задач математического программирования весьма трудоемки, поэтому для их решения обычно используют компьютеры. MS Excel повсеместно распространен и дает хорошие средства для решения и анализа задач 4.

Оптимизация линейных моделей в MS Excel производится симплексметодом – целенаправленным перебором опорных решений задачи линейного программирования. Алгоритм симплекс-метода сводится к построению выпуклого многогранника в многомерном пространстве, а затем к перебору его вершин с целью поиска экстремального значения ЦФ. Практически этот метод реализуется встроенной процедурой «Поиск решения» (Solver), являющейся одной из надстроек Excel.

Усольцев Л. А. Линейное программирование. Омск : Изд-во СибАДИ, 2008.

Использование процедуры «Поиск решения» предоставляет возможности:

– использования планов большой размерности (т. е. с большим количеством варьируемых переменных);

– задания ограничений сложного вида;

– отыскания оптимального из допустимых решений;

– генерирования множества различных решений, сохраняемых в дальнейшем в виде сценариев;

– автоматического создания отчетов по решению задачи.

Задачи, которые лучше всего решаются данным средством, имеют три основных свойства:

– имеется единственная цель, функционально связанная с другими параметрами системы, которую нужно оптимизировать (найти ее максимум, минимум или определенное числовое значение);

– имеются ограничения, выражающиеся, как правило, в виде неравенств (например, объем используемого сырья не может превышать запасов сырья на складе, или время работы станка за сутки не должно быть больше 24 часов минус время на обслуживание);

– имеется набор входных значений-переменных, влияющих на оптимизируемые величины и на ограничения.

Параметры задач ограничиваются такими предельными показателями:

– количество неизвестных – 200;

– количество формульных ограничений на неизвестные – 100;

– количество предельных условий на неизвестные – 400.

Алгоритм поиска оптимальных решений включает в себя несколько этапов:

– подготовительные работы;

– отладка решения;

– анализ решения.

Последовательность необходимых подготовительных работ, выполняемых при решении задач оптимизации с помощью MS Excel, приведена на блоксхеме (рис. 1.8).

Рисунок 1.8 – Последовательность работ при решении задач оптимизации Из приведенных пяти пунктов плана подготовительных работ только пятый пункт является формализуемым. Остальные работы могут быть выполнены по-разному. Кратко поясним сущность формулировок пунктов плана.

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

2. Под «составлением формализованной модели» понимается графическое описание задачи в виде таблицы, схемы или рисунка (например, рис. 1.1), упрощающее составление математической модели.

3. Математическая модель деятельности рассматриваемой реальной системы сводится к связыванию формулами отдельных элементов этой системы. В предыдущем примере мы выразили через формулы расход трудовых и материальных ресурсов, а ЦФ выразили через заданные константы нормативной прибыли.

4, 5. Представление математической модели в виде таблицы MS Excel и поиск решения будем подробно рассматривать на прошлом примере.

Рассмотрим подробно последние два этапа.

1. Создадим экранную форму и введем в нее исходные данные (рис. 1.9).

Рисунок 1.9 – Экранная форма для ввода данных ЗЛП Обратите внимание на формулу в ячейке С7. Это формула ЦФ. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений:

2. Проверьте, установлена ли надстройка «Поиск решения» (в разных версиях MS Excel она вызывается и устанавливается по-разному. В MS Excel2007, на примере которого рассматривается решение нашей задачи, надстройка «Поиск решения» должна быть на вкладке «Данные», группа «Анализ»).

Если надстройка «Поиск решения» не обнаружена, щелкните на кнопку Microsoft Office, а затем Параметры Excel. Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти». В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее).

3. После загрузки надстройки для поиска решения в группе «Анализ» на вкладке «Данные» становится доступна команда «Поиск решения» (рис. 1.10).

В поле «Установить целевую ячейку» выбираем ячейку со значением ЦФ – $C$7. Выбираем, максимизировать или минимизировать ЦФ. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. При необходимости можно задавать условия целочисленности переменных, например, как в рис. 1.11.

Рисунок 1.11 – Пример добавления ограничения на целочисленность х В разделе Параметры отмечаем галочками Линейную модель и Неотрицательные значения (в данном случае вторую галочку отмечать необязательно, поскольку неотрицательность переменных учтена за счет ограничений снизу).

4. Жмем «Выполнить». В появившемся окне «Результат поиска решения»

можно выбрать тип отчета. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, будет рассказано в следующем разделе. На основном листе появились значения максимизированной ЦФ – 130 000 руб. и изменяемых параметров х1 = 10 и х2 = 30. Таким образом, для максимизации дохода следует произвести 10 единиц продукта А и 30 единиц продукта В.

В случае бесконечного множества решений (рис. 1.5, случай 4) Excel выдает сообщение «Значения целевой ячейки не сходятся», а в случае несовместности ограничений (рис. 1.5, случай 1) – «Поиск не может найти подходящего решения».

1.4. Анализ оптимального решения на чувствительность На практике многие параметры (цены на продукцию и сырье, запасы сырья, спрос на рынке, заработная плата и т. д.) с течением времени меняют свои значения. Поэтому оптимальное решение ЗЛП, полученное для конкретной ситуации, после ее изменения может оказаться непригодным или неоптимальным.

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

Ограничения линейной модели классифицируются следующим образом (см. рис. 1.7). Связывающие ограничения проходят через оптимальную точку, например: 3x1 + 10x2 330 и 6x1 + 6x2 240. Несвязывающие ограничения не проходят через оптимальную точку, например 16x1 + 4x2 400 и х2 12. Аналогично ресурс, представляемый связывающим ограничением, называют дефицитным, а ресурс, представляемый несвязывающим ограничением, – недефицитным. Ограничение называют избыточным в том случае, если его исключение не влияет на область допустимых решений и, следовательно, на оптимальное решение (в нашей задаче таких нет).

Выделяют следующие три задачи анализа на чувствительность.

1. Анализ сокращения или увеличения ресурсов:

1) насколько можно увеличить (ограничения типа ) или уменьшить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

2) насколько можно уменьшить (ограничения типа ) или увеличить (ограничения типа ) запас недефицитного ресурса при сохранении полученного оптимального значения ЦФ?

2. Увеличение (уменьшение) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения целевых коэффициентов: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Проведем анализ чувствительности нашей задачи. Для этого необходимо после запуска в Excel задачи на решение в окне «Результаты поиска решения»

выделить с помощью мыши три типа отчетов: «Результаты», «Устойчивость»

и «Пределы» (рис. 1.12).

Рисунок 1.12 – Выделение типов отчетов, требуемых для анализа чувствительности После это в Excel будут созданы три новых листа – Отчет по результатам1, Отчет по устойчивости1 и Отчет по пределам1.

Отчет по результатам Отчет по результатам состоит из трех таблиц (рис. 1.13):

1) таблица 1 содержит информацию о ЦФ;

2) таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи;

3) таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий.

Если ресурс используется полностью (т. е. ресурс дефицитный), то в графе «Статус» соответствующее ограничение указывается как «связанное»; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается «не связан». В графе «Значение» приведены величины использованного ресурса.

Для граничных условий (строки 22, 23) в графе «Разница» показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием.

Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Так, если на ресурс наложено ограничение типа, то в графе «Разница» дается количество ресурса, на которое была превышена минимально необходимая норма (в нашей задаче такая ситуация не встречается).

Если на ресурс наложено ограничение типа, то в графе «Разница» дается количество ресурса, которое не используется при реализации оптимального решения. Так, анализ строки 20 отчета по результатам показывает, что количество использованного сырья составило 280 ед. Неизрасходованными остаются 120 ед. имеющегося сырья. Из этого следует, что запас недефицитного ресурса «Запасы сырья» можно уменьшить на 120 ед. и это никак не повлияет на оптимальное решение.

Отчет по устойчивости Отчет по устойчивости состоит из двух таблиц (рис. 1.14).

Таблица 1 содержит информацию, относящуюся к переменным.

1. Результат решения задачи.

2. Нормированная стоимость, которая показывает, насколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение (в оптимальное решение нашей задачи входят оба вида продукции, поэтому обе нормированные стоимости равны нулю).

3. Коэффициенты ЦФ.

4. Допустимое Увеличение/Уменьшение – предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение. Например, допустимое увеличение цены на продукт А равно 1000 руб./шт., а допустимое уменьшение – 1450 руб./шт. Это означает, что если цена на продукт А возрастет более чем на 1000 руб./шт., то оптимальное решение изменится.

Таблица 2 содержит информацию, относящуюся к ограничениям.

1. Величина использованных ресурсов в колонке «Результ. значение».

2. Ценность дополнительной единицы i-го ресурса (теневая цена) рассчитывается только для дефицитных ресурсов. После того как мы установили, что увеличение времени машинной обработки и единиц труда приведет к новым планам выпуска, обеспечивающим более высокую прибыль, возникает следующий вопрос – запасы какого ресурса выгодно расширять в первую очередь.

Ответ на этот вопрос и дает графа «Теневая цена». Для машинной обработки она равна примерно 143 руб./ч., а для единиц труда – 345 руб./ед., то есть каждый дополнительный час машинного времени увеличит прибыль на 143 руб., а каждая дополнительная единица труда – на 345 руб. Отсюда вывод: в первую очередь выгодно увеличивать емкость склада готовой продукции.

3. Предельные значения приращения ресурсов. В графах «Допустимое Увеличение/Уменьшение» показано, насколько можно увеличить (повысить минимально необходимое требование) ресурс или уменьшить (устранить излишек), сохранив при этом оптимальное решение. Время машинной обработки имеет смысл увеличить самое большее на 70 часов, а труд – на 34 единицы. Это приведет к новым оптимальным решениям, увеличивающим прибыль. Дальнейшее увеличение сверх указанных пределов не будет больше улучшать решение, так как уже другие ресурсы станут связывающими.

Отчет по пределам В отчете по пределам (рис. 1.15) показывается, в каких пределах могут изменяться значения x, вошедшие в оптимальное решение, при сохранении структуры оптимального решения. Кроме этого, для каждого типа продукции приводятся значения целевой функции, получаемые при подстановке в оптимальное решение значения нижнего предела выпуска изделий соответствующего типа при неизменных значениях выпуска остальных типов. Например, если при оптимальном решении х1 = 10, х2 = 30 положить х1 = 0 (нижний предел) при неизменном х2, то значение целевой функции будет равно 2500 0 + 3500 30 = 105000.

Далее приводятся верхние пределы изменения x и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.

2. ОСНОВНЫЕ ВИДЫ ЭКОНОМИЧЕСКИХ ЗАДАЧ, СВОДЯЩИХСЯ

К ЗАДАЧАМ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

Имеется n компонентов, при сочетании которых в различных пропорциях образуются различные смеси. В состав каждого компонента входят m веществ.

Пусть aij означает количество i-го вещества (i = 1,..., m), которое входит в состав единицы j-го компонента (j = 1,..., n). Заданы числа cj (j = 1,..., n), характеризующие цену единицы j-го компонента, и числа bi (i = 1,..., m), указывающие минимально необходимое содержание i-го вещества в смеси. Требуется определить состав смеси минимальной стоимости.

Пусть числа xj (j = 1,..., n) характеризуют количество j-й компоненты в смеси. Тогда задача принимает следующий вид. Требуется минимизировать функцию, характеризующую общую стоимость:

при условиях обязательного минимального содержания каждого вещества:

Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. М.: Инфра-М, 2003.

Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 1000 г. жиров, 1200 г.

белков и 1000 г. углеводов. Содержание в 1 кг каждого вида комбикорма жиров белков и углеводов, а также стоимость комбикормов приведены в табл. 2.1.

Таблица 2.1 – Содержание компонентов и стоимость комбикормов Содержание в 1 кг Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?

Стоимость смеси:

Ограничения на количество ингредиентов:

Решив задачу, например с помощью MS Excel, получаем: x1 = 0, x2 = 12, x3 = 0, F = 240. Таким образом, минимальная стоимость смеси, равная 240 у. е, будет достигнута при использовании только комбикорма В в количестве 12 кг.

2.2. Задача оптимального раскроя материала Большинство материалов, используемых в промышленности, поступает на производство в виде стандартных форм. Непосредственное использование таких материалов, как правило, невозможно. Предварительно их разделяют на заготовки необходимых размеров. Это можно сделать, используя различные способы раскроя материала. Задача оптимального раскроя состоит в том, чтобы выбрать один или несколько способов раскроя материала и определить, какое количество материала следует раскраивать, применяя каждый из выбранных способов. Впервые была сформулирована, поставлена и решена в 1939 г. российским ученым. Канторовичем Л.В на примере раскроя древесных хлыстов.

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

Выделяют два этапа решения задачи оптимального раскроя.

На первом этапе определяются рациональные способы раскроя материала.

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

Задачу оптимального раскроя материала лучше всего пояснить, разобрав конкретный пример.

Допустим, имеется два вида заготовок в виде стержней: длиной 650 мм в количестве 100 шт. и 400 мм в количестве 80 шт. Необходимо раскроить из них детали размером 125 мм и 200 мм, из которых впоследствии будут изготовлены комплекты в виде скоб. Причем, каждый комплект содержит две детали по 125 мм и одну деталь 200 мм, как показано на рис. 2.1.

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

Варианты раскроя вместе с получившимися остатками сведем в виде таблицы (табл. 2.2).

Таблица 2.2 – Варианты раскроя Вариант раскроя Количество деталей при раскрое заготовки 400 мм Для экономико-математической постановки рассматриваемой задачи введем следующие обозначения.

xij – количество заготовок i-го типа, раскроенных j-м способом (т. е. нам необходимо найти оптимальные x11, x12, x13, x14, x21, x22, x23).

аijl – количество (целое число) деталей вида l, полученных при раскрое заготовки i-го типа j-м способом. В нашем случае:

a111 = 3, a112 = 0, a121 = 2, a122 = 2, a131 = 1, a132 = 3, a141 = 0, a142 = 5, a211 = 2, a212 = 2, a221 = 2, a222 = 2, a231 = 2, a232 = 2.

Таким образом, получаем:

xij aijl – общее количество деталей вида l;

cij – количество отходов при раскрое заготовок i-го типа j-м способом.

В нашем случае:

c11 = 50, c12 = 0, c13 = 75, c14 = 25, bi – количество заготовок i-го типа. В нашем случае b1 = 100, b2 = 80.

k – коэффициент комплектности. В нашем случае k = 2.

Ограничения по количеству заготовок: каким бы способом ни раскраивалась рассматриваемая заготовка, общее количество раскроенных заготовок не должно превышать их запаса по заданному типу:

У нас заготовок размером 650 мм – 100 шт., а размером 400 мм – 80 шт.

Отсюда имеем:

Ограничения по количеству деталей в комплекте:

Наш комплект состоит из двух деталей 125 мм и одной детали 200 мм:

или, упрощая:

Ограничения на неотрицательность переменных:

Ограничения на целочисленность переменных:

Наконец, необходимо добавить ограничение, которое не позволяет одновременно всем переменным становится равным 0:

В итоге, получаем следующую систему ограничений:

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

1. ЦФ минимального расхода материала:

Решив данную задачу с помощью MS Excel, получаем:

Это означает, что минимальное количество раскроенных заготовок, равное 2, будет получено при раскрое одной заготовки 650 мм третьим способом (в соответствии с картой раскроя при этом получатся 1 деталь 200 мм и 3 детали 125 мм) и одной заготовки 400 мм вторым способом (1 деталь 200 мм и 1 деталь 125 мм). При этом всего будет получено 2 детали 200 мм и 4 детали 125 мм, т. е. условие комплектности выполняется.

2. ЦФ максимального количества комплектов:

Получаем:

Это означает, что максимальное количество комплектов, равное 420, будет получено при раскрое 99 заготовок 650 мм вторым способом, 6 заготовок 400 мм первым способом и 74 заготовок 400 мм третьим способом.

3. ЦФ минимального количества отходов Получаем:

Это означает, что минимальное количество расходов, равное 50 мм, будет получено при раскрое 5 заготовок 650 мм вторым способом и 2 заготовок 650 мм четвертым способом.

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

Суть задачи состоит в том, что командируемый выезжает из исходного пункта A, посещает (n – 1) остальных пунктов и возвращается в пункт A. Естественно, что при этом необходимо стремиться минимизировать суммарное расстояние либо продолжительность времени, либо финансовые затраты в зависимости от обстоятельств.

Постановка рассматриваемой задачи сводится к следующему: задается матрица затрат (табл. 2.3), где cij – затраты времени либо денег, либо расстояние при перемещении из i-го в j-й пункт.

Таблица 2.3 – Матрица затрат Вводим дополнительную переменную xij и условимся, что если xij =1, то командируемый воспользовался маршрутом из i-го в j-й пункт, и xij = 0, если он этим маршрутом не воспользовался.

Используя матрицу затрат, формируем ЦФ рассматриваемой задачи:

Достижение минимума ЦФ будет происходить в реальных условиях следующих ограничений:

1. Ограничение одноразового посещения города:

– условие одноразового въезда в j-й пункт посещения:

– условие одноразового выезда из j-го пункта посещения:

2. Условие односвязанности маршрута:

где ui, uj – специально подобранные целые числа.

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

3. Условие неотрицательности решения:

4. Условие целочисленности решения Так как переменные xij по смыслу задачи могут принимать только значения или 1, то условия (3) и (4) можно заменить требованием двоичности переменных.

Рассмотрим пример решения задачи коммивояжера с помощью MS Excel.

Пусть имеется 5 городов, расстояния cij между которыми приведены в табл. 2.4.

Таблица 2.4 – Пример матрицы затрат В диагональных клетках таблицы стоят значки (любое большое число, значительно превосходящее остальные числа в таблице), так как прямого маршрута между одноименными городами не существует.

Коммивояжер, выезжая из города 1, должен посетить все города, побывав в каждом из них только по одному разу и вернуться в исходный город. Необходимо определить такой маршрут объезда городов, при котором длина маршрута будет минимальной.

Используя приведенную выше математическую модель, получаем:

Исходные данные и формулы для вычисления ограничений и целевой функции в рабочей книге MS Excel приведены на рис. 2. На панели Поиск решения установить следующие параметры решения задачи.

Целевая ячейка $G$20, равная минимальному значению.

Изменяя ячейки: $B$4:$F$8;$C$10:$F$10 – сюда заносятся не только ячейки, которые будут изменяться и в которых будет занесено решение задачи (ячейки с адресами $B$4:$F$8), но и ячейки $C$10:$F$10, содержащие переменные ui, которые также являются изменяемыми.

Ограничения:

$B$21:$E$ $B$4:$F$8 = двоичное Параметры: линейная модель, неотрицательные значения.

Рисунок 2.2 – Исходные данные и формулы задачи коммивояжера в MS Excel После нажатия кнопки Выполнить на диалоговой панели Поиск решения на рабочем листе Excel появятся результаты решения задачи (рис. 2.3).

Рисунок 2.3 – Результаты решения задачи коммивояжера в MS Excel Итак, оптимальное решение таково: целевая функция F = 18, получившийся маршрут: 1 – 2 – 3 – 5 – 4 – 1.

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

Линейные транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании такого плана перевозок продукции с m складов в n пунктов назначения, который потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки сij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы kcij.

Далее, предполагается, что где ai – количество продукции, находящееся на складе i; bj – потребность потребителя j. Такая транспортная задача называется закрытой. Однако если данное равенство не выполняется, то получаем открытую транспортную задачу, которая сводится к закрытой по следующим правилам:

1. Если сумма запасов в пунктах отправления превышает сумму поданных заявок, т. е.

складах. В этом случае мы введем «фиктивного» потребителя n + 1 с потребноm n ai b j и положим транспортные расходы сi,n + 1 равными 0 для всех i.

стью 2. Если сумма поданных заявок превышает наличные запасы, т. е.

ai < b j, то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом b j ai и стоимость перевозок из фикj =1 i = тивного пункта отправления во все пункты назначения принять равным нулю:

сm + 1,j = 0.

Математическая модель транспортной задачи имеет вид:

где xij – количество продукции, поставляемое со склада i потребителю j.

Пример. Компания производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. т. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 750 тыс. т щебенки. Стоимость перевозки 1 тыс. т щебенки с каждого карьера на каждый объект приведены в табл. 6.

Таблица 2.5 – Открытая транспортная задача Задача открытая (2300 > 2200), поэтому введем фиктивного поставщика с запасом 100 и нулевыми стоимостями перевозок (табл. 2.6).

Таблица 2.6 – Закрытая транспортная задача Потребности 8x11 + 4x12 + x13 + 7x14 + 3x21 + 6x22 + 7x23 + 3x24 + 6x31 + 5x32 + 11x33 + 8x34 min;

Ответ: min = 6600.

ЗАДАНИЯ ДЛЯ ПРАКТИЧЕСКИХ РАБОТ

1. В соответствии с номером варианта составить модель ЗЛП, решить ее графически и с помощью Excel, сверить ответы. Проанализировать полученное оптимальное решение на чувствительность.

Вариант 1. Небольшая фабрика изготавливает два вида красок: для наружных (№ 1) и внутренних (№ 2) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т соответственно. Расходы А на 1 т краски № 1 – 1 т, на 1 т краски № 2 – 2 т, расходы В на 1 т краски № 1 – 2 т, на 1 т краски № 2 – 1 т. Изучение рынка сбыта показало, что суточный спрос на краску № 2 никогда не превышает спрос на краску №1 более чем на 1 т. Кроме того, установлено, что спрос на краску № 2 никогда не превышает 2 т в сутки. Прибыль от реализации одной тонны красок № 1 равна 3 тыс. у. е, а для краски № 2 – 2 тыс. у. е. Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Вариант 2. Пошивочное предприятие намечает выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 чел/день трудозатрат. На мужской костюм требуется 3,5 м шерсти, 0,5 м лавсана и 1 чел./дн. трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 чел./дн. трудозатрат. Определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 у. е., от мужского – 20 у. е. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Вариант 3. Компания производит полки для ванных комнат двух размеров – А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В – 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В – 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 у. е., а от полок типа В – 4 у. е., то сколько полок каждого типа следует выпускать в неделю?

Вариант 4. Небольшая фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 фута древесины, а для изготовления одного стола – 7 футов. На изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола – 8 часов. Каждый стул приносит 1 у. е. прибыли, а каждый стол – 3 у. е. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 футами древесины и 400 часами рабочего времени и хочет получить максимальную прибыль?

Вариант 5. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 фунта азотных, 4 фунта фосфорных и 1 фунт калийных удобрений, а в улучшенный – 2 фунта азотных, 6 фунтов фосфорных и 3 фунта калийных удобрений. Известно, что для некоторого газона требуется, по меньшей мере, 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 у. е., а улучшенный – 4 у. е. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Вариант 6. На имеющихся у фермера 400 акрах земли он планирует посеять кукурузу и сою. Сев и уборка кукурузы требует на каждый акр 200 у. е. затрат, а сои – 100 у.е. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. у. е. Каждый акр, засеянный кукурузой, приносит 40 бушелей, а каждый акр, засеянный соей, – 80 бушелей. Фермер заключил договор на продажу, по которому каждый бушель кукурузы принесет ему 3 у. е., а каждый бушель сои – 1 у. е. Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. бушелей. Фермеру хотелось бы знать, сколько акров нужно засеять каждой из этих культур, чтобы получить максимальную прибыль.

Вариант 7. На заводе используется сталь трех марок: А, В, С, запасы которых равны соответственно 10, 16 и 12 ед. Завод выпускает два вида изделий. Для изделия 1 требуется по одной единице стали всех марок. Для изделия 2 требуется единицы стали марки В, одна – марки С и не требуется сталь марки А. От реализации единицы изделия вида 1 завод получает 300 руб. прибыли, а вида 2 – 200 руб.

Составить план выпуска продукции, дающий наибольшую прибыль.

Вариант 8. Производитель безалкогольных напитков располагает двумя разливочными машинами А и В. Машина А спроектирована для пол-литровых бутылок, а машина В – для литровых. Машина А выпускает 50 пол-литровых бутылок в 1 мин, а машина В – 30 литровых бутылок в 1 мин. Каждая из машин работает ежедневно по 6 час при пятидневной рабочей неделе. Прибыль от поллитровой бутылки составляет 4 у. е., а от литровой – 10 у. е. Недельная продукция не может превосходить 250000 л; рынок принимает не более 300000 поллитровых бутылок и 200000 литровых. Сколько бутылок пол-литровых и литровых необходимо выпускать производителю, чтобы максимизировать свою прибыль при имеющихся средствах.

2. В соответствии с номером варианта решить задачу о смесях.

Вариант 1. По медицинским данным содержание ингредиентов в некоторых продуктах задается следующей таблицей, где потребность в ингредиентах дана для человека в возрасте 30–39 лет (в числителе для женщины, в знаменателе для мужчины); содержание и потребность ингредиентов (кроме калорий) даны в граммах на 1 кг продукта. Определить самый дешевый набор продуктов для мужчин и женщин при обеспечении минимальной потребности в ингредиентах.

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

Сорт вина Вариант 3. Пусть рациональное питание состоит из двух продуктов P и Q.

Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q – 4 единицы жира и 200 калорий соответственно. При этом цена 1 кг продукта Р равна 15 у. е., а 1 кг продукта Q – 25 у. е. В какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

Вариант 4. Из четырех видов основных материалов (медь, цинк, свинец, никель) составляют три вида сплавов латуни: обычный, специальный и для художественных изделий. Себестоимости единицы веса меди, цинка, свинца и никеля составляют 0,8 у. е., 0,6 у.е., 0,4 у. е. и 1,0 у. е., а доходы от единицы веса сплава, соответственно, 2 у. е., 3 у. е., 4 у. е. Сплав для художественных изделий должен содержать не менее 6% никеля, не менее 50 % меди и не более 30 % свинца; специальный – не менее 4% никеля, не менее 70 % меди, не менее 10 % цинка и не более 20 % свинца. В обычный сплав компоненты могут входить без ограничения. Производственная мощность предприятия позволяет выпускать (за определенный срок) не более 400 ед. веса обычного сплава, не более 700 ед. веса специального сплава и не более 100 ед. веса сплава для художественных изделий. Найти производственный план, обеспечивающий максимальную прибыль.

Вариант 5. Госпиталь стремится минимизировать стоимость мясного питания (говядина, свинина и баранина). Больничный рацион должен содержать, по крайней мере, 1,5 фунта жирного мяса на человека в неделю. Говядина, которая стоит 1,25 у. е. за фунт, содержит 20 % жирной и 80 % постной части.

Свинина – 1,5 у. е. за фунт и содержит 60 % жирной и 40 % постной части, баранина стоит 1,4 у. е. за фунт и состоит из 30 % жирной и 70 % постной части.

Госпиталь имеет холодильную площадь не более чем на 900 фунтов мяса. В госпитале на мясной диете 200 пациентов. Сколько фунтов каждого вида мяса необходимо покупать еженедельно для того, чтобы обеспечить необходимую калорийность рациона при минимальной стоимости?

Вариант 6. Нефтеперерабатывающий завод получает 4 полуфабриката: тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: сорт А: 2 : 3 :

5 : 2, сорт В: 3 : 1 : 2 : 1, сорт С: 2 : – : 1 : 3. Стоимость 1 тыс. л указанных сортов бензина составляет соответственно 120 у. е., 100 у. е. и 150 у. е. Определить планы смешивания компонентов для достижения максимальной стоимости всей продукции и максимального использования компонентов.

Вариант 7. Корпорация импортирует три сорта виски – ирландское, шотландское и канадское. Виски смешиваются согласно рецептам, устанавливающим максимум или минимум процентного содержания ирландского и канадского в каждой смеси.

Стоимость и запасы трех основных видов виски приведены в таблице.

Ирландское Шотландское Канадское Составить модель, позволяющую определить, сколько производить каждого типа смеси, чтобы получить максимальную прибыль.

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

3. В соответствии с номером варианта решить задачу оптимального раскроя материалов.

Вариант 1. При изготовлении парников используется материал в виде металлических стержней длиной 200 см. Этот материал разрезается на стержни длиной 120 (их должно быть не менее 80), 100 (не менее 120) и 70 (не менее 102) см. Решите задачу по критериям общего количества используемого материала и минимума общего количества отходов.

Вариант 2. На складе предприятия имеются заготовки (стальные бруски) длиной 8,1 м. Из этих заготовок необходимо изготовить 100 комплектов более коротких заготовок. При этом в один комплект входят два бруска длиной 3 м и по одному бруску длиной 2 м и 1,5 м. Необходимо раскроить исходный материал так, чтобы получить требуемое количество комплектов коротких заготовок с минимальными отходами.

Вариант 3. На производство поступила партия стержней длиной 250 и 190 см. Необходимо получить 470 заготовок длиной 120 см и 450 заготовок длиной 80 см. Отходы должны быть минимальными.

Вариант 4. Завод заключил договор на поставку комплектов отрезков стержней длиной по 18, 23 и 32 см. Причем количества отрезков разной длины в комплекте должны быть в соотношении 1 : 5 : 3. На сегодняшний день имеется 80 стержней длиной по 89 см. Как их следует разрезать, чтобы количество комплектов было максимальным?

Вариант 5. Из 50 шт. бревен длиной 6,5 м необходимо изготовить наибольшее число комплектов, в состав каждого из которых входит 2 шт. детали длиной 2 м и 3 шт. детали длиной 1,25 м.

Вариант 6. В леспромхозе производится раскряжевка хлыстов на сортименты. Требуется получить сортименты трех видов – длиной 6, 2,2 и 1,5 м. Длина среднего хлыста 31 м, средний диаметр 0,3 м. План поставки сортиментов, соответственно, 32,4 тыс. м3, 86,3 тыс. м3 и 40,3 тыс. м3. Определить оптимальный с точки зрения отходов план раскроя без учета толщины пропила.

Вариант 7. Произвести распил тысячи 5-метровых бревен на брусья размерами 1,5 м; 2,4 м и 3,2 м в отношении 2:3:5 так, чтобы минимизировать общую величину отходов.

Вариант 8. На строительный объект поступает партия в 1000 листов стекла размером 1,5 1,3 м. Для остекления здания необходимы стекла размером в 1 0,5 м, 1 0,8 м, 1,5 0,5 м в отношении 2:3:5:8. Составить план раскроя партии стекол, при котором будет получено максимальное количество комплектов.

4. В соответствии с номером варианта решить задачу коммивояжера.

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

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Розова, В. Н. Методы оптимизации. Курс лекций [Электронный ресурс] :

учебное пособие / В. Н. Розова, И. С. Максимова ; Университетская библиотека онлайн (ЭБС). – Москва : Российский университет дружбы народов, 2010. – 111 с. – Режим доступа: http://www.biblioclub.ru/book/115762/.

Дополнительная учебная, учебно-методическая литература 1. Балдин, К. В. Математическое программирование [Электронный ресурс] : учебник для студентов вузов, обучающихся по направлению подготовки «Экономика» и экономическим специальностям / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев ; под ред. К. В. Балдина ; Университетская библиотека онлайн (ЭБС). – 2-е изд. – Москва : Дашков и К, 2012. – 219 с. – Режим доступа:

http://www.biblioclub.ru/book/112201/.

2. Волошин, Г. Я. Методы оптимизации в экономике [Текст] : учеб. пособие для студ. вузов / Г. Я. Волошин ; Моск. гос. ун-т леса. – Москва : Дело и Сервис, 2004. – 320 с.

3. Курзина, В. М. Методы оптимизации [Текст] : учеб. пособие для студ.

всех спец. / В. М. Курзина, А. В. Трегуб ; М-во образования Рос. Федерации, Моск. гос. ун-т леса. – Москва : МГУЛ, 2003. – 48 с.

4. Лунгу, К. Н. Линейное программирование. Руководство к решению задач [Электронный ресурс] : учеб. пособие для студ. вузов, обучающихся по экон. и техн. спец. / К. Н. Лунгу ; Университетская библиотека онлайн (ЭБС). – Изд.

2-е, испр. и доп. – Москва : Физматлит, 2009. – 132 с. – Режим доступа:

http://www.biblioclub.ru/book/82255/.

5. Мастяева, И. Н. Методы оптимизации. Линейные и нелинейные методы и модели в экономике [Электронный ресурс] : учеб. пособие / И. Н. Мастяева, О. Н. Семенихина ; Университетская библиотека онлайн (ЭБС). – Москва : Евразийский открытый институт, 2011. – 422 с. – Режим доступа:

http://www.biblioclub.ru/book/90388/.

6. Методы оптимизации. Самостоятельная работа студентов [Текст] : метод. указ. для подготовки дипломированного специалиста по направлению 660300 «Агроинженерия», спец. 110301 «Механизация сельского хозяйства», 110302 «Электрификация и автоматизация сельского хозяйства» / сост.

Н. Э. Готман. – Сыктывкар : СЛИ, 2007. – 32 с.

7. Пантелеев, А. В. Методы оптимизации. Практический курс [Электронный ресурс] : учеб. пособие для студ. вузов, обучающихся по направлению подгот. «Прикладная математика» спец. «Прикладная математика» / А. В. Пантелеев, Т. А. Летова ; Университетская библиотека онлайн (ЭБС). – Москва : Логос, 2011. – 424 с. – (Новая университетская библиотека). – Режим доступа:

http://www.biblioclub.ru/book/84995/.

8. Струченков, В. И. Методы оптимизации в прикладных задачах [Электронный ресурс] : [курс лекций] / В. И. Струченков ; Университетская библиотека онлайн (ЭБС). – Москва : Солон-Пресс, 2009. – 315 с. – (Библиотека профессионала). – Режим доступа: http://www.biblioclub.ru/book/117856/.

9. Черноруцкий, И. Г. Методы оптимизации в теории управления [Текст] :

учеб. пособие для студ. вузов, обучающихся по направлениям подготовки бакалавров и магистров «Системный анализ и управление» и «Информатика и вычислительная техника» / И. Г. Черноруцкий. – Санкт-Петербург : Питер, 2004. – 256 с. – (Учебное пособие).

1. Приоритетные направления развития науки и технологий и перспективные изобретения [Текст] : обзорно-аналитическое издание. – Москва : ОАО ИНИЦ «Патент». – Выходит дважды в год.

2. Теория и системы управления [Текст]. Известия РАН. – Выходит раз в два месяца.