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

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

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

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

(1.2)

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

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

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

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

,

где a₁₁ - количество единиц ресурсов вида 1 на первом предприятии; a₁₂ - количество единиц ресурсов вида 1 на втором предприятии и т.п.;b₁ - общий объем ресурсов вида 1(для всех предприятий); x₁, x₂ и т.д. - искомое количество предприятий типов 1, 2 и т.д.

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

,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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