Курсовая работа (т): Решение типовых задач линейного программирования в табличном процессоре MS Excel

Рисунок 6 - Заполненная форма

) выделить ячейку функции цели для запуска команды «Поиск решения»;

) выбрать вкладку «Данные», в ней выбрать закладку «Анализ», затем команду «Поиск решения»;

) в открывшемся диалоговом окне, представленном на рисунке 7, установить:

Рисунок 7 - Диалоговое окно команды «Поиск решения»

-       в группе «Равной»переключатель на максимальное значение;

-       в поле «Установить целевую ячейку»ввести адрес ячейки G9,уже содержащей формулу для расчета значения функции цели;

-       в поле «Изменения ячейки»указать ссылки на изменяемые ячейки В10 и С10, содержащие неизвестные  и ;

-       в поле «Ограничения»нужно задать необходимые ограничения, для этого необходимо нажать кнопку «Добавить»;

) в результате открывается диалоговое окно, рисунок 8, «Добавление ограничения»:

Рисунок 8- Диалоговое окно «Добавление ограничения»

-       в поле «Ссылка на ячейку»указать адрес левой части первого ограничения F4. Из списка выбрать нужный оператор, означающий «не более» (<=);

-       в поле «Ограничения»указать адрес правой части первого ограничения Н4. Нажать кнопку «ОК»,

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

Диалоговое окно «Поиск решения», рисунок 9, после ввода исходных данных имеет вид:

Рисунок 9 - Форма после ввода исходных данных

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

Рисунок 10 - Результаты работы команды «Поиск решения»

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

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

.4 Решение задачи о раскрое в среде MS Excel

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

Для изготовления металлоконструкций используется заготовки длиной 70, 100 и 120 см. Заготовки производят из металлических стержней длиной 220 см. Для выполнения всего заказа требуется изготовить 102 стержня длиной 70 см, 120 стержней длиной 100 см и 80 стержней длиной 120 см.Какое минимальное количество материала необходимо использовать, чтобы выполнить заказ?

Решение:

Сначала нужно определить все возможные способы раскроя материала. Для наглядности представим эти данные в таблице 6:

Таблица 6 - Способы раскроя материала

Таким образом, получаем пять различных способов раскроя материала.

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

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

Система ограничений примет вид:

Очевидно, что количество заготовок () должно быть целым числом и не может быть отрицательным.

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

Рисунок 11 -Форма для ввода данных

Ячейка G7 зарезервирована под функцию цели, позже в нее будет записана формула для нахождения минимального количество стержней длиной 220 см. В ячейках диапазона B3:F5, размещена таблица рациональных способов раскроя материала, в диапазоне ячеек B6:F6 - величина отходов для каждого способа раскроя, а в G3:G5 - требуемое количество стержней заготовок различной длины. Ячейки B7:F7 заполнятся автоматически после выполнения команды «Поиск решения», и будут равны количеству заготовок получаемых при каждом способе раскроя.

В ячейках H3:H5необходимо указать формулы для расчета фактического количества стержней разной длины. В ячейке H3 формула будет иметь вид =$B$7*B3+$C$7*C3+$D$7*D3+$E$7*E3+$F$7*F3, ячейки H4 и H5 заполняются аналогично (для этого можно использовать автозаполнение т.к. в формуле использованы абсолютные ссылки).

В ячейку G7 нужно занести целевую функцию, вычисляющую суммарное количество единиц материала, то есть необходимое количество стержней длиной 220 см. Таким образом, в данной ячейке будет введена формула: =B7+C7+D7+E7+F7.

Необходимо воспользоваться надстройкой «Поиск решения». Вызвать ее можно выбрав вкладку «Данные», закладку «Анализ». В диалоговом окне «Поиска решения», рисунок 12, вводим ячейку целевой функции $G$7, диапазон изменяемых ячеек:$B$7:$F$7, устанавливаем переключатель «Равной минимальному значению».

Рисунок 12 - Диалоговое окно надстройки «Поиск решения»

В поле «Изменяя ячейки» задается диапазон подбираемых параметров - $B$7:$F$7.

Также нужно добавить ограничения:

-       количество заготовок должно быть целым числом ($B$7:$F$7=целое);

-       количество не должно быть отрицательным числом ($B$7:$F$7>=0);

-       фактическое количество стержней различной длины, требуемое для выполнения заказа, должно быть не менее необходимого количества ($H$3:$F$5>=$G$3:$G$5).

В результате выполнения надстройки «Поиск решения» получаем минимальное количество материала необходимое для выполнения заказа в ячейке G7 - 134 единицы материала, рисунок 13:

Рисунок 13 - Результат выполнения надстройки «Поиск решения»

Так же на рисунке 13 видно, что для этого используются только 3 способа раскроя материала(1 способ - 80 единиц, 3 способ - 20 единиц и 5 способ - 34 единицы).

.5 Решение транспортной задачи в среде MS Excel

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

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

Существует четыре пункта производства продукта A₁, A₂, A₃, A₄производственные мощности которых составляют 30, 40, 50 и 30 единиц. Данный товар востребован в трех пунктах потребления B₁, B₂, B₃, потребности которых составляют 40, 60 и 50 единиц. Затраты на поставку единицы товара (у.д.е.) от пунктов производства до пунктов назначения заданы матрицей:

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

Решение:

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

Система ограничений примет вид:

По аналогии с предыдущими задачами, создаем форму ввода и заполняем ее исходными данными, рисунок 14:

Рисунок 14 - Форма для ввода данных к решению транспортной задачи

Для функции цели зарезервирована ячейка H9, для переменных  - ячейки B4:B7, D4:D7, F4:F7, в них будут занесены результаты решения задачи. В ячейки B9, D9, F9 необходимо ввести формулы для вычисления левых частей уравнений-ограничений по заявкам. Для потребителя B₁ ограничение имеет вид уравнения:

.

Следовательно, в ячейку B9 нужно записать формулу: =СУММ(В4:В7).

Формулы в ячейках D9 и F9 задаются таким же образом. В ячейки I4:I7 введем формулы для вычисления левых частей уравнений по запасам.

Для поставщика A₁ уравнение имеет следующий вид:

,

что соответствует формуле в ячейке I4:= B4 + D4 + F4. Аналогично задаются формулы для ячеек I5, I6 и I7.

Для вычисления значения целевой функции

В ячейку H9 запишем формулу: = СУММПРОИЗВ(C4:C7; B4:B7) + +СУММПРОИЗВ(E4:E7;D4:D7)+СУММПРОИЗВ(G4:G7; F4:F7).

Необходимо воспользоваться надстройкой «Поиск решения». Вызвать ее можно выбрав вкладку «Данные», закладку «Анализ». В диалоговом окне «Поиска решения», рисунок 15, вводим ячейку цели функции $H$9, диапазон изменяемых ячеек: $B$4:$B$7;$D$4:$D$7;$F$4:$F$7.

Рисунок 15 - Ввод уравнений-ограничений для транспортной задачи

Целевая функция считается равной минимальному значению. Введем уравнения-ограничения по заявкам:B9=B8; D9=D8; F9=F8; по запасам:I4:I6=H4:H6. Так же нужно указать неотрицательность переменных:В4:B7>=0;D4:D7>=0;F4:F7>=0.

В результате выполнения программы «Поиск решения»получим на экране в ячейках B4:B6; D4:D6; F4:F6 оптимальный план перевозок, а в ячейке Н9 - минимальную общую стоимость за все перевозки, рисунок 16:

Рисунок 16 - Результат работы надстройки «Поиск решения»

Таким образом, в то время как .

ЗАКЛЮЧЕНИЕ

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

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

Основными используемыми способами решения задач линейного программирования являются графический и симплекс-метод. Также для задач подобного рода найти решение можно с помощью надстройки «Поиск решения» табличного процессора Excel2007 из пакета прикладных программ Microsoft Office.

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

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1.     Бродецкий, Г.Л. Экономико-математические методы и модели в логистике. Процедуры оптимизации: учебник / Г.Л. Бродецкий, Д.А. Гусев. - М.: Академия, 2012. - 281 с.

2.      Васильев, А.Н. Финансовое моделирование и оптимизация средствами Excel 2007: учеб. пособие.-СПб.: Питер, 2009.- 319 с.

.        Введение в анализ «что если» [Электронный ресурс]. - Режим доступа:http://office.microsoft.com/ru-ru/excel-help/HA010342628.aspx (дата обращения 20.04.2014)

.        Введение в исследование операций [Электронный ресурс]. - http://ru.convdocs.org/docs/index-159945.html?page=9 (дата обращения 18.04.2014)

.        Задача о раскрое материалов[Электронный ресурс]. - Режим доступа: http://edu.nstu.ru/courses/mo_tpr/files/3.1.6.html (дата обращения 18.04.2014)

.        Задачи оптимизации в Excel[Электронный ресурс]. - Режим доступа: http://exsolver.narod.ru/LM/LM_material.html (дата обращения 19.04.2014)

.        Змеев, О.А. Исследование операций [Электронный ресурс]. - Режим доступа: http://abc.vvsu.ru/Books/ebooks_iskt/%D0%AD%D0%BB%D0%B5% D0%BA%D1%82%D1%80%D0%BE%D0%BD%D0%BD%D1%8B%D0%B5%D1%83%D1%87%D0%B5%D0%B1%D0%BD%D0%B8%D0%BA%D0%B8/%D0%98%D1%81%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5%20%D0%BE%D0%BF%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B9/fmi.asf.ru/vavilov/index.htm (дата обращения 20.04.2014)

.        Интерактивный обучающий курс. Математика [Электронный ресурс]. - Режим доступа: http://math.immf.ru (дата обращения 18.04.2014)

.        Косарева, А.С., Ляпина, Е.А. Использование метода линейного программирования в процессе финансового планирования и бюджетирования // Современная наука: актуальные проблемы теории и практики. - 2013. -№3-4. - С.20-23.

.        Красс, М.С. Математические методы и модели для магистрантов экономики: учеб. пособие. 2-е изд., дополненное / М.С. Красс, Б.П. Чупрынов - СПб.: Питер, 2013.- 486 с.