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

 

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

. СУЩНОСТЬ ЗАДАЧИ ОПТИМИЗАЦИИ

.1 Немного истории

.2 Основные понятия

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

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

.1 Задача о рационе питания (задача о диете)

.2 Задача о составлении плана производства

.3 Задача о раскрое материалов

.4 Транспортная задача

. ПРИКЛАДНЫЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

.1 Характеристика программного средства

.2 Решение задачи о рационе питания в среде MS Excel

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

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

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

ЗАКЛЮЧЕНИЕ

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

ВВЕДЕНИЕ

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи:

-изучить и раскрыть необходимый теоретический материал;

-провести анализ некоторых типовых задач линейного программирования;

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

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

-найти оптимальное решение задач с помощью средств табличного процессора.

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

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

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

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

1. СУЩНОСТЬ ЗАДАЧИ ОПТИМИЗАЦИИ

1.1 Немного истории

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

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

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

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

Математическое программирование - это раздел математики, занимающийся анализом многомерных экстремальных задач управления и планирования и разработкой теории и численных методов их решения [8].

Линейное программирование является наиболее изученным разделом математического программирования. Термин линейного программирования появился в работах Т. Купманса и Дж. Данцига в 1951 г[4].

1.2 Основные понятия

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

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

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

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

Модель задачи математического программирования включает в себя:

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

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

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

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

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

Модели линейного программирования широко используются при оптимизации процессов практически во всех отраслях:

-при составлении плана производства;

-при разделении заданий и отдельных технологических процессов по исполнителям;

-при нахождении оптимального набора изготавливаемой продукции;

-при распределении работ по временным промежуткам;

-при определении маршрутов грузопотоков между потребителями и поставщиками;

-при составлении плана товарооборота и порядка его распределении и т. д.

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

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

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

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

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

(1.1)

где xj- неизвестные переменные, содержащие решение поставленной задачи;ij и bj- известные постоянные величины, характеризующие условия задачи.

Целевая функция задается в виде:

(1.2)

где cj- постоянные коэффициенты стоимости.

Ограничения могут быть, заданы не только в виде уравнений, но и в виде системы неравенств. В данном случае, для того чтобы привести систему неравенств к виду (1.1), нужно в каждое линейное ограничение ввести добавочные неотрицательные неизвестные: xn+1, xn+2, …,xn+m.

Общая математическая формулировка задачи соответствует условиям (1.1) и (1.2).

Первая строка системы уравнений (1.1) соответствует выражению:

,

где a11 - количество единиц ресурсов вида 1 на первом предприятии; a12 - количество единиц ресурсов вида 1 на втором предприятии и т.п.;b1 - общий объем ресурсов вида 1(для всех предприятий); x1, x2 и т.д. - искомое количество предприятий типов 1, 2 и т.д.

Вторая строка системы уравнений (1.1) содержит аналогичные величины для ресурсов вида 2 и т.д. Функция цели соответствует формуле (1.2). Требуется обратить в минимум величину

,

где cj- показатель, характеризующий издержки предприятий.

Пусть m - суммарное число разных типов ресурсов, которые есть у собственника, а n - число видов предприятий, между которыми эти ресурсы распределены. При этом известно, какое количество однородных ресурсов различного вида (i=1, 2, …,m) может быть реализовано на каждом из предприятий данного типа (j=1,2,…,n), а также общее количество ресурсов данного вида (bi). Известно также относительное значение издержек на каждом из предприятий(cj).

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

Таким образом, особенностями линейного программирования являются:

-линейная зависимость функции цели;

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

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

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

Основные виды задач линейного программирования:

-задача об ассортименте;

-задача о диете (рационе питания, о смесях);

-транспортная задача;

-задача об оптимальном использовании имеющихся мощностей;

-задача о назначениях и др.

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

.1 Задача о рационе питания (задача о диете)

Задача о смесях появляется при составлении рациона питания животных, удовлетворяющего конкретным медицинским требованиям так, чтобы затраты на «меню» были сведены к минимуму [13].

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

Таблица 1 - Содержание нужных веществ в каждом виде продукта

Получается, что величина aij это количество i-го элемента, присутствующего в единице веса j-го продукта. Матрица называется матрицей питательности.

Вектор решения для рациона питания должен показать, какое количество xi i-го продукта должно содержаться в меню«исследуемого» животного за день (месяц, квартал, год). Он означает, что за определенный промежуток времени животное должно быть обеспеченоx1единиц первого продукта, x2 единиц второго, …, xn единиц n-го продукта.

Какие же требования могут быть предъявлены к рациону? Выполнение конкретных медицинских требований. Они состоят в том, что за определенный срок животное должно получить не менее необходимого количества каждого элемента. Обозначим через bj, то минимально необходимое количество j-го элемента, которое должно получить животное. В таком случае, рацион питания должен соответствовать полученным ограничениям (2.1).

(2.1)

Тогда стоимость всей диеты будет составлять:

(2.2)

где - цена единицы веса i-го продукта.

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

(2.3)

Таким образом, очевидно что:

-реальная задача приобрела строгую математическую форму;

-функция цели (стоимость питания) является линейной функцией;

-ограничения на значения переменных x1, x2, …, xn имеют вид системы линейных неравенств.

.2 Задача о составлении плана производства

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

Для выпуска данных товаров необходимо использовать различные материальные ресурсы. Пусть количество этих ресурсов будет m; обозначим их через

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

Таблица 2 - Технологическая матрица

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

(2.4)

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

(2.5)

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

.3 Задача о раскрое материалов

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

Нередко поиск оптимального способа раскроя осуществляется в два этапа.

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

На II этапе решаются задачи рациональных способов раскроя.

-Нахождение рациональных способов раскроя материала

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

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

Пусть- индекс типа заготовки ();

- номер способа раскроя единицы материала ();

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

Математически представить определение рационального способа раскроя материала можно в таком виде: способ раскроя называется рациональным, если для любого другого способа раскроя из соотношений , следуют соотношения [5].

-Определение интенсивности использования рациональных способов раскроя.

Обозначения:

- индекс материала ();

- номер типа заготовки ();

- индекс способа раскроя единицы материала();

- количество заготовок вида , полученных при раскрое единицы -го материала -м способом;

- количество заготовок вида в комплекте, отправляемому заказчику;

- количество материала-го вида;

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

- величина отхода, полученного при раскрое единицы -го материала по -му способу;

- число комплектов заготовок различного вида.

Имеется несколько типов моделей задач о раскрое материала:

-Модель I(раскрой, с минимальным расходом материалов):

где (2.6) - функция цели (минимум количества используемых материалов);

(2.7) - система ограничений, определяющих количество заготовок, необходимое для выполнения работы;

(2.8) - условия неотрицательности переменных.

Модель II (раскрой, с минимальными отходами материалов):

где (2.9) - функция цели (минимум отходов при раскрое материалов);

(2.10) - система ограничений, определяющих количество заготовок, необходимое для выполнения заказа;

(2.11) - условия неотрицательности переменных.

-Модель III (раскроя материала с учетом комплектации):

где (2.12) - функция цели (максимум комплектов, включающих заготовки различных видов);

(2.13) - ограничения по количеству материалов;

(2.14) - система ограничений, определяющих количество заготовок, необходимое для формирования комплектов;

(2.15) - условия неотрицательности переменных.

Рассмотрим несколько подробнее задачу о раскрое материала в общем виде.

Пусть на обработку поступает a единиц сырьевого материала одного вида (например, a листов картона одинаковых размеров). Из них необходимо изготовить комплекты, в каждый из которых входит n видов изделий в количестве, пропорциональном числам Имеется m способов обработки данного материала, то есть известны величины определяющие количество единиц j-х заготовок при i-м способе раскроя [18].

Установить план раскроя, при котором количество комплектов будет максимально. Согласно условиям задачи имеем, таблицу 3:

Таблица 3 -Способы раскроя

Вид изделия Способ раскрояm

Пусть xi- количество единиц сырьевого материала, раскраиваемого i-м вариантом

Тогда количество изделий 1-го вида равно:

Принимая во внимание условие комплектности, имеем:

где y - количество комплектов.

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

.

Очевидно, (на раскрой поступает a единиц сырьевого материала), а также

Цель задачи - максимизировать количество комплектов:

Итак, приходим к математической модели задачи о раскрое:

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

.4 Транспортная задача

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

Пусть имеется m пунктов производства однородного продукта (добыча руды в карьерах, сборка бытовой техники, изготовление кондитерских изделий и др.) и n пунктов потребления этого продукта. Мощности пунктов производства составляют единиц однородного продукта, а потребности каждого j-го пункта потребления равны единиц. Известны затраты на перевозку едиицы продукта от i-го поставщика j-му потребителю. Составить такой план перевозок, при котором суммарные затраты на все перевозки были бы наименьшими. Пусть спрос и предложение совпадают, то есть

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

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

Матрицу называют матрицей затрат (тарифов).

Составим таблицу 4, в которую внесем все исходные данные и перевозки xij.

Таблица 4 - Транспортная таблица

c2n

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

которую необходимо минимизировать при ограничениях: (весь продукт из каждого i-го () пункта должен быть, вывезен полностью),(спрос каждого j-го () потребителя должен быть, полностью удовлетворен).

Из условия задачи следует, что все .

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

3. ПРИКЛАДНЫЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

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

.1 Характеристика программного средства

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

Надстройка «Поиск решения» позволяет найти оптимальное (максимальное или минимальное) значение для формулы <javascript:AppendPopup(this,'xldefFormula_2_2')>, содержащейся в целевой ячейке. Поиск решения» работает с диапазоном ячеек, связанных с формулой в целевой ячейке. Чтобы получить оптимальный результат по формуле из целевой ячейки, «Поиск решения» изменяет значения в ячейках, выбранных как изменяемые. Для конкретизации значений применяются ограничения (система неравенств), которые могут ссылаться на другие ячейки (группы ячеек), влияющие на формулу для ячейки с записанной целевой функцией[3].

Именно этими возможностями обладают известные табличные процессоры Microsoft Office Excel 2007 и Open Office Calc. В отличие от Open Office Calc MS Excel является более распространенным и привычным для обычного пользователя, имеет более широкий спектр поддерживаемых форматов файлов. При использовании MS Excel возникновение несовместимости с другими программы в разы меньше, чем у Open Office. Так же в MS Excel есть встроенный язык программирования - Visual Basic for Applications. Плюс ко всему вышеперечисленному данное программное средство обладает более функциональным и интуитивно понятным интерфейсом.

Надстройка «Поиск решения» в Open Office Calc немногим отличается от похожей надстройки в MS Excel. В последнее время эти два табличных редактора уже стали практически идентичны по функциональному набору. Хотя стоит признать, что Calc все же уступает конкуренту именно в наборе «Пакета анализа»[19].

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

.2 Решение задачи о рационе питания в среде MS Excel

линейное программирование табличный процессор

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

Необходимо составить наименее затратный рацион питания поросят, содержащий необходимое количество витаминов А, C и D. Пищевая ценность рациона питания (в калориях) должна быть не менее необходимой. Данная смесь изготавливается из двух видов кормов - К1 и К2. Причем, корма вида K1 в рационе не должно быть использовано более 0,5 кг. Аналогично для корма K2 - не более 0,85 кг. Исходные данные для дальнейших расчетов приведены в таблице 5.

Таблица 5 - Содержание витаминов в кормах

Содержание в 100 г К1, мгСодержание в 100 г К2, мгПотребность, мгВитамин А101060Витамин D4010100Витамин С201080Энергетическая ценность, калории100200800Стоимость 100 г, ден. ед.57

Решение:

Построим математическую модель. За обозначим количество корма К1, аналогично за - объем К2.Исходя из условия задачи и - неотрицательные значения. Целевая функция будет стремиться к минимуму т.к. расходы, с учетом всех необходимых условий, должны быть как можно меньше.

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

Из названий столбцов таблицы 5 ясно, что порции кормов составляют по 100 грамм, а ограничение по количеству в условии задачи дано в килограммах. Следовательно, необходимо их привести в ту же систему, что и остальные неравенства. 0,5 кг это 500 г, а 0,85 кг - 850 г. Таким образом, .

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

Задачу линейного программирования можно решить как графически, так и симплекс-методом. В данном случае, воспользуемся пакетом прикладных программ Microsoft Office, в частности MS Excel, надстройкой «Поиск решения».

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

Рисунок 1 - Форма ввода данных в задаче о диете

Ячейки B3 и C3 отведены для переменных , пока они обнулены, но в дальнейшем они будут являться изменяемыми ячейками т.к. именно эти значения влияют на функцию цели. В ячейку E3 введена формула для целевой функции, которая будет стремиться к минимальному значению. В диапазоне ячеек F7:F12 можно применить математическую функцию «Сумму произведений» (СУММПРОИЗВ). Первый массив для всех неравенств, следовательно, его нужно отметить знаком «$», как абсолютную ссылку, чтобы при копировании в другие ячейки адрес этих ячеек не изменялся. Использование данной функции представлено на рисунке 2.

Рисунок 2 - Введение формул

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

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

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

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

Таким образом, минимальное значение функции цели , то есть для составления оптимального суточного рациона питания, с минимальными затратами и содержанием всех витаминов в полном объеме, нужно взять 400 грамм корма К1и 200 грамм корма К2. При этом стоимость данных витаминных добавок будет составлять 34 денежные единицы.

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

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

Необходимо произвести изделия двух типов. Для их изготовления имеется 120 кг алюминия. На изделиеI типа расходуется 4 кг алюминия, а на изделиеII типа - 2 кг. Составить план выпуска изделий, обеспечивающий получение наибольшей прибыли от продажи изделий. Стоимость изделия I типа установлена 4условные денежные единицы, а изделия II типа - 5условных денежных единиц, причем изделий I типа требуется изготовить не более 35, а изделий II типа - не более 10.

Решение:

Обозначим количество изделийI типа как , а количество, производимых по плану, изделий II типа -.

Логично предположить, что Прибыль от продажи изделий составит

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

Также при составлении оптимального плана производства нельзя не учитывать ограничения по имеющемуся ресурсу. При производстве изделий I типа расходуется (кг). В то время, на производство изделий II типа используется (кг) алюминия.Таким образом, суммарный расход алюминия составляет(кг). Данная величина не должна превышать запасы алюминия в количестве 120 кг. В итоге получаем неравенство:

Изделий I типа в плане выпуска продукции должно быть не более 35 штук, то есть. Аналогично для изделий II типа: , так как по условию этих изделий должно быть не более 10.

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

Решим задачу линейного программирования с помощью программы MSExcel.

Для этого необходимо выполнить следующие шаги:

) создать форму для ввода исходных данных задачи, изображенную на рисунке 5:

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

Текст в данной форме непосредственно на ход решения задачи не оказывает никакого влияния. Данные комментарии делают решение задачи более понятной. Для неизвестных и зарезервированы ячейкиВ10 и С10. В них после решения задачи будут внесены полученные значения. Значение функции цели Z будет зафиксировано в ячейке G9;

2) ввести исходные данные. В диапазон В4:С6 вводим коэффициенты при переменных в системе ограничений: «Первое» - коэффициенты 1 и 0,«Второе» - 0 и 1,«Третье» - 4 и 2.В диапазоне ячеек D4:D6 и Н4:Н6 заносим значения свободных членов системы ограничений: 35, 10 и 120. В диапазон ячеек В11:С11 - коэффициенты целевой функции Z, то есть 4 и 5;

3) ввести формулы для расчета целевой функции и системы ограничений. Для вычисления значений функции цели в ячейкуG9необходимо ввести формулу = В11*В10 + С11*С10.Здесь вместо коэффициентов 4 и 5 записаны их адреса В11 иС11, а вместо переменных и соответствующие адреса В10 иС10.

Введем формулы левых частей системы ограничений в диапазоне ячеек F4:F6. Сначала в ячейку F4 запишем выражение = В4*$B$10 + C4*$C$10, соответствующее алгебраическому выражению (1· + 0·). Этолевая часть первого ограничения системы неравенств. Абсолютная адресация ячеек ($C$10)необходима, так как абсолютный адрес при перемещении (копировании) не изменяется. Для создания формул в ячейкахF5 и F6 воспользуемся возможностью заполнения формулы в ячейке F4 путем ее копирования. В результате заполнения в ячейке F5 будет записана формула = В5*$B$10 + C5*$C$10, что соответствует выражению - (0· +1·), а в ячейке F6:= B6*$B$10 + C6*$C$10, что соответствует выражению (4· + 2·). В результате вводавсех имеющихся данных таблица примет вид, представленный на рисунке 6:

Рисунок 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 - Способы раскроя материала

Виды заготовокСпособы раскроя из стержня 220 смIIIIIIIVV70 см01013100 см10210120 см11000Отходы, см030205010

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

Обозначим через - количество единиц материала, раскраиваемых по -му способу (интенсивность использования способа раскроя), то есть - количество материала, раскраиваемого по способу 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 единиц товара, производится поиск оптимального решения транспортной задачи.

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

Существует четыре пункта производства продукта A1, A2, A3, A4производственные мощности которых составляют 30, 40, 50 и 30 единиц. Данный товар востребован в трех пунктах потребления B1, B2, B3, потребности которых составляют 40, 60 и 50 единиц. Затраты на поставку единицы товара (у.д.е.) от пунктов производства до пунктов назначения заданы матрицей:

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

Решение:

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

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

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

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

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

.

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

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

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

,

что соответствует формуле в ячейке 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 с.

.Введение в анализ «что если» [Электронный ресурс]. - Режим доступа:#"justify">.Введение в исследование операций [Электронный ресурс]. - #"justify">.Задача о раскрое материалов[Электронный ресурс]. - Режим доступа: #"justify">.Задачи оптимизации в Excel[Электронный ресурс]. - Режим доступа: #"justify">.Змеев, О.А. Исследование операций [Электронный ресурс]. - Режим доступа: #"justify">.Интерактивный обучающий курс. Математика [Электронный ресурс]. - Режим доступа: #"justify">.Косарева, А.С., Ляпина, Е.А. Использование метода линейного программирования в процессе финансового планирования и бюджетирования // Современная наука: актуальные проблемы теории и практики. - 2013. -№3-4. - С.20-23.

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

.Линейное программирование [Электронный ресурс]. - Режим доступа: #"justify">.Макаров, В.И. Экономико-математические методы и модели. Задачник : учеб. пособие. - М.: КноРус, 2009. - 208 с.

.Методы линейного программирования [Электронный ресурс]. - Режим доступа: #"justify">.Орлова, И.В. Экономико-математические методы и модели: компьютерное моделирование : учебное пособие для вузов/ И. В. Орлова, В. А. Половников. -2-е изд., испр. -М.: Вузовский учебник, 2010.-365 с.

.Примеры решения задач симплексным методом в Excel[Электронный ресурс]. - Режим доступа: #"justify">.Просветов Г.И. Математические методы в логистике: задачи и решения: учебно-практическое пособие. - 2-е изд., доп. -М.: Альфа-Пресс, 2009. -303с.

.Решение задач линейного программирования в Excel [Электронный ресурс]. - Режим доступа: #"justify">.Решение задач оптимизации в среде MS Excel[Электронный ресурс]. - Режим доступа: #"justify">.Свободный поиск. Поиск решения в OpenOffice.org Calc[Электронный ресурс]. - Режим доступа: http://mxl4.net/blog/2009/01/svobodnyj-poisk.html(дата обращения 18.04.2014).

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ . СУЩНОСТЬ ЗАДАЧИ ОПТИМИЗАЦИИ .1 Немного истории .2 Основные понятия .3 Постановка задачи линейного программирования .

Больше работ по теме: