Размещено на http://www.allbest.ru/

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



Содержание

• Введение
• 1. Задачи линейного программирования и методы их решения
• 1.1 Постановка задачи линейного программирования
• 1.2 Методы решения задач линейного программирования
• 1.3 Изучение элементов линейного программирования в профильных и элективных курсах информатики
• 2. Электронные таблицы и их применение в решении задач
• 2.1 Краткие сведения об электронных таблицах MS Excel
• 2.2 Технология решения задач линейного программирования с помощью поиска решений в среде Excel
• 2.3 Задания к контрольной работе
• Заключение
• Список литературы


Введение

Задачи линейного программирования были первыми, подробно изученными, задачами поиска экстремума функций при наличии ограничений типа неравенств. В 1820 году Фурье и затем в 1947 году Данциг предложил метод направленного перебора смежных вершин в направлении возрастания целевой функции -- симплекс-метод, ставший основным при решении задач линейного программирования.

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

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

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

В 1931 году венгерский математик Б. Эгервари рассмотрел математическую постановку и решил задачу линейного программирования, имеющую название «проблема выбора», метод решения получил название «венгерского метода».

Канторовичем совместно с М. К. Гавуриным в 1949 году разработан метод потенциалов, который применяется при решении транспортных задач. В последующих работах Канторовича, Немчинова, В. В. Новожилова, А. Л. Лурье, А. Брудно, Аганбегяна, Д. Б. Юдина, Е. Г. Гольштейна и других математиков и экономистов получили дальнейшее развитие как математическая теория линейного и нелинейного программирования, так и приложение её методов к исследованию различных экономических проблем.

Методам линейного программирования посвящено много работ зарубежных учёных. В 1941 году Ф. Л. Хитчкок поставил транспортную задачу. Основной метод решения задач линейного программирования -- симплекс-метод -- был опубликован в 1949 году Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Куна (англ.), А. Таккера (англ.), Гасса (Saul. I. Gass), Чарнеса (Charnes A.), Била (Beale E. M.) и др.

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

Начиная с 1955 году опубликовано много работ, посвященных квадратическому программированию (работы Била, Баранкина и Дорфмана (Dorfman R.), Франка (Frank M.) и Вольфа (Wolfe P.), Марковица и др.). В работах Денниса (Dennis J. B.), Розена (Rosen J. B.) и Зонтендейка (Zontendijk G.) разработаны градиентные методы решения задач нелинейного программирования. программирование информатика еxcel

В настоящее время для эффективного применения методов математического программирования и решения задач на компьютерах разработаны алгебраические языки моделирования, представителями которыми являются AMPL и LINGO.

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

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

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

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

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

Объект исследования - задачи линейного программирования.

Предмет исследования - методы и средства решения задач линейного программирования.

Цель - рассмотреть методы решения задач линейного программирования.

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

Задачи исследования:

Рассмотреть постановку задач линейного программирования;

Привести описание методов решения задач линейного программирования;

Проанализировать порядок изучения элементов линейного программирования в профильных и элективных курсах информатики;

Изучить методы и средства электронные таблицы и их применение в решении задач;

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

Изучение элементов линейного программирования в профильных и элективных курсах информатики

Методы, используемые при написании работы - изучение и анализ учебно-методической литературы, классификация, сопоставление методов обучения.

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

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

В первой главе работы рассмотрены понятия задачи линейного программирования и методы их решения. Первый параграф посвящен постановке задачи линейного программирования. Во втором параграфе главы описаны методы решения задач линейного программирования.

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



1. Задачи линейного программирования и методы их решения

1.1 Постановка задачи линейного программирования

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

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

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

Задача, в которой фигурируют ограничения в форме неравенств, называется основной задачей линейного программирования (ОЗЛП)

,

.

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

,

Основную задачу можно свести к канонической путём введения дополнительных переменных.

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

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

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

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

Дана линейная функция вида

F c1 x1 c2 x2 ... cn1 xn1 cn xn

На функцию F накладываются следующие ограничения:

a11x1 a12 x2 ...a1n xn b1

a21x1 a22 x2 ...a2n xn b2

am1x1 am2 x2 ...amnxn bm

xj 0( j 1, n), где:

c j - коэффициент целевой функции

( j 1, n) ;

ai j - коэффициент при x j

(i 1, m; j 1, n) ;

x j - неизвестные

( j 1, n);

bi - свободные члены

(i 1, m);

Требуется найти решение

X (x1 , x2 ,..., xn1 , xn ),

которое удовлетворяет ограничениям, при которых функция F0 минимальное значение.

Для данного типа задачи необходимо разработать программу, позволяющую:

Вносить исходные данные;

Производить протокол расчета решения задачи;

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

Вести базу данных учетных записей пользователей тестовой системы;

Проводить тестирование с выдачей и сохранением результатов.

1.2 Методы решения задач линейного программирования

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

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

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

Решение задачи линейного программирования графическим методом включает следующие этапы:

На плоскости X10X2 строят прямые. Определяются полуплоскости.

Определяют многоугольник решений;

Строят вектор N(c1,c2), который указывает направление целевой функции;

Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.

Вычисляют координаты точки и значение целевой функции в этой точке.

Рис. 1 Иллюстрация к графическому методу

Простой перебор. Возьмем некоторый многомерный параллелепипед, в котором лежит многогранник, задаваемый ограничениями. Как его построить? Например, если имеется ограничение типа 2Х1 + 5Х2 ? 10, то, очевидно, 0 ? Х1 ? 10/2 = 5 и 0 ? Х2 ? 10/2 = 5. Аналогичным образом от линейных ограничений общего вида можно перейти к ограничениям на отдельные переменные. Остается взять максимальные границы по каждой переменной. Если многогранник, задаваемый ограничениями, неограничен, как было в задаче о диете, можно похожим, но несколько более сложным образом выделить его "обращенную" к началу координат часть, содержащую решение, и заключить ее в многомерный параллелепипед.

Проведем перебор точек параллелепипеда с шагом 1/10n последовательно при n=2,3,…, вычисляя значения целевой функции и проверяя наличие ограничений. Из всех точек, удовлетворяющих ограничениям, возьмем ту, в которой целевая функция максимальна. Решение найдено! (Более строго выражаясь, найдено с точностью до 1/10n .)

Направленный перебор. Начнем с точки, удовлетворяющей ограничениям (ее можно найти простым перебором). Будем последовательно (или случайно - т.н. метод случайного поиска) менять ее координаты на определенную величину ?, каждый раз в точку с более высоким значением целевой функции. Если выйдем на плоскость ограничения, будем двигаться по ней (находя одну из координат по уравнению ограничения). Затем движение по ребру (когда два ограничения-неравенства переходят в равенства)… Остановка - в вершине линейного многогранника. Решение найдено! (Более строго выражаясь, найдено с точностью до ? ; если необходимо, в окрестности найденного решения проводим направленный перебор с шагом ?/2 , ?/4 и т.д.)

Симплекс-метод. Этот один из первых специализированных методов оптимизации, нацеленный на решение задач линейного программирования, в

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

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

Первый полиномиальный алгоритм, метод эллипсоидов, был предложен в 1979 году советским математиком Л. Хачияном, разрешив таким образом проблему, долгое время остававшуюся нерешённой. Метод эллипсоидов имеет совершенно другую, некомбинаторную природу, нежели симплекс-метод. Однако в вычислительном плане этот метод оказался неперспективным.

Тем не менее, сам факт полиномиальной сложности задач привёл к созданию целого класса эффективных алгоритмов ЛП --методов внутренней точки, первым из которых был алгоритм Н. Кармаркара, предложенный в 1984 году. Алгоритмы этого типа используют непрерывную трактовку задачи ЛП, когда вместо перебора вершин многогранника решений задачи ЛП осуществляется поиск вдоль траекторий в пространстве переменных задачи, не проходящих через вершины многогранника. Метод внутренних точек, который, в отличие от симплекс-метода, обходит точки из внутренней части области допустимых значений, использует методы логарифмических барьерных функций нелинейного программирования, разработанные в 1960-х годах Фиако (Fiacco) и МакКормиком (McCormick).

Продемонстрируем применение симплекс-метода на следующем примере.

Пример. Рассмотрим задачу линейного программирования: F = 15 Х1 + 12 Х2 + 14 Х3 > max .

Х1 / 200 + Х2 / 300 + Х3 / 120 ? 100 ,

Х1 / 300 + Х2 / 100 + Х3 / 100 ? 100 , Х3 / 80 ? 100 .

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

В соответствии с симплекс-методом введем т.н. "свободные переменные" Х4 , Х5 , Х6 , соответствующие недоиспользованным мощностям, т.е. перейдем к системе уравнений:

Х1 / 200 + Х2 / 300 + Х3 / 120 + Х4 = 100 , Х1 / 300 + Х2 / 100 + Х3 / 100 + Х5 = 100 , Х3 / 80 + Х6 = 100 ,

15 Х1 + 12 Х2 + 14 Х3 = F .

У этой системы имеется очевидное решение, соответствующее вершине многогранника допустимых значений переменных:

Х1 = Х2 = Х3 = 0, Х4 = Х5 = Х6 = 100, F = 0.

В терминах исходной задачи это значит, что ничего не надо выпускать.

Такое решение приемлемо только на период летних отпусков.

Выбираем переменную, которая входит в целевую функцию F с самым большим положительным коэффициентом. Это Х1 .

Сравниваем частные от деления свободных членов в первых трех

уравнениях на коэффициенты при только что выбранной переменной Х1: 100 / (1/200) = 20000, 100 / (1/300) =30000, 100/0 = + ? .

Выбираем строку, которой соответствует минимальное из всех положительных отношений. В рассматриваемом примере - это первая строка, которой соответствует отношение 20000.

Умножим первую строку на 200, чтобы получить Х1 с единичным коэффициентом:

Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20000 .

Затем умножим вновь полученную строку на (-1/300) и сложим со второй строкой, получим

7/900 Х2 + 4/900 Х3 - 2/3 Х4 + Х5 = 100/3.

Ту же преобразованную первую строку умножим на (-15) и сложим со строкой, в правой части которой стоит F, получим:

2 Х2 - 11 Х3 - 3000 Х4 = F - 300000.

В результате система уравнений преобразуется к виду, в котором переменная Х1 входит только в первое уравнение:

Х1 + 2/3 Х2 + 2/1,2 Х3 + 200 Х4 = 20000 ,

7/900 Х2 + 4/900 Х3 - 2/3 Х4 + Х5 = 100/3, Х3 / 80 + Х6 = 100 ,

2 Х2 - 11 Х3 - 3000 Х4 = F - 300000.

Очевидно, у новой системы имеется улучшенное по сравнению с исходным решение, соответствующее вершине в шестимерном пространстве:

Х1 = 20000, Х2 = Х3 = Х4 = 0, Х5 = 100/3, Х6 = 100, F = 300000.

В терминах исходной задачи это значит, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.

Повторим описанную выше операцию. В строке с F имеется еще один положительный коэффициент - при Х2 (если бы положительных коэффициентов было несколько - мы взяли бы максимальный из них). На основе коэффициентов при Х2 (а не при Х1, как в первый раз) образуем частные от деления соответствующих свободных членов на эти коэффициенты:

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ?.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х2 , предварительно умножив их на подходящие числа, т.е. такие, чтобы все коэффициенты при Х2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х1 + 9/7 Х3 + 1800/7 Х4 - 600/7 Х5 = 120000/7 , Х2 + 4/7 Х3 - 600/7 Х4 + 900/7Х5 = 30000/7,

Х3 / 80 + Х6 = 100 ,

- 85/7 Х3 - 19800/7 Х4 - 1800/7 Х5 = F - 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х3 = Х4 = Х5 = 0. Из остальных уравнений следует, что при этом Х1 = 120000/7 = 17143, Х2 = 30000/7 = 4286, Х6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс-метода закончил свою работу, оптимальное решение найдено.

1.3 Изучение элементов линейного программирования в профильных и элективных курсах информатики

Задачи линейного программирования могут изучаться в рамках различных курсов информационного и физико-математического профилей. К таким курсам относится элективный курс «Информационные системы и модели» (авторский коллектив: д-р пед. наук, профессор И. Г. Семакин, д-р физ.-мат. наук, профессор Е.К. Хеннер). Ознакомимся со структуру и планированием указанного курса.

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

Курс «Информационные системы и модели» является преемственным по отношению к базовому курсу информатики, обеспечивающему требования к ее изучению в основной школе. При планировании и создании курса авторы учитывают, что раздел «Информационные системы и модели» становится одним из ведущих в изучении информатики на старшей ступени школы.

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

Среди многочисленных приложений современной информатики и информационных технологий в данном учебном курсе выделяются два:

информационные системы;

компьютерное математическое моделирование.

Содержание курса

Курс состоит из двух разделов.

Раздел 1. Моделирование информационных систем

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

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

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

По ходу изучения раздела осваиваются элементы программирования приложений на языке Visual Basic Application (VBA).

Раздел 2. Компьютерное математическое моделирование

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

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

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

Составной частью курса является подготовка реферата по одной из проблем, затронутых в курсе, а также выполнение и защита проекта. При подборе материалов для реферата учащимся рекомендуется использование ресурсов Интернета, для его оформления потребуется работа с текстовым процессором Word и иными средствами пакета MS Office. Защиту проекта рекомендуется проводить с использованием презентации, созданной средствами Power Point.

Тематическое планирование изучения курса

1. Моделирование информационных систем (30 ч) Системы и структуры данных (4 ч)

Основные понятия системологии: система, структура. Графы и сети. Иерархические структуры данных; деревья. Табличная организация данных.

Информационные системы и базы данных (3 ч)

Понятие информационной системы. Классификация информационных систем. Основные понятия баз данных. Назначение и функции СУБД.

Базы данных на электронных таблицах (8 ч)

Создание однотабличной базы данных (списка) в среде табличного процессора (MS Excel). Правила оформления списка. Использование формы

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

Базы данных в реляционных СУБД (10 ч)

Проектирование многотабличной базы данных. Понятие о нормализации данных. Типы связей между таблицами. Создание базы данных в среде реляционной СУБД (MS ACCESS). Реализация приложений: запросы, отчеты.

Программирование в среде СУБД (5 ч)

Разработка пользовательского интерфейса: кнопочные формы. Мак- росы. Введение в VBA.

2. Компьютерное математическое моделирование (36 ч)

Введение в технологию компьютерного математического моделирования (4 ч)

Основные понятия и принципы моделирования. Моделирование и компьютеры. Разновидности математических моделей. Компьютерное математическое моделирование, его этапы.

Инструментарий компьютерного математического моделирования (8 ч).

Табличные процессоры и электронные таблицы. Табличный процессор

MS Excel, основные сведения. Построение графиков зависимостей между величинами в ТП Excel. Система математических расчетов MathCAD. Примеры использования MathCAD.

Моделирование процессов оптимального планирования (18 ч) Постановка задач оптимального планирования. Линейное программирование -- введение. Общая формулировка и существование решения задач линейного программирования. Симплекс-метод. Алгоритмическая реализация симплекс-метода. Понятие о нелинейном программировании.

Использование средства «Поиск решения» табличного процессора Excel для решения задач линейного и нелинейного программирования. Решение задач оптимизации с помощью пакета MathCAD. Программная реализация симплекс-метода в VBA; сопоставление с Turbo-Pascal. Динамическое программирование. Алгоритмическая реализация метода динамического программирования. Реализация алгоритма динамического программирования в VBA. Понятие о моделях многокритериальной оптимизации.

Компьютерное имитационное моделирование (6 ч)

Принципы имитационного моделирования. Введение в математический аппарат имитационного моделирования. Случайные числа и их рас- пределения. Пример моделирования системы массового обслуживания с помощью VBA. Пример имитационного моделирования в экономике. Пример имитационного моделирования в экологии.

3. Подготовка реферата, презентации, подготовка и защита проекта (6 ч).



2. Электронные таблицы и их применение в решении задач

2.1 Краткие сведения об электронных таблицах MS Excel

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

Использовать сложные формулы, содержащие встроенные функции.

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

Создавать сводные таблицы.

Применять к таблицам сортировку и фильтрацию данных.

Осуществлять консолидацию данных (объединение данных из нескольких таблиц в одну).

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

Выполнять автоматизированный поиск ошибок в формулах. Защищать данные.

Использовать структурирование данных (скрывать и отображать части таблиц).

Применять автозаполнение. Применять макросы.

Строить диаграммы.

Использовать автозамену и проверку орфографии. Использовать стили, шаблоны, автоформатирование. Обмениваться данными с другими приложениями.

Ключевые понятия:

Рабочая книга - основные документы, хранится в файле. Лист (объем: 256 столбцов, 65536 строк).

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

Формула - математическая запись вычислений. Ссылка - запись адреса ячейки в составе формулы.

Функция - математическая запись, указывающая на выполнение определенных вычислительных операций. Состоит из имени и аргументов.

Ввод данных:

Данные могут быть следующих типов - Числа.

Текст. Функции. Формулы.

Вводить можно - В ячейки.

В строку формул.

Если на экране в ячейке после ввода появляется ########, значит число длинное и в ячейке не помещается, то надо увеличить ширину ячейки.

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

Ссылка на ячейку (например, А6).

Функция.

Арифметический оператор (+, -, /, *). Операторы сравнения (>, <, <=, =>, =).

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

Функции - это стандартные формулы для выполнения определенных задач. Функции используются только в формулах.

Способ: Вставка - Функция или в строке формул щелкнуть на =. Появится диалоговое окно со списком десяти недавно использованных функций. Для расширения списка выбрать Другие функции…, откроется другое диалоговое окно, где функции сгруппированы по типам (категориям), приведено описание назначения функции и их параметров.

Полное описание по работе с электронными таблицами MS Excel, можно найти в учебниках и пособиях.

2.2 Технология решения задач линейного программирования с помощью поиска решений в среде Excel

Поиск решения - это надстройка EXCEL, которая позволяет решать оптимизационные задачи. Если, в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.

После выбора команд Сервис Поиск решения появится диалоговое окно Поиск решения.

В диалоговом окне Поиск решения есть три основных параметра:

• Установить целевую ячейку

• Изменяя ячейки

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

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

Второй важный параметр средства Поиск решения - это параметр Изменяя ячейки. Изменяемые ячейки - это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.

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

Для решения задачи необходимо:

1) Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

2) Ввести исходные данные.

3) Ввести зависимость для целевой функции

4) Ввести зависимости для ограничений. Запустить Поиск решений.

5) Назначение целевой функции (установить целевую ячейку).

6) Ввод ограничений.

7) Ввод параметров для решения ЗЛП.

Рассмотрим технологию решения используя условия Задачи 1 (Задача о костюмах).

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

Сформулируем математическую модель задачи

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

Прибыль от реализации женских костюмов составляет 10х 1, а от реализации мужских 20х 2, т.е. необходимо максимизировать целевую функцию

f(x) = 10х1 + 20х2 -> max.

Ограничения задачи имеют вид:

х1 + х2 150 - ограничение по труду

2х1 + 0.5х2 240 - ограничение по лавсану х1 + 3.5х2 350 - ограничение по шерсти

х2 60 - ограничение по костюмам х1 0

Решение.

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Обозначьте через Х1, Х2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2,) будут помещены в ячейках A2:B2, оптимальное значение целевой функции в ячейке C3.

2. Ввести исходные данные.

Введите исходные данные задачи, как показано на рис.2.

Рис. 2.

3. Ввести зависимость для целевой функции

*Курсор в ячейку "С3".

*Курсор на кнопку "Мастер функций", расположенную на панели инструментов.

*М1. На экране появляется диалоговое окно "Мастер функций шаг 1 из 2"

• Курсор в окно "Категория" на категорию "Математические".

• Курсор в окно "Функции" на "СУММПРОИЗВ" (рис.3).

Рис 3.

На экране появляется диалоговое окно "СУММПРОИЗВ" (рис. 3)

Рис. 4.

• В строку "Массив 1"1 ввести А2:В2

• В строку "Массив 2" ввести А3:В3.

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

Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку2.

На экране: в ячейку С3 введена функция (рис. 3).

Рис. 5.

4. Ввести зависимости для ограничений.

• Курсор в ячейку "С3".

• На панели инструментов кнопка "Копировать в буфер".

• Курсор в ячейку "С4".

• На панели инструментов кнопка "Вставить из буфера".

• Курсор в ячейку "С5".

• На панели инструментов кнопка "Вставить из буфера".

• Курсор в ячейку "С6".

• На панели инструментов кнопка "Вставить из буфера".

• Курсор в ячейку "С7".

• На панели инструментов кнопка "Вставить из буфера".

2 Относительные и абсолютные ссылки. В зависимости от выполняемых задач в Excel можно использовать относительные ссылки, определяющие положение ячейки относительно положения ячейки формулы, или абсолютные ссылки, которые всегда указывают на конкретные ячейки. Если перед буквой или номером стоит знак доллара, например, $A$2, то ссылка на столбец или строку является абсолютной. Относительные ссылки автоматически корректируются при их копировании, а абсолютные ссылки - нет.

Рис.6.

Примечание. Содержимое ячеек С4 - С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис.6 (в качестве примера представлено содержимое ячейки С5).

Рис. 7.

В строке "Меню" указатель мышки на имя "Сервис". В развернутом меню команда "Поиск решения". Появляется диалоговое окно "Поиск решения" (рис. 7).

Рис. 8.

5. Назначить целевую функцию (установить целевую ячейку), указать адреса изменяемых ячеек.

• Курсор в строку "Установить целевую ячейку".

• Введите адрес ячейки "$С$3".

• Введите направление целевой функции в зависимости от условия вашей задачи: "Максимальному значению" ("Минимальному значению").

• Курсор в строку "Изменяя ячейки".

• Ввести адреса искомых переменных А$2:В$2. (Рис. 8.)

Рис. 9.

6. Ввести ограничения

• Указатель мышки на кнопку "Добавить". Появляется диалоговое окно "Добавление ограничения"

• В строке "Ссылка на ячейку" введите адрес $С$4.

• Ввести знак ограничения ?.

• В строке "Ограничение" введите адрес $D$4 (рис. 9).

• Указатель мышки на кнопку "Добавить". На экране вновь диалоговое окно "Добавление ограничения".

• Введите остальные ограничения задачи, по выше описанному алгоритму

• После введения последнего ограничения кнопка "ОК".

На экране появится диалоговое окно "Поиск решения" с введенными условиями (рис.10).

Рис. 10.

Рис.11

7. Ввести параметры для решения ЗЛП

• В диалоговом окне указатель мышки на кнопку "Параметры". На экране появляется диалоговое окно "Параметры поиска решения" (рис.

Рис.12

• Установите флажки в окнах "Линейная модель" (это обеспечит применение симплекс - метода) и "Неотрицательные значения".

• Указатель мышки на кнопку "ОК". На экране диалоговое окно

"Поиск решения".

• Указатель мышки на кнопку "Выполнить".

Через непродолжительное время появится диалоговое окно "Результаты поиска решения" и исходная таблица с заполненными ячейками А3:В3 для значений Хi и ячейка С3 с максимальным значением целевой функции (рис.12).

Рис.13

Если указать тип отчета "Устойчивость", то можно получить дополнительную информацию об оптимальном решении (Рис. 14).

Рис. 14

В результате решения задачи получили ответ:

Х1 = 70 - необходимо сшить женских костюмов,

Х2 = 80 - необходимо сшить мужских костюмов,

F(x) = 2300 что бы получить максимальную прибыль. Решим еще одну задачу.

Задача о коврах

Фабрика имеет в своем распоряжении определенное количество ресурсов: рабочую силу, деньги, сырье, оборудование, производственные площади и т. п. Допустим, например, ресурсы трех видов рабочая сила, сырье и оборудование имеются в количестве соответственно 80 (чел/дней), 480(кг), 130 (станко/часов). Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса необходимых для производства одного ковра каждого вида и доходах, получаемых предприятием от единицы каждого вида товаров, приведена в табл.1.

Таблица 1

Ресурсы	Нормы расхода ресурсов на единицу изделия	Наличие ресурсов
	Ковер А	Ковер В	Ковер С	Ковер D
Труд	7	2	2	6	80
Сырье	5	8	4	3	480
Оборудова ние	2	4	1	8	130
Цена (тыс. руб.)	3	4	3	1

Требуется найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальная.

1. Сформулируем экономико - математическую модель задачи. Обозначим через Х1, Х2, Х3, Х4 количество ковров каждого типа.

Целевая функция - это выражение, которое необходимо максимизировать

f(x) = 3Х1 +4Х2 +3Х3 +Х4

Ограничения по ресурсам

7Х1 +2Х2 +2Х3 +6Х4 80

5Х1 +8Х2 +4Х3 +3Х4 480

2Х1 +4Х2 +Х3 +8Х4 130 Х1, Х2, Х3, Х4 0

Решение

1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).

Обозначьте через Х1, Х2, Х3, Х4 количество ковров каждого типа. В нашей задаче оптимальные значения вектора Х =(Х1, Х2, Х3, Х4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции в ячейке F4.

2. Ввести исходные данные.

Введем исходные данные в созданную форму. В результате получим (Рис. 15):

Рис. 15. Данные введены

3. Введем зависимость для целевой функции

• Курсор в F4.

• Курсор на кнопку Мастер функций.

На экране диалоговое окно Мастер функций шаг 1 из 2.

• Курсор в окно Категория на категорию Математические.

Рис. 16. Вводится функция для вычисления целевой функции

• Курсор в окно Функции на СУММПРОИЗВ.

• В массив 1 ввести3 В$3:E$3.

• В массив 2 ввести В 4:E4.

• Готово. На экране: в F4 введена функция, как показано на Рисунке 15.

4. Введем зависимость для левых частей ограничений:

• Курсор в F4.

• Копировать в буфер.

• Курсор в F7.

• Вставить из буфера.

• Курсор в F8.

• Вставить из буфера.

• Курсор в F9.

• Вставить из буфера.

На этом ввод зависимостей закончен. Запуск Поиска решения.

6) Назначение целевой функции (установить целевую ячейку).

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

· Курсор в поле Установить целевую ячейку.

Ввести адрес $F$4.

Ввести направление целевой функции: Максимальному значению. Ввести адреса искомых переменных:

Курсор в поле Изменяя ячейки. Ввести адреса В$3:E$3.

5. Ввод ограничений.

Курсор в поле Добавить. Появится диалоговое окно Добавление ограничения (Рис. 17.).

Рис. 17. Ввод правых и левых частей ограничений.

· В окне Ссылка на ячейку ввести $F$7.

· Ввести знак ограничение

· Курсор в правое окно.

Вести $H$7.

· Добавить. На экране опять диалоговое окно Добавление ограничения.

Ввести остальные ограничения.

· После ввода последнего ограничения ввести ОК.

На экране появится диалоговое окно Поиск решения с введенными условиями (Рис. 18).

Рис. 18. Введены все условия для решения задачи.

8) Ввод параметров для решения ЗЛП (Рис. 18). Открыть окно Параметры поиска решения.

Установить флажок Линейная модель, что обеспечивает применение симплекс-метода.

Установить флажок Неотрицательные значения.

ОК (На экране диалоговое окно поиска решения).

Выполнить (На экране диалоговое окно результаты поиска решения - Рис. 19.).

Рис. 19. Ввод параметров

Рис. 20. Решение найдено

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 кг.

Создание отчета по результатам поиска решения

Excel позволяет представить результаты поиска решения в форме отчёта. Существует три типа таких отчетов:

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

Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках иди в формулах ограничений.

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

Отчет по результатам

Рис. 21

В отчете по результатам содержатся оптимальные значения переменных Х1, Х2, Х3, Х4, которые соответственно равны 0,10, 30,0; значение целевой функции - 150, а также левые части ограничений.



2.3 Задания к контрольной работе

В параграфе приведены варианты задач линейного программирования. Решение задач требуется оформить в виде Excel документа. В практической работе рекомендуется использовать ресурсы онлайн-калькулятора.

Онлайн-калькулятор: Графический метод решения ЗЛП - [Электронный ресурс]: ООО Новый семестр URL: http://math.semestr.ru/lp/index.php

НАЗНАЧЕНИЕ СЕРВИСА. С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в Excel.

ИНСТРУКЦИЯ. Выберите количество строк (количество ограничений). Начало формы

Количество ограничений

Конец формы

Если количество переменных больше двух, необходимо систему привести к КЗЛП. Если ограничение двойное, например, 1 ? x1 ? 4, то оно разбивается на два: x1 ? 1, x1 ? 4 (т.е. количество строк увеличивается на 1).

Задача 1

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

Сформулировать двойственную задачу и найти ее оптимальный план, используя теоремы двойственности.

Задача 2

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

В каждой задаче требуется:

Определить план выпуска продукции из условия максимизации его стоимости.

Определите ценность каждого ресурса (двойственные оценки) и его приоритет при решении задачи увеличения запаса ресурсов.

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

На сколько уменьшится стоимость выпускаемой продукции при принудительном выпуске единицы нерентабельной продукции?

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

Вариант 1

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
	А	Б	В	Г
I	1	2	1	0	18
II	1	1	2	1	30
III	1	3	3	2	40
Цена изделия	12	7	18	10

1. Определить, как изменятся общая стоимость продукции и план ее выпуска при увеличении запасов сырья I и II вида на 4 и 3 единицы соответственно и уменьшении на 3 единицы сырья III вида.

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

Вариант 2

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

Тип сырья	Нормы расхода сырья на одно изделие	Запасы сырья
	А	Б	В	Г
I	1	0	2	1	180
II	0	1	3	2	210
III	4	2	0	4	800
Цена изделия	9	6	4	7

5. Определить, как изменятся общая стоимость продукции и план выпуска при увеличении запасов сырья II и III вида на 120 и 160 ед. соответственно и одновременном уменьшении на 60 ед. запасов сырья I вида;

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

Вариант 3

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

Тип Сырья	Нормы расхода сырья на одно изделие	Запасы сырья
	А	Б	В
I	4	2	1	180
II	3	1	3	210
III	1	2	5	244
Цена	10	14	12

5. Определить, как изменится общая прибыль продукции и план выпуска при увеличении запасов сырья I и III вида на 4 ед. каждого;

6. Определить целесообразность включения в план изделия "Г", на изготовление которого расходуется соответственно 1, 3 и 2 ед. каждого вида сырья ценой 13 ед. и изделия "Д" на изготовление которого расходуется по две единицы каждого вида сырья ценой 12 ед.

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

Тип Сырья	Нормы расхода сырья на одно изделие	Запасы ырья
	А	Б	В	Г
I	2	1	3	2	200
II	1	2	4	8	160
III	2	4	1	1	170
Цена изделия	5	7	3	8

Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья I и II вида на 8 и 10 ед. соответственно и одновременном уменьшении на 5 ед. запасов сырья III вида;

Определить целесообразность включения в план изделия "Д" на изготовление, которого расходуется по две единицы каждого вида сырья и ожидается прибыль 10 ед.

Вариант 5

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

Ресурсы	Нормы затрат ресурсов на единицу продукции	Запасы
	I вид	II вид	III вид
Труд	1	4	3	200
Сырье	1	1	2	80
Оборудован ие	1	1	2	140
Цена	40	60	80

5. Определить, как изменится общая стоимость продукции и план выпуска при увеличении запасов сырья на 18 единиц;.

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

Вариант 6

На предприятии выпускается три вида изделий, используется при этом три вида сырья:

Сырье	Нормы затрат ресурсов на единицу продукции	Запасы сырья
	А	Б	В
I	18	15	12	360
II	6	4	8	192
III	5	3	3	180
Цена	9	10	16

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида увеличить на 45 кг., а II - уменьшить на 9кг.?

6. Целесообразно ли выпускать изделие Г ценой 11 единиц, если нормы затрат сырья 9, 4 и 6 кг.?

Вариант 7

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

Ресурсы	Нормы затрат ресурсов на единицу продукции	Запасы
	I вид	II вид	III вид
Труд	3	6	4	2000
Сырье 1	20	15	20	15000
Сырье 2	10	15	20	7400
Оборудование	0	3	5	1500
Цена	6	10	9

5. Как изменится общая стоимость выпускаемой продукции и план ее выпуска, если запас сырья I вида у...