МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Экономика и организация энергетики» ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Лабораторный практикум Часть 1 Минск БНТУ 2012 МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ Белорусский национальный технический университет Кафедра «Экономика и организация энергетики» ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Лабораторный практикум для студентов специальности 1-27 01 01 «Экономика и организация производства» В 2 частях Часть 1 Минск БНТУ 2012 УДК 330.4(076.5) ББК 65в631я7 Э40 С о с т а в и т е л ь: А. В. Куприк Р е ц е н з е н т ы: Т. Ф. Манцерова, А. И. Лимонов Э40 Экономико-математические методы и модели : лабораторный практикум для студентов специальности 1-27 01 01 «Экономика и организация производства» : в 2 ч. / сост. А. В. Куприк. – Минск : БНТУ, 2012. – Ч. 1. – 33 с. ISBN 978-985-525-784-5 (Ч.1). В лабораторном практикуме приведены рекомендации по выполнению лабо- раторных работ по дисциплине «Экономико-математические методы и модели» для студентов специальности 1-27 01 01 «Экономика и организация производства». Лабораторные работы включают в себя задания, решение которых позволит закрепить теоретический материал и получить навыки соответствующих расчетов и анализа. УДК 330.4(076.5) ББК 65в631я7 ISBN 978-985-525-784-5 (Ч.1) Белорусский национальный ISBN 978-985-525-958-0 технический университет, 2012 3 Лабораторная работа № 1 ПОСТРОЕНИЕ И АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Цель работы: научиться определять оптимальный план произ- водства (приобретения) продукции с учетом ограниченного обеспе- чения ресурсами различного вида; освоить методику и технологию поиска оптимального решения задач линейного программирования (ЗЛП) с помощью ЭВМ; приобрести практический опыт проведения анализа оптимального решения ЗЛП на чувствительность. Теоретические основы Задача линейного программирования в общем виде записывается следующим образом: требуется найти максимальное (минимальное) значение целевой функции 1 max (min) n j j j F c x (1) при следующих условиях: 1 , 1, , n ij j i j a x b i k k m , (2) 1 , 1, n ij j i j a x b i k m , (3) 0, 1, ,jx j l l n , (4) где xj – неизвестные величины; aij, bi, cj – заданные действительные числа. 4 (1) – целевая функция; (2), (3) – основные ограничения задачи; (4) – неосновные ограничения. Для решения задач ЛП могут быть использованы графический метод, симплекс-метод, метод искусственного базиса, модифици- рованный симплекс-метод и двойственный симплекс-метод. Любой ЗЛП (1)–(4) можно поставить в соответствие двойствен- ную задачу следующего вида: 1 min (max) m i i i f b y , (5) 1 , 1, m ij i j i a у с j k , (6) 1 , 1, m ij i j i a y c j k n , (7) 0, 1, .iy i s (8) Заметим, что yi имеет произвольный знак для 1,i s m . Поскольку задача, двойственная по отношению к двойственной, представляет собой исходную задачу, говорят, что задачи (1)–(4) и (5)–(8) образуют пару взаимодвойственных задач. Основные задачи анализа на чувствительность: 1. Анализ изменения запасов ресурсов позволяет ответить на два вопроса: а) на сколько можно увеличить запас некоторого ресурса с целью улучшения полученного оптимального значения целевой функции? б) на сколько можно уменьшить запас некоторого ресурса с со- хранением полученного ранее оптимального значения целевой функции? Если ресурс израсходован полностью, его относят к разряду де- фицитных. Ресурс в избытке называют недефицитным. Объем не- дефицитного ресурса можно уменьшить на величину избытка без изменения значения целевой функции. Объем дефицитного ресурса не следует увеличивать сверх того предела, когда соответствующее ему ограничение становится избыточным. 5 2. Определение наиболее выгодного ресурса, т. е. ресурса, кото- рому следует отдавать предпочтение при инвестировании дополни- тельных средств. Для этого вводится характеристика ценности еди- ницы ресурса: max приращение целевой функции , max допустимый прирост -го ресурса iy i где yi – теневая цена ресурса (стоимость единицы ресурса). Значение теневой цены ресурсов – это решение задачи, двой- ственной к данной. Теневая цена ресурса показывает, на сколько изменится значение целевой функции (ЦФ) при изменении запаса ресурса на единицу. Теневая цена позволяет определить статус ресурса. У недефи- цитного ресурса теневая цена равна нулю; положительное значение теневой цены говорит о дефицитности данного ресурса. Теневая цена также предоставляет возможность оценить целесо- образность введения в оптимальный план продукцию нового вида. Если выполняется условие 1 , m ij i j i a y c (9) то введение в план j-го вида продукции выгодно. 3. Определение пределов изменения коэффициентов целевой функции позволяет ответить на два вопроса: а) каков диапазон изменения того или иного коэффициента ЦФ, при котором не происходит изменение оптимального решения? б) на сколько следует изменить тот или иной коэффициент ЦФ, чтобы сделать дефицитный ресурс недефицитным и наоборот? Задания Вариант 1. Для изготовления обуви четырех моделей на фабри- ке используют два сорта кожи. Ресурсы рабочей силы и материала и затраты труда и материала на изготовление каждой пары обуви 6 приведены в таблице. Прибыль от реализации первой модели обуви составляет 2 ден. ед., второй – 40 ден. ед., третьей – 10 ден. ед., чет- вертой – 15 ден. ед. Составить план выпуска обуви по ассортименту, максимизиру- ющий прибыль. Ресурс Затраты ресурсов на одну пару обуви по моделям Запас ресурса № 1 № 2 № 3 № 4 Рабочее время, чел-ч 1 2 2 1 1000 Кожа 1-го сорта 2 1 0 0 500 Кожа 2-го сорта 0 1 4 1 1200 Вариант 2. Мебельная фабрика может выпускать стулья двух типов стоимостью 8 и 12 ден. ед. Удельный расход материальных и трудовых ресурсов, необходимых для изготовления каждого типа стула, приведен в таблице. Запас досок составляет 490 м, ткани – 65 м2, времени – 325 чел-ч. Необходимо составить оптимальный план производства стульев, максимизирующий их суммарную стоимость. Стул Расход досок, м ткани, м2 времени, чел-ч 1 2 0,50 2,0 2 4 0,25 2,5 Вариант 3. В наличии имеется 10 000 кг реагента А, 18 000 кг реагента В, 12 000 кг реагента С. Общее время работы оборудова- ния 30 000 ч. На изготовление 1 кг краски типа I расходуется 1 кг реагента А, ¾ кг реагента В и 1½ кг реагента С, а также 1 8 ч времени работы обору- дования. 7 На изготовление 1 кг краски типа II расходуется 1 кг реагента А, ½ кг реагента В и ¾ кг реагента С, а также 1 4 ч времени работы оборудования. На изготовление 1 кг краски типа III расходуется 1¼ кг реагента А, 1¼ кг реагента В и 1½ кг реагента С, а также 1 6 ч времени рабо- ты оборудования. Чистая прибыль от продажи 1 кг краски типов I, II, III составляет 0,8; 0,65; 1,25 у. е. соответственно. Необходимо определить, сколько кг краски каждого из трех ти- пов требуется произвести, чтобы получить максимальную прибыль. Вариант 4. Имеются два проекта на строительство жилых до- мов. Запас стройматериалов и их расход на один дом по каждому проекту приведены в таблице. Полезная площадь дома по первому проекту составляет 60 м2, по второму – 50 м2. Определить, сколько домов по первому и второму проекту сле- дует построить, чтобы полезная площадь была наибольшей. Стройматериалы Расход стройматериалов на один дом, м 3 Запас стройматериалов, м 3 I проект II проект Кирпич силикатный 7 3 1365 Кирпич красный 6 3 1245 Пиломатериалы 1 2 650 Вариант 5. Цех выпускает трансформаторы двух видов. Для их изготовления используют железо и проволоку. Общий запас железа – 3 т, проволоки – 18 т. На один трансформатор первого вида расхо- дуется 5 кг железа и 3 кг проволоки, а на один трансформатор вто- рого вида расходуется 2 кг железа и 3 кг проволоки. За каждый реа- лизованный трансформатор первого вида завод получает прибыль 3 ден. ед., второго – 4 ден. ед. Составить план выпуска трансформаторов, обеспечивающий за- воду максимальную прибыль. 8 Вариант 6. Предприятие выпускает три вида изделий: А, Б, В, – для изготовления которых используется фрезерное, токарное, сва- рочное и шлифовальное оборудование. Удельные затраты и общий фонд рабочего времени приведены в таблице. Прибыль от реализа- ции продукции типа А составляет 10 ден. ед., типа Б – 14 ден. ед., типа В – 12 ден. ед. Требуется так спланировать объемы выпуска изделий, чтобы прибыль от их реализации была максимальной. Тип оборудования Затраты времени на изделие типа Фонд времени А Б В Фрезерное 2 4 5 120 Токарное 1 8 6 280 Сварочное 7 4 5 240 Шлифовальное 4 6 10 360 Вариант 7. Чулочно-носочная фирма производит и продает два вида товаров: мужские носки и женские чулки. Фирма получает прибыль в размере 10 ден. ед. от производства и продажи одной па- ры чулок и в размере 4 ден. ед. от производства и продажи одной пары носков. Производство каждого изделия осуществляется на трех участках. Затраты труда (в часах) на производство одной пары для каждого участка указаны в следующей таблице. Участок про- изводства Чулки Носки 1 0,02 0,01 2 0,03 0,01 3 0,03 0,02 Руководство рассчитало, что в следующем месяце фирма еже- дневно будет располагать следующими ресурсами рабочего време- ни на каждом из участков: 60 ч на участке 1; 70 ч на участке 2; 100 ч на участке 3. Какое количество продукции каждого вида следует ежедневно производить предприятию, чтобы получить максимальную при- быль? 9 Вариант 8. Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство произво- дит четыре вида продукции: П1, П2, П3, П4. Организация производ- ства характеризуется приведенной таблицей. Составить план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. Продукция Затраты на 1 ед. продукции Доход от 1 ед. продукции Площадь Труд Тяга П1 2 2 2 1 П2 3 1 3 4 П3 4 2 1 3 П4 5 4 1 5 Вариант 9. Завод выпускает продукцию четырех типов. От реа- лизации 1 ед. каждой продукции завод получает прибыль соответ- ственно 2, 1, 3, 5 ден. ед. На изготовление продукции расходуются три вида ресурсов: энергия, материалы, труд. Данные о технологи- ческом процессе приведены в таблице. Составить план выпуска продукции, обеспечивающий хозяйству максимальную прибыль. Ресурс Затраты на 1 ед. продукции Запас ресурсов, ед. I II III IV Энергия 2 3 1 2 30 Материалы 4 2 1 2 40 Труд 1 2 3 1 25 Вариант 10. Для приобретения оборудования по сортировке зерна фермер выделяет 20 ден. ед. Оборудование должно быть раз- мещено на площади, не превышающей 72 м2. Фермер может зака- зать оборудование двух видов: менее мощные машины типа А сто- имостью 2 ден. ед., требующие производственную площадь 12 м2 (с учетом проходов) и обеспечивающие производительность за сме- ну 6 т зерна, и более мощные машины типа В стоимостью 5 ден. ед., 10 занимающие площадь 6 м2 и обеспечивающие производительность за смену 8 т сортового зерна. Машин типа В можно заказать не бо- лее 3 единиц. Определить оптимальный план приобретения оборудования, обеспечивающий максимальную производительность участка. Вариант 11. Имеющийся фонд материалов Мi нужно распреде- лить между изготовителями продукции Пj так, чтобы получить мак- симальную прибыль от реализации всей продукции, произведенной из имеющихся материалов. Нормы расхода на единицу продукции и запас материалов приведены в таблице. Прибыль, получаемая от реализации единицы готовой продукции, П1 составляет 5 ден. ед., П2 – 7 ден. ед., П3 – 6 ден. ед., П4 – 9 ден. ед., П5 – 8 ден. ед. Материал Фонд материалов Продукция П1 П2 П3 П4 П5 М1 50 000 0,7 0,9 1,5 2,3 1,8 М2 28 000 1,4 0,3 0,7 2,5 2,0 М3 40 000 0,5 2,1 1,8 0,7 2,0 Вариант 12. Предприятие выпускает продукцию четырех типов. При производстве продукции расходуются различные ресурсы. Их запасы и удельные затраты на 1 единицу продукции приведены в таб- лице. Цена единицы продукции первого типа составляет 65 ден. ед., второго типа – 70 ден. ед., третьего – 60 ден. ед., четвертого – 120 ден. ед. Найти оптимальный план выпуска продукции, максимизирую- щий выручку предприятия от реализованной продукции. Ресурсы Запас ресурса Нормы расхода на 1 ед. продукции П1 П2 П3 П4 Трудовые, чел-ч 4800 4 2 2 8 Полуфабрикаты, кг 2400 2 10 6 0 Станочное оборудование, станко-ч 1500 1 0 2 1 11 Содержание отчета 1. Титульный лист. 2. Цель работы. 3. Условие задачи. 4. Математическая модель задачи с условными обозначениями и пояснениями. 5. Таблица 1. 6. Итоговая симплекс-таблица. 7. Математическая модель задачи, двойственной к исходной, и ее решение. 8. Определение максимального изменения запаса каждого ресурса. 9. Определение пределов изменения каждого коэффициента це- левой функции. 10. С помощью двойственных оценок определить верхнюю и нижнюю границы изменения запаса каждого ресурса (найти интервалы устойчивости оценок по отношению к изменению ресурсов). 11. Ответы на контрольные вопросы. Таблица 1 Анализ решения задачи Изделия ЦФ F(X) Х1 Х2 … Xn Оптимальный объем производства Ресурс Наличие Расход ресурсов на производство изделий Общий расход Оста- ток Статус ресурса Теневая цена Х1 Х2 … Xn b1 b2 ... bm 12 Контрольные вопросы 1. Основные вопросы анализа оптимального решения ЗЛП на чувствительность. 2. Анализ оптимального решения ЗЛП на чувствительность с помощью итоговой симплекс-таблицы: – статус ресурсов; – теневая цена; – изменение запасов ресурсов и цены на продукцию; – целесообразность выпуска (приобретения) нового вида про- дукции. 13 Лабораторная работа № 2 ТРАНСПОРТНЫЕ МОДЕЛИ Цель работы: научиться находить оптимальное решение задач транспортного типа в усложненной постановке. Теоретические основы В общем виде транспортную задачу (ТЗ) можно записать следу- ющим образом: имеется m поставщиков и n потребителей однород- ного груза. Запасы i-го поставщика обозначим ai, спрос j-го потре- бителя – bj. Если обозначить стоимость перевозки единицы груза cij, а количество перевозимого груза от i-го поставщика j-му потребите- лю xij, то математическая модель задачи будет иметь вид: 1) суммарные запасы на перевозку должны быть минимальные: 1 1 min; m n ij ij i j c x 2) объем поставок i-го поставщика должен быть равен его запасу: 1 , 1, , n ij i j x a i m 3) объем поставок j-му потребителю должен быть равен его спросу: 1 , 1, m ij j i x b i n , 0, 1, , 1,ijx i m j n . Если суммарный объем отправляемых грузов равен потребности в этих грузах, то транспортная задача называется закрытой (сбалан- сированной): 1 1 m n i j i j a b ; иначе – открытой. 14 Если имеет место открытая ТЗ, ее нужно свести к закрытой фор- ме следующим образом: 1) если спрос > предложения, то вводят фиктивного поставщика с недостающим объемом спроса. Тарифы cij, связывающие фиктивные пункты с реальными, равны штрафам за недопоставку продукции; 2) если спрос < предложения, вводят фиктивного потребителя с недостающим объемом потребления. Элементы матрицы cij, связы- вающие фиктивные пункты с реальными, равны стоимости хране- ния единицы невывезенного груза. Если указанные в пп. 1 и 2 затраты неизвестны, то соответству- ющие элементы cij = 0. Транспортная задача решается в два этапа. Сначала необходимо найти исходный опорный план, а затем производить последова- тельно его улучшение до получения оптимального плана. На пер- вом этапе для распределения ресурсов можно использовать правило «северо-западного угла» (здесь не учитываются тарифы и план да- лек от оптимального) или правило «минимального элемента», при котором необходимо осуществлять максимальные поставки ресур- сов в клетки с минимальными тарифами. На втором этапе можно применить распределительный метод или метод потенциалов. ТЗ присущи следующие особенности: 1) распределению подлежит однородный груз; 2) основные ограничения выражаются только уравнениями; 3) во всех уравнениях коэффициенты при неизвестных равны единице; 4) каждая переменная встречается только в двух уравнениях си- стемы ограничений. При решении практических задач приходится учитывать ряд до- полнительных ограничений: 1) отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены из-за отсутствия необходи- мых условий хранения, чрезмерной загрузки транспортных комму- никаций и т. д. Это достигается путем искусственного завышения тарифов в тех ячейках транспортной таблицы, перевозки через ко- торые следует запретить; 2) на предприятии необходимо оценить суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при планировании размещения производственных 15 объектов. С этой точки зрения может оказаться экономически более выгодным поставлять сырье из более отдаленных регионов, но по меньшей его себестоимости. В таких задачах в качестве критерия оптимальности принимают суммарные затраты на транспортировку и производство продукции; 3) ряд транспортных маршрутов, по которым необходимо доста- вить груз, имеет ограничения по пропускной способности (ограни- чение «не более чем»). Если по маршруту АiВj можно доставить ≤ q единиц груза, столбец Bj разбивается на два столбца: Bj и Bj . В первом спрос равен q, во втором – (bj – q). Несмотря на то что транспортные затраты в обоих столбцах одинаковы и равны исход- ным, ячейка AiBj блокируется (в ней ставится завышенный тариф). Затем задача решается обычным способом; 4) поставки по определенным маршрутам обязательны и должны войти в план поставок независимо от того, выгодно это или нет (ограничение «не менее чем»). В этом случае уменьшают запас гру- за и спрос у соответствующих поставщиков и потребителей на ве- личину обязательных поставок и решают задачу относительно тех поставок, которые необязательны. После чего задачу корректируют с учетом обязательных поставок; 5) необходимо максимизировать целевую функцию в ТЗ (напри- мер, задача об оптимальном распределении оборудования). Для это- го надо изменить знак в тарифах на противоположный. В ответе отрицательный знак игнорируется. Задания Вариант 1. На четырех ткацких станках с объемом рабочего времени 200, 300, 250 и 400 станко-ч за 1 час можно изготовить со- ответственно 260, 200, 340 и 500 м ткани трех артикулов I, II, III. Составить оптимальную программу загрузки станков, если прибыль (в ден. ед.) от реализации 1 м ткани i-го артикула при ее изготовле- нии на j-м станке характеризуется элементами матрицы 2,5 2,2 2,8 1,6 1,0 1,9 1,2 , 0,8 1,0 0,6 0,9 16 а суммарная потребность в ткани каждого из артикулов равна 200, 100 и 150 тыс. м. Необходимо учитывать, что ткань I артикула не может производиться на третьем станке. Вариант 2. Нефтеперерабатывающие заводы З1, З2, З3 и З4 еже- дневно производят бензин в объемах 30, 80, 70 и 40 млн л соответ- ственно, который направляется в бензохранилища БХ1, БХ2, БХ3 и БХ4. Вместимость бензохранилищ составляет соответственно 40, 60, 50 и 80 млн л. Все бензохранилища связаны с заводами трубопро- водами, по которым и перекачивается бензин. Стоимость перекачки 1 млн л бензина с заводов в бензохранилища приведена в таблице. Требуется составить план перекачки бензина с заводов в бензо- хранилища, обеспечивающий минимальные затраты. Завод Бензохранилище БХ1 БХ2 БХ3 БХ4 З1 6 5 9 7 З2 10 11 8 3 З3 12 8 7 9 З4 10 7 12 3 Как изменится план перекачки бензина, если в рассматриваемый промежуток времени трубопровод от завода З1 к бензохранилищу БХ4 перекрыт для профилактического ремонта, по трубопроводу от завода З3 к бензохранилищу БХ2 в данный момент нет возможности пропустить более 45 млн л в день, кроме того, емкости бензохрани- лища БХ1 должны быть заполнены полностью? Вариант 3. Пять автопарков (АП) города с ежемесячной потреб- ностью в бензине в 40, 30, 80, 60 и 50 т соответственно снабжаются четырьмя бензохранилищами вместимостью соответственно 55, 70, 35 и 100 т. Доставка горючего из бензохранилищ осуществляется автотранспортом. Средние транспортные издержки в расчете на 1 т приведены в таблице. Требуется составить план перевозки горючего, обеспечивающий минимальные суммарные транспортные затраты. 17 Бензохранилище Автопарк АП1 АП2 АП3 АП4 АП5 БХ1 6 5 9 7 4 БХ2 10 11 8 3 2 БХ3 12 8 7 9 6 БХ4 10 7 12 3 5 Как изменится план поставки горючего, если учесть следующие условия: из бензохранилища БХ2 весь запас бензина поставляется в автопарк АП3; потребность автопарка АП1 удовлетворяется полно- стью; в бензохранилище БХ3 остается резервный запас в 20 т бензи- на для чрезвычайных нужд? Вариант 4. На заводах №№ 1, 2 и 3 производится однородная продукция в количестве 500, 700 и 600 ед. соответственно. При этом затраты на производство единицы продукции на указанных заводах составляют 10, 3 и 6 ден. ед. Для четырех потребителей требуется соответственно 400, 800, 200 и 500 ед. продукции. Расхо- ды по перевозке единицы продукции с i-го завода j-му потребителю задаются элементами матрицы 3 5 6 1 5 1 3 3 . 4 5 8 1 Для полного удовлетворения потребителей необходимо соста- вить оптимальный план расширения производства продукции, если имеются следующие возможности: 1) расширить мощность завода № 1 с дополнительными затрата- ми на единицу продукции, равными 3 ден. ед.; 2) расширить мощность завода № 2 с дополнительными затрата- ми на единицу продукции, равными 2 ден. ед.; 3) построить новый завод с затратами на производство продук- ции, равными 5 ден. ед., и расходами по перевозке единицы про- дукции, равными соответственно 7, 6, 5 и 9 ден. ед. 18 Вариант 5. Имеются 4 трактора марки А, 20 – марки Б, 10 – мар- ки В и 4 – марки Г. Объем работ и себестоимость 1 га работ приве- дены в таблице. Сезонная норма выработки на один трактор марки А составляет 500 га условной пахоты, марки Б – 385 га, марки В – 310 га, марки Г – 300 га. Распределить сельскохозяйственные работы по маркам тракто- ров таким образом, чтобы общие затраты на выполнение работ бы- ли минимальными. Вид работ Объем работ, га условной пахоты Себестоимость 1 га работ, ден. ед., для трактора марки А Б В Г Культивация пара 3300 0,8 1,0 0,9 0,9 Пахота пара 6000 2,4 3,0 3,4 3,2 Культивация пропашных 1250 1,2 0,9 1,0 0,95 Боронование в один след 1600 0,2 0,27 0,25 0,27 Сенокошение 1850 0,7 0,8 0,75 0,85 Вариант 6. Заводы З1, З2, и З3 выпускают однородную продук- цию в количестве 40, 20 и 50 ед. себестоимостью 1, 3 и 7 ден. ед. соответственно. Продукция поставляется в пункты А, Б и В в коли- честве 30, 25 и 45 ед. соответственно с тарифами, приведенными в матрице: 7 6 13 1 7 6 . 4 3 2 Пятнадцать единиц продукции завода З3 предназначено для пункта Б. Продукцию завода с наименьшей себестоимостью распределить полностью. Составить наиболее экономный план удовлетворения потребностей в продукции, учитывающий затраты на ее производ- ство и доставку. 19 Вариант 7. Фирма переводит свой головной завод на производ- ство определенного вида изделий, которые будут выпускаться в те- чение четырех месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет: – запасов изделий, произведенных в прошлом месяце, сохраня- ющихся для реализации в будущем; – производства изделий в текущем месяце; – избытка производства изделий в более поздние месяцы в счет невыполненных заказов. Затраты на одно изделие в каждом месяце составляют 4 ден. ед. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 ден. ед. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыпол- ненных заказов, облагается штрафом в размере 2 ден. ед. в месяц. Объем производства изделий меняется от месяца к месяцу в за- висимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск не более 50, 180, 280 и 270 изделий соответственно. Требуется составить план, имеющий минимальную стоимость производства и хранения изделий. Вариант 8. Составить план посева зерновых культур по участ- кам различного плодородия, максимизирующий получаемую при- быль. Площадь участка I составляет 3000 га, участка II – 1000 га, участка III – 300 га, участка IV – 500 га. Остальные данные приве- дены в таблице. Зерновая культура Урожайность по участкам, ц/га Посевная площадь, га Заку- почная цена, ден. ед. Затраты средств по участкам на 1 га, ден. ед. I II III IV I II III IV Пшеница 35 25 20 15 2400 6,5 50 40 40 40 Кукуруза 60 40 30 50 1700 5,0 90 90 70 65 Ячмень 30 20 15 15 350 4,3 50 40 40 45 Рожь 25 30 20 15 250 7,0 50 50 45 40 Просо 40 20 15 10 100 7,2 60 50 50 50 20 Вариант 9. Заводы №№ 1, 2 и 3 производят однородную про- дукцию в количествах 490, 450 и 470 ед. соответственно. Себестои- мость производства единицы продукции на заводе № 1 составляет 25 ден. ед., на заводе № 2 – 20 ден. ед., на заводе № 3 – 23 ден. ед. Продукция отправляется в пункты А, Б, В, потребности которых равны соответственно 300, 340 и 360 ед. Стоимость перевозок еди- ницы продукции задается матрицей 7 5 1 3 4 5 . 4 2 1 Составить оптимальный план перевозки продукции с учетом ее себестоимости при условии, что коммуникации между заводом № 2 и пунктом А не позволяют пропускать в рассматриваемый период более 200 ед. продукции. Установить, во что обошлось ограничение пропускной способности указанного маршрута. Вариант 10. Завод имеет три цеха – А, Б, В – и четыре склада – №№ 1, 2, 3, 4. Цех А производит 30 тыс. изделий, цех Б – 40 тыс., цех В – 20 тыс. Пропускная способность складов за то же время ха- рактеризуется следующими показателями: склад № 1 – 25 тыс. из- делий, склад № 2 – 30 тыс., склад № 3 – 35 тыс., склад № 4 – 15 тыс. Стоимость перевозки из цеха А на склады №№ 1, 2, 3 и 4 одной ты- сячи изделий равна 2, 3, 0,5, 4 ден. ед. соответственно, из цеха Б – 3, 2, 5 и 1 ден. ед., из цеха В – 4, 3, 2 и 6 ден. ед. Составить план перевозки изделий на склады, минимизирующий транспортные расходы. При этом необходимо учесть, что на скла- дах №№ 1 и 4 созданы лучшие условия для хранения готовой про- дукции, а поэтому их следует загрузить полностью. Вариант 11. Механизмы М1, М2 и М3, имеющиеся в количествах 10, 5 и 15 ед., могут использоваться для работ на участках У1, У2, У3 и У4, с которых поступили заявки на 7, 12, 14 и 13 механизмов соот- ветственно. Производительность каждого механизма на соответ- ствующем участке приведена в матрице: 21 5 4 6 9 3 9 8 4 . 6 3 5 7 Распределить механизмы согласно заявкам так, чтобы общий объем выполненной работы был максимальным при непременном условии, что заявка участка У2 удовлетворена полностью. Вариант 12. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных услови- ях: из А1 в В1 должно быть перевезено не менее 50 ед. груза, из А3 в В5 – не менее 60 ед., а из А2 в В4 – не более 40 ед. груза. Потребность пункта В1 составляет 90 ед. груза, пункта В2 – 60 ед., В3 – 80 ед., В4 – 70 ед., В5 – 90 ед. Пункт отправления Пункт назначения Запас В1 В2 В3 В4 В5 А1 5 3 2 4 8 160 А2 7 6 5 3 1 90 А3 8 9 4 5 2 140 Содержание отчета 1. Титульный лист. 2. Цель работы. 3. Условие задачи. 4. Табличная модель. 5. Табличная модель с учетом дополнительных условий задачи. 6. Решение задачи. 7. Ответы на контрольные вопросы. Контрольные вопросы 1. Как записывается математическая модель задачи транспортного типа? 2. Как свести открытую транспортную задачу к закрытой? 3. Каковы основные ситуации, описывающие дополнительные ограничения транспортной задачи? 22 Лабораторная работа № 3 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ТРАНСПОРТНОЙ ЗАДАЧИ С ПОМОЩЬЮ EXCEL Цель работы: научиться решать задачи линейного программи- рования и транспортные задачи с помощью процедуры «Поиск ре- шения» в Excel. Теоретические основы Рассмотрим на примере задачи линейного программирования использование процедуры «Поиск решения» в Excel. Пример 1. Задача распределения ресурсов. Предприятие изготавливает и продает краску двух видов: для внутренних и внешних работ. Для производства краски использует- ся два исходных продукта A и B. Расходы продуктов A и B на 1 тонну соответствующих красок и запасы этих продуктов на складе приведены в таблице. Исходный продукт Расход продуктов, тонн, на 1 тонну краски Запас продукта на складе, тонн для внутренних работ для внешних работ A 1 2 3 B 3 1 3 Продажная цена за 1 тонну краски для внутренних работ состав- ляет 2000 рублей, краски для наружных работ – 1000 рублей. Тре- буется определить, какое количество краски каждого вида следует производить предприятию, чтобы получить максимальный доход. Решение. I. Составление математической модели задачи. 23 Обозначим: x1 – количество производимой краски для внутрен- них работ; x2 – соответствующее количество краски для наружных работ; F – доход от продажи краски (в тысячах рублей). Ограничения, которым должны удовлетворять переменные задачи: x1 + 2x2 ≤ 3; 3x1 + x2 ≤ 3; x1 ≥ 0, x2 ≥ 0. В левых частях первых двух неравенств определены расходы про- дуктов A и B, а в правых частях записаны запасы этих продуктов. Тогда целевая функция задачи записывается так: F = 2x1 + x2 → max. II. Решение задачи распределения ресурсов в Excel. Введем данные примера 1 в таблицу Excel (рисунок 1). Рисунок 1 – Ввод исходных данных На рисунке 1 «Краска 1» обозначает краску для внутренних ра- бот, «Краска 2» – краску для наружных работ. Для переменных задачи x1 и x2 отведены ячейки B3 и C3. Эти ячейки называются рабочими или изменяемыми ячейками. В изме- няемые ячейки ничего не заносится, и в результате решения задачи в них будут оптимальные значения переменных. 24 В ячейку D4 вводится формула для вычисления целевой функции задачи (дохода) F = 2x1 + x2. Чтобы сделать это, можно вводить форму- лу вручную, а можно воспользоваться функцией «СУММПРОИЗВ». Для этого выполняем следующие действия: курсор ставим в ячейку D4; в меню выбираем Вставка / Функция (или Формулы / Вставить функцию); в появившемся окне выбираем «Математиче- ские» и «СУММПРОИЗВ». В окне мастера функций следует нажать Далее, в появившемся окне в поле «Массив 1» ввести (протаскивая курсор мыши по ячейкам) адреса изменяемых ячеек B3:C3. В поле «Массив 2» необходимо ввести адреса ячеек B4:C4, содержащих цены на краски, после нажать Готово (рисунок 2). Рисунок 2 – Окно мастера функций В ячейку D7 вводится формула для вычисления израсходованно- го количества продукта А: x1 + 2x2, а в ячейку D8 вводится формула для израсходованного количества продукта B: 3x1 + x2. Обе форму- лы вводятся аналогично целевой функции. Проверить результаты ввода можно следующим образом: при установке курсора в ячейку D4 в строке ввода должно появиться «=СУММПРОИЗВ(B3:C3; B4:C4)»; в ячейке D7: «= СУММПРОИЗВ (B3:C3; B7:C7)»; в ячейке D8: «= СУММПРОИЗВ(B3:C3; B8:C8)». После ввода формул и данных экран имеет вид, представленный на рисунке 3. 25 Рисунок 3 – Окно после ввода исходных данных и формул В меню «Сервис» выбираем процедуру «Поиск решения». В появившемся окне нужно установить адрес целевой ячейки D4, значение целевой ячейки – максимальное, адреса изменяемых ячеек – B3:C3. Чтобы ввести ограничения задачи, следует нажать кнопку «Добавить». В появившемся диалоговом окне (рисунок 4) слева ввести адрес D7 (израсходованное количество продукта А), затем выбрать знак <=, а в правой части ввести количество продукта А на складе, равное 3 (или адрес ячейки E7). Рисунок 4 – Ввод ограничения После ввода нажать кнопку «Добавить» и аналогично ввести второе ограничение: D8 <= 3. Снова нажать кнопку «Добавить» и ввести ограничение B3:C3 >= 0 (соответствующее ограничению x1 ≥ 0, x2 ≥ 0). После ввода последнего ограничения нажать ОК. 26 После ввода ограничений окно «Поиск решения» будет иметь вид, представленный на рисунке 5. Рисунок 5 – Поиск решения Произведем настройку параметров решения задачи: в окне «По- иск решения» нажать «Параметры», в появившемся окне установить флажок в пункте «Линейная модель». В этом случае при решении задачи будет использоваться симплекс-метод. Остальные значения можно оставить без изменения. После нажать кнопку ОК. Для решения задачи в окне «Поиск решения» нажать кнопку «Выполнить». Если решение задачи найдено, то появляется окно «Результаты поиска решения» (рисунок 6). Рисунок 6 – Результаты поиска решения 27 Для просмотра результатов выбираем тип отчета «Результаты» и нажимаем кнопку ОК. В появившихся трех таблицах (рисунок 7) приводятся результаты поиска. Рисунок 7 – Отчет о результатах Из этих таблиц видно, что в оптимальном решении: производство краски 1 = B3 = 0,6; производство краски 2 = С3 = 1,2; при этом доход = D4 = 2,4; расход ресурса A = D7 = 3; расход ресурса B = D8 = 3. Таким образом, оба ресурса дефицитные (соответствующие ограничения называются связанными). «Отчет о результатах» состоит из трех таблиц: 28 в таблице 1 приводятся сведения о целевой функции; в таблице 2 приводятся значения переменных задачи; в таблице 3 показаны результаты поиска для ограничений задачи. Так же можно выбирать тип отчета «Устойчивость» или «Преде- лы» (см. рисунок 6). Первоначальная таблица Excel заполняется результатами, полу- ченными при решении (на рисунке 8 появившиеся значения в тем- ных ячейках). Рисунок 8 – Результат решения задачи Следовательно, чтобы получить максимальный доход 2400 руб- лей, предприятию необходимо производить 0,6 тонны краски для внутренних работ и 1,2 тонны краски для внешних работ. Рассмотрим транспортную задачу. Любую транспортную задачу можно представить в виде задачи линейного программирования, т. е. можно составить целевую функцию и ограничения. Следовательно, ее можно решать способами, которыми решаем задачу линейного программирования. Пример 2. Транспортная задача. В хранилищах А и В находится соответственно 170 и 90 тонн го- рючего. Пунктам 1, 2, 3 требуется соответственно 90, 60, 110 тонн горючего. Стоимость перевозки одной тонны горючего из храни- лища А в пункты 1, 2, 3 соответственно равна 50, 10, 40 ден. ед.; из хранилища В в пункты 1, 2, 3 соответственно равна 100, 30, 80 ден. ед. Составить план перевозки горючего, минимизирующий общие транспортные расходы. 29 Решение. I. Составление математической модели задачи. Введем следующие обозначения: x1 – количество горючего, перевозимого из хранилища А в пункт 1; x2 – из хранилища А в пункт 2; x3 – из хранилища А в пункт 3; x4 – из хранилища В в пункт 1; x5 – из хранилища В в пункт 2; x6 – из хранилища В в пункт 3; F – общие транспортные расходы, ден. ед. Так как транспортная задача закрытого типа (спрос = предложе- нию), то ограничения будут типа равенства (особенность транс- портной задачи). Ограничения, которым должны удовлетворять переменные задачи: x1 + x2 + х3 = 170; x4 + x5 + х6 = 90; x1 + x4 = 90; x2 + x5 = 60; x3 + x6 = 110; xi ≥ 0, i = 1, n . Тогда целевая функция задачи, минимизирующая общие транс- портные расходы, записывается так: F = 50x1 + 10x2 + 40х3 + 100x4 + 30x5 + 80х6 → min. Таким образом, получили математическую модель задачи ли- нейного программирования. II. Решение транспортной задачи с помощью «Поиска решения» в Excel производится аналогично решению задачи линейного про- граммирования (пример 1). 30 Задания Решить задачи своего варианта из лабораторных работ № 1 и № 2 с помощью «Поиска решения» в Excel. Сравнить полученные результаты. Содержание отчета 1. Титульный лист. 2. Цель работы. 3. Условие задачи линейного программирования. 4. Математическая модель задачи с условными обозначениями и пояснениями. 5. Реализация решения задачи линейного программирования в Excel. 6. Условие транспортной задачи. 7. Математическая модель транспортной задачи с условными обозначениями и пояснениями. 8. Реализация решения транспортной задачи в Excel. 9. Ответы на контрольные вопросы. Контрольные вопросы 1. Как транспортную задачу представить в виде задачи линейно- го программирования? 2. Как с помощью процедуры «Поиск решения» в Excel можно решать задачи линейного программирования и транспортные задачи? 31 Литература 1. Балашевич, В. А. Экономико-математическое моделирование производственных систем : учеб. пособие для вузов / В. А. Балаше- вич, А. М. Андронов. – Минск : Унiверсiтэцкае, 1995. – 240 с. : ил. 2. Кузнецов, А. В. Высшая математика. Математическое програм- мирование : учеб. / А. В. Кузнецов, В. А. Сакович, Н. И. Холод, – 2-е изд., перераб. и доп. – Минск : Выш. шк., 2001. – 351 с. : ил. 3. Падалко, Л. П. Математические методы оптимального плани- рования развития и эксплуатации энергосистем / Л. П. Падалко. – Минск : Выш. шк., 1972. 4. Партыка, Т. Л. Математические методы : учеб. / Т. Л. Партыка, И. И. Попов. – М. : ФОРУМ : ИНФРА-М, 2005. – 464 с. : ил. 5. Экономико-математические методы и модели : учеб. пособие / Н. И. Холод [и др.] ; под ред. А. В. Кузнецова. – 2-е изд. – Минск : БГЭУ, 2000. – 412 с. : ил. Содержание Лабораторная работа № 1 ПОСТРОЕНИЕ И АНАЛИЗ НА ЧУВСТВИТЕЛЬНОСТЬ МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ………………..……………………………3 Лабораторная работа № 2 ТРАНСПОРТНЫЕ МОДЕЛИ…………………….………………….13 Лабораторная работа № 3 РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ТРАНСПОРТНОЙ ЗАДАЧИ С ПОМОЩЬЮ EXCEL……………..………………………………..22 Литература……………………………………………….……………31 Учебное издание ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ Лабораторный практикум для студентов специальности 1-27 01 01 «Экономика и организация производства» В 2 частях Часть 1 Составитель КУПРИК Алёна Викторовна Редактор В. О. Кутас Компьютерная верстка А. Г. Занкевич Подписано в печать 09.11.2012. Формат 60 84 1/16. Бумага офсетная. Ризография. Усл. печ. л. 1,92. Уч.-изд. л. 1,5. Тираж 100. Заказ 1093. Издатель и полиграфическое исполнение: Белорусский национальный технический университет. ЛИ № 02330/0494349 от 16.03.2009. Пр. Независимости, 65. 220013, г. Минск