Министерство образования и науки Украины

Севастопольский национальный технический университет

МЕТОДИЧЕСКИЕ УКАЗАНИЯ К ВЫПОЛНЕНИЮ

КОНТРОЛЬНЫХ И РАСЧЁТНО-ГРАФИЧЕСКИХ ЗАДАНИЙ

ПО ДИСЦИПЛИНЕ “МЕТОДЫ ИССЛЕДОВАНИЯ

ОПЕРАЦИЙ’’ "Информационные управляющие системы и технологии" для студентов всех форм обучения по направлению 0804 – “Компьютерные науки” Часть 1. Задачи линейного программирования Севастополь Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) УДК 004. Методические указания к выполнению контрольных и расчётнографических заданий по дисциплине “Методы исследования операций’’ для студентов всех форм обучения по направлению 0804 – “Компьютерные науки”. Часть 1. Задачи линейного программирования / Разраб. Л.П. Старобинская, В.Ю. Карлусов. - Севастополь:

Изд-во СевНТУ, 2006. –52 с.

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

Методические указания рассмотрены и утверждены на заседании кафедры Информационных систем, протокол № 02 от 15 сентября 2006 г.

Допущено учебно-методическим центром СевНТУ в качестве методических указаний.

Рецензент Апраксин Ю.К., доктор техн. наук, процессор. каф.

Кибернетики и вычислительной техники.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

СОДЕРЖАНИЕ

Введение 1. Математическая постановка задачи линейного программирования…. … 2. Геометрическая интерпретация задачи линейного программирования … 3. Теоремы линейного программирования………………………………... … 4. Экономическая интерпретация задачи линейного программирования 5. Методы решения задач линейного программирования……………….. … 5.1. Графический метод…………………………………………………….. … 5.1.1. Описание алгоритма решения задачи………………………………. … 5.1.2. Пример решения задачи линейного программирования графическим методом……………………………………………………………….. … 5.2. Табличный симплекс метод…………………………………………… … 5.2.1. Описание алгоритма решения задачи………………………………. … 5.2.2. Пример решения задачи линейного программирования простым симплекс методом…………………………………………………………... … 5.3. Метод искусственного базиса…………………………………………. … 5.3.1. Построение математической модели задачи……………………….. … 5.3.2. Алгоритм решения задачи…………………………………………… … 5.3.3. Пример решения задачи методом искусственного базиса………… … 5.4. Модифицированный симплекс-метод………………………………… … 5.4.1.Описание алгоритма решения задачи……………………………….. … 5.4.2. Пример решения задачи линейного программирования модифицированным методом………………………………………………………. … 5.5. Двойственный симплекс – метод……………………………………... … 5.5.1. Содержательная постановка задачи………………………………… … 5.5.2. Построение математической модели задачи……………………….. … 5.5.3. Алгоритм решения задачи…………………………………………… … 5.5.4. Пример решения задачи двойственным симплекс – методом…….. … 6. Исследование модели на чувствительность задачи линейного программирвания модифицированным симплекс-методом…………………. … 6.1. Теоретические положения…………………………………………...... … 6.2. Пример анализа на чувствительность………………………………… … Библиографический список………………………………………………... … Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

ВВЕДЕНИЕ

Анализ опыта преподавания дисциплины “Методы исследования операций” позволил обнаружить существенные моменты, на которые следует обратить внимание в ходе выполнения контрольных работ, курсового проектирования и подготовки к экзаменам.

1. Отмечается слабое представление учащимися связей теоретических моделей исследования операций с практическими (прикладными) задачами.

2. Замечены случаи недопонимания отдельными студентами тонкостей тех или иных методов оптимизации.

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

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

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

Авторы считают необходимым выразить благодарность студентам М.Р.

Валентюк, М.Г. Нестеровой, Н.А. Погребной 3-го курса 2004/2005 гг., которые оказали ощутимую помощь в сборе, художественной обработке и оформлении материалов настоящих методических указаний.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

1. МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Задачу линейного программирования (ЛП) можно сформулировать так.

В данном случае все условия имеют вид неравенств. Иногда они могут быть смешанными, т.е. неравенства и равенства:

Если все ограничения задачи ЛП заданы в виде равенств:

то данная форма называется канонической.

В матричной форме задачу ЛП записывают следующим образом.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) где А – матрица ограничений размером (m*n), b - вектор – столбец свободных членов (m*1), x- вектор переменных (n*1), сТ = [с1, с2,…, сn] – вектор – строка коэффициентов целевой функции (ЦФ).

Решение х0 будет оптимальным, если для него выполняется условие Множество всех векторов х, удовлетворяющих ограничениям (1.2) и (1.3), представляет собой выпуклый многогранник R(x). В этом случае говорят, что R(x) является выпуклым многогранным множеством.

Отметим, что поскольку min f(x) эквивалентен max [-f(x)], то задачу минимизации в ЛП всегда можно свести к эквивалентной задаче максимизации.

2. ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

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

Рассмотрим следующий пример.

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

Пусть f ( x1, x 2 ) 1000 z1. График уравнения 2 x1 5 x 2 1000 представляет собой прямую с отрезками на осях х1 = 500 единиц, а х2 =200 единиц.

Прямая z2 параллельна прямой z1, но расположена выше ее. Перемещая прямую, параллельную Z1 и Z2 вверх, приходим к такому положению zmax, когда прямая и множество R будут иметь только одну общую точку А.

Очевидно, что точка А (х1 = 200; х2 =300) – оптимальное решение, так как оно лежит на прямой с максимально возможным значением zmax. Заметим, что эта точка оказалась крайней точкой множества R.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) В векторной форме записи ограничения задачи ЛП записывают так:

Векторы А1, А2, Аn называются требованиями задачи. Рассмотрим допустимое множество R в пространстве данных векторов. Так как в формуле (2.1) x i 0(i 1,2,..., n), то все положительные комбинации векторов А1, А2, Аn образуют конус. Поэтому вопрос о существовании допустимого решения равнозначен вопросу о принадлежности вектора b к этому конусу.

Поэтому справедливо следующее утверждение. Если задача ЛП содержит n переменных и m ограничений (n>m), записанных в форме неравенств, не считая неотрицательности xj>=0, то в оптимальное решение входит не более чем m ненулевых компонент вектора х.

3. ТЕОРЕМЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Теорема 1. Если ЦФ достигает минимального или максимального значения на множестве допустимых решений R, то она достигает этого значения в крайней точке множества R. Если она достигает минимального или максиCreate PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) мального значения более чем в одной точке, то она достигает этого же значения в любой их выпуклой комбинации.

Теорема 2. Пусть существуют системы векторов A1, A2,..., Ak, размерностью m, причем m, таких, что выполняется: A1 x1 A2 x 2... Ak x k A0, то вектор с координатами x x1, x 2,..., x k, 0, 0,...,0, [где количество нулей определяется как (m-k)], есть крайняя точка.

Теорема 3. Если Х0 – крайняя точка множества R, то координаты вектора являются допустимым базисным решением.

Следствия: 1) Оптимальное решение может находиться только в крайней точке множества допустимых значений. 2) Для того чтобы найти оптимальное решение, необходимо перебрать все крайние точки.

4. ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Целью работы коммерческой фирмы является получение прибыли.

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

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

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

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

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) В общем виде постановка задачи математического программирования состоит в определении наибольшего или наименьшего значения целевой функции f (х1, х2,..., хn) при условиях gi (х1, х2,..., хn) bi; (i =1,2,…m), где f и gi; – линейные функции, а bi – некоторые действительные числа.

1. Задача о планировании выпуска продукции пошивочного предприятия.

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

2. Задача о планировании выпуска продукции фармацевтической фирмы.

Фармацевтическая фирма производит витамины двух видов: для детей и для взрослых. Продукция обоих видов поступает в продажу. Для их производства кроме стандартного комплекса витаминов, микроэлементов и аминокислот используют новые биологические добавки A, B, С и D. Расход этих добавок в граммах на килограмм соответствующих витаминов и ограничения в применении добавок A, B, С и D приведены в таблице 4. Таблица 4.1 – Показатели потребителя пищевых добавок Добавки Расход добавок (Г/кГ) Ограничения в применении добавок (г) Оптовые цены 1 кг витаминов, изготовленных в виде капсул: для детей Требуется найти такое количество витаминов каждого вида, которое должна производить фирма, чтобы доход от реализации продукции был максимальным.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

5. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

5.1.1. Описание алгоритма решения задачи Данный метод применяется для задач, где общее число переменных n=2 или задача может быть сведена к соответствующей задаче с числом независимых переменных k=2. Пусть ЛП-задача имеет вид (1.1) – (1.3).

Алгоритм метода включает следующие шаги.

1. На плоскости строится допустимое множество решений, определяемое (1.2) и (1.3). Эта множество называется областью допустимых стратегий 2. По коэффициентам целевой функции (ЦФ) с1 и с2 строится вектор нормали, который указывает направление возрастания f ( x1, x 2 ). Нормаль всеF F Эта прямая перпендикулярна линии пересечения плоскости f(x1,x2) с координатной плоскостью, а также проекциям всех линий равного уровня, принадлежащих плоскости ЦФ f(x1,x2).

3. К нормали N восстанавливается перпендикуляр, который перемещается по ней, пока не достигнет крайней точки ОДС. Направление перемещения определяется видом оптимизации. Если задача решается на min, то перемещение осуществляется в направлении от точки С к точке О, а если – на При этом возможен один из следующих случаев:

а) если область ограничений не замкнута в направлении оптимизации, то решений не будет;

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

в) если область ограничений образована несовместными неравенствами, то решений не будет;

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

д) существует решение в единственной крайней точке.

Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) 5.1.2. Пример решения задачи линейного программирования графическим методом Решим задачу о планировании выпуска продукции пошивочному предприятию (задача 1 из параграфа 4).

Построим математической модели задачи по содержанию. Введем следующие обозначения: х1 - число женских костюмов; x2 - число мужских костюмов.

Прибыль от реализации женских костюмов составляет 10х1, а от реализации мужских 20х2, т.е. необходимо максимизировать целевую функцию Первое ограничение по труду х1 + х2 150. Прямая х1 + х2 = 150 проходит через точки (150, 0) и (0, 150).

проходит через точки (120, 0) и (0, 480).

Четвертое ограничение по количеству мужских костюмов x2 60.

Решением этого неравенства является полуплоскость, лежащая выше прямой x2 = 60. Область допустимых решений должна быть ограничена прямыми, соответствующими каждому из заданных ограничений (рассмотренных выше). На рисунке 5.1 заштрихована область допустимых решений.

Для определения направления движения к оптимуму построим точку С (с1;с2), координаты которой являются частными производными целевой Чтобы построить вектор нормали, нужно соединить точку (10;20) с началом координат. Если задача решается на min, то перемещение осуществляется в направлении вектора нормали к точке (0;0), а если – на max, то наоборот.

В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. В крайней, угловой точке достигается Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com) максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума: х1 + 4х2 = 350 и х1 + Отсюда легко записать решение исходной ЗЛП: max f(x) = 2160 и достигается при x1=66 и x2=84.

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