Применение MS EXCEL для решения задач линейного программирования

Линейное программирование

СОДЕРЖАНИЕ

Введение 4

1. ОБЩАЯ ЧАСТЬ 5

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

1.2.Применение процессора Microsoft Excel для расчета задач линейного программирования 10

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

1.3.1.Microsoft Visual Basic 6.0 22

1.3.2 Microsoft Office 24

1.4. Алгоритм нахождения оптимального решения задач линейного программирования 26

2. СПЕЦИАЛЬНАЯ ЧАСТЬ 27

2.1. Задание для курсового проекта 27

2.1.1.Приведение задачи к каноническому виду 28

2.2. Нахождение начального опорного решения (НОР) 29

2.3. Нахождение оптимального решения 30

2.4. Алгоритмы и их описание 33

2.5. Описание программы 42

2.6. Описание процесса отладки программы  обработка ошибок программы 44

2.7. Инструкция пользователю 48

3.Заключение 50

4. Приложения 51

Приложение №1. Внешний вид форм 51

Приложение №2. Программный код 54

Приложение№ 3.Таблицы Excel 66

Приложение № 4.Таблицы Excel с формулами 67

Список используемой литературы: 71

Введение

Данный курсовой проект предназначен для решения задач линейного программирования.  Для этого было необходимо произвести расчеты, используя ручной метод решения задачи симплекс методом,  табличный процессор MS Excel из пакета программ Microsoft Office, а также необходимо было написать программу в среде Microsoft Visual Basic.

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

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

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

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

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

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

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

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

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

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

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

1. Необходимо осуществить математическую формализацию задачи линейного программирования. Это означает, что нужно идентифицировать управляемые переменные и цель задачи. Затем с помощью этих переменных цель и ограничения на ресурсы описываются в форме линейных соотношений.
2. После завершения формулировки задачи линейного программирования рассматриваются все допустимые сочетания переменных. Из них выбирается то, которое оптимизирует целевую функцию задачи. Если исследуемая задача содержит только две переменные, ее можно решить графически. Однако в случае исследования задачи со многими переменными необходимо прибегнуть к одному из алгебраических методов решения задач линейного программирования, для использования которых существуют пакеты прикладных программ.
3. Когда оптимальное решение получено, производится его оценка. Она включает в себя анализ задачи на чувствительность.

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

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

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

Шаг 2. Определение цели и ограничений на ресурсы.

Шаг 3. Описание цели через переменные задачи.

Шаг 4. Описание ограничений через переменные задачи

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

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

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

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

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

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

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

Базовую модель, с которой я работал в дальнейшем, формально можно представить следующим образом:

Максимизировать Z = с1х1 + с2×2 + … + сnхn.

Здесь сi – константы. Данная функция максимизируется в условиях системы m линейных ограничений:

a11х1 + а12×2 + а13×3 + … + a1nxnb1

a21х1 + а22×2 + а23×3 + … + a2nxnb2

a31х1 + а32×2 + а33×3 + … + a3nxnb3

am1х1 + аm2x2 + аm3x3 + … + amnxnbm

x10

Данная система содержит n переменных и m ограничений. Первая цифра двойных индексов коэффициентов в левой части системы ограничений соответствует номеру ограничения, вторая — номеру переменной. Например, a32 принадлежит ограничению 3 и является коэффициентом при переменной х2.

1.2.Применение процессора Microsoft Excel для расчета задач линейного программирования

Microsoft Excel — одна из программ пакета Microsoft Office, представляющая собой программируемый табличный калькулятор.

Область применения Excel широка:

• благодаря тому, что лист Excel представляет собой готовую таблицу, Excel часто используют для создания документов без всяческих расчётов, просто имеющих табличное представление (прайс-листы в магазинах, расписания);
• в Excel легко можно создавать различные виды графиков и диаграмм, которые берут данные для построения из ячеек таблиц (график снижения продаж на предприятии за указанный период);
• его могут использовать обычные пользователи для элементарных расчетов (сколько потратил за этот месяц, что/кому/когда дал/взял);
• Excel содержит многие математические и статистические функции, благодаря чему его могут использовать школьники и студенты для расчетов курсовых, лабораторных работ;
• Excel интенсивно используется в бухгалтерии – во многих фирмах это основной инструмент для оформления документов, расчётов и создания диаграмм. Естественно, он имеет в себе соответствующие функции;
• Excel может также работать как база данных.

Минимальные системные требования:

• Операционная система Microsoft® Windows® 95/98/Me/2000/XP/Vista/Seven
• Процессор Pentium® 200 МГц MMX
• 16 МБ оперативной памяти
• Разрешение экрана 800х600 с глубиной цвета 16 бит
• 16-битное звуковое устройство
• 8-скоростное устройство для чтения компакт-дисков или DVD-дисков

Excel – программируемый табличный калькулятор. Все расчеты в Excel выполняют формулы. Формулой Excel считает все, что начинается со знака «=». Если в ячейке написать просто «1+1», Excel не будет вычислять это выражение. Однако если написать «=1+1» и нажать Enter, в ячейке появится результат вычисления выражения – число 2.

После нажатия Enter формула не пропадает, ее можно увидеть снова, если сделать двойной щелчок по ячейке, или если выделить ее и нажать F2 или просто нажать Ctrl + «Апостроф». Также ее можно увидеть в панели инструментов «Строка формул», если опять же выделить ячейку.

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

Ниже я представлю пример решения задачи линейного программирования в Microsoft Excel с использованием модуля «Поиск решения»

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

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

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

Целевая функция 

S = 60*x1+70*x2+120*x3+130*x4         → max

Система ограничений

1*x1+1*x2+1*x3+1*x4 ≤ 16

6*x1+5*x2+4*x3+3*x4 ≤ 110

4*x1+6*x2+10*x3+13*x4 ≤ 150

x1, x2, x3, x4 ≥ 0 – целые

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

Рис 1 Модуль «Поиск решения» программы MS Excel

Далее, переходим к решению. Выбираем в меню «Сервис | Поиск решения». Открывается диалоговое окно «Поиск решения». Здесь указывается ячейки целевой функции, переменных и устанавливаются ограничения исходя из системы ограничений. Можно начать решение, или установить «параметры» решения (рис.1.2).

Источник: http://referat911.ru/Matematika/linejnoe-programmirovanie/184121-2300522-place1.html

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

Лабораторнаяработа № 1

Цель работы:изучение современных программныхсредств решения задачи линейногопрограммирования; практическое решениезадач линейного программированияграфическим методом, симплекс-методоми средствами программыMicrosoftExcel; программная реализациясимплекс-метода на языке программированиявысокого уровня.

1. Теоретическая часть

Для решения задачлинейного программирования в программеMicrosoftExcelимеется надстройка Поискрешения,обращениек которой производится из меню Сервис.

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

Рис. 1

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

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

Постановка задачи

Предприятиеизготавливает и реализует три видапродукции – P1,Р2и Р3.Для производства продукции используютсятри вида ресурсов – комплектующиеизделия, сырье и материалы. Запасыресурсов и их расход на изготовлениеединицы продукции каждого вида приведеныв табл. 1.

Таблица 1

Виды ресурсов	Расходы ресурсов на 1 ед. продукции	Запасы ресурсов, ед.
P1	P2	P3
Комплектующие изделия	4	6	8	3120
Сырье	2	8	10	3000
Материалы	6	9	4	3150

Прибыль от реализацииединицы продукции каждого вида составляет240, 210 и 180 денежных единиц для P1,Р2и Р3соответственно.

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

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

Обозначим переменнымиx1,x2и x3искомые объемы производства продукциивидов P1,Р2и Р2,а через F– прибыль предприятия. Тогда математическаяпостановка представленной задачипринимает следующий вид.

Определить значенияпеременных x1,x2и x3,для которых достигается максимум целевойфункции

F= 240 x1 + 210 х2+ 180 x3

при ограничениях:

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

x1≥ 0; x2≥ 0; x3≥ 0.

Порядок оптимального решения задачи

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

Шаг 1.Исходные данные задачи записываютсяна рабочем листе электронной таблицы.Один из вариантов показан на рис. 2.

Рис. 2

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

Для этого начальные значениянекоторых или всех переменных могутбыть заданы вручную. В данном примередля их хранения используются ячейки$B$2,$C$2и $D$2.

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

Шаг 2.В ячейку E3вводится формула

=СУММПРОИЗВ(В3:D3;$B$2:$D$2)

для вычислениятекущего значения целевой функции,которая находит сумму попарныхпроизведений ячеек (В3:D3)с коэффициентами при переменных ввыражении целевой функции на ячейки($B$2:$D$2)с текущими значениями переменных.

Шаг 3.Чтобы задать ограничения решаемойзадачи, в ячейки E5,E6и E7копируется формула из ячейки E3.После этого в указанных ячейках должныбыть получены формулы, представленныев табл. 2.

Таблица2

Ячейка	(формула)
E5	=СУММПРОИЗВ(В5:D5; $B$2:$D$2)
E6	=СУММПРОИЗВ(В6:D6; $B$2:$D$2)
E7	=СУММПРОИЗВ(В7:D7; $B$2:$D$2)

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

Рис. 3

В поле Установитьцелевую ячейкуокна «Поиск решения», показанного нарис. 3, долженпоявиться адрес ячейки с формулойцелевой функции (в данном примере этоячейка $E$3).

Затем в этом окне(рис. 3) заполняются следующие поля этогоокна:

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

– в поле Изменяяячейкиуказываетсядиапазон ячеек со значениями переменныхзадачи, выделяемый на рабочем листеэлектронной таблицы (в примере этоячейки $B$2:$D$2);

– в поле Ограничениязадаютсяограничения исходной задачи. Для этогокурсор устанавливается в поле вводаограничений и нажимается кнопка Добавить.В результатевыводится диалоговое окно «Добавлениеограничения», показанное на рис. 4.

Рис. 4

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

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

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

Рис. 5

После нажатиякнопки Добавитьв окне«Добавление ограничения»(или кнопкиОКдлявводапоследнего ограничения) данное ограничениепопадает в список ограничений решаемойзадачи. С помощью кнопок Удалитьи Изменитьможно удалятьвыделенные в списке ограничения иливносить в них исправления.

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

Шаг 5.После заполнения всех полей окна «Поискрешения» нажимается кнопка Параметры(рис. 3),которая открывает диалоговое окно«Параметры поиска решения», показанноена рис. 6.

Рис. 6

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

Шаг 6.Задав необходимые параметры в окне«Параметрыпоиска решения»,следует нажать на кнопку Выполнитьдля поискарешения задачи (рис. 3) вокне «Поиск решения».Если решение найдено, то на экранвыводится окно с соответствующимсообщением (рис. 7).

Рис. 7

Полученныерезультаты отображаются на рабочемлисте электронной таблицы, как этопоказано на рис. 8. В частности, значенияпеременных – в ячейках $B$2:$D$2,значение целевой функции – в ячейкеE3.

Рис. 8

Таким образом,получено оптимальное решение исходнойзадачи в виде вектора ,где,и,для которого значение целевой функцииFмаксимально и составляет F*= 129825.

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

Для сохранениярезультатов в виде отчетов необходимопредварительно в поле Типотчетавыделитьтребуемые типы отчетов (рис. 7).

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

Отчет по результатамдля рассмотренной задачи показанна рис. 9.

Рис. 9

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

Состояниеограничений (графа Статус)характеризует расположение точкив области допустимых решений. ГрафаРазницапоказывает разности между значениямилевых и правых частей ограничений(невязки).

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

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

В рассмотренной задаче ограничения (1)и (3) соответствуют комплектующим изделиями материалам, которые являются дефицитнымиресурсами. Ограничение (2) является несвязанным, т.е. не влияет на оптимальныйплан производства продукции по критериюмаксимальной прибыли.

Это означает, чтовторой ресурс (сырье) не использован вобъеме 292,5 ед.

Вотчете по устойчивости (рис.

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

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

Рис. 10

В графе Нормированнаястоимостьэлемент во второй строке (-150) показывает,на сколько уменьшится значение функции,если в решении переменную x2увеличить на единицу.

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

Вотчетепо пределам(рис.

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

В частности, еслиx1= 0, а x2и x3остаются без изменений, то F= 2400+ 2100+ 180191,25= 34425; при x3= 0 и неизменных x1и x2получим F= 240397,5+ 2100+ 1800= 95400.

Рис. 11

Источник: https://StudFiles.net/preview/6129199/