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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ -

УЧЕБНО-НАУЧНО-ПРОИЗВОДСТВЕНЫЙ КОМПЛЕКС»

ТЕХНОЛОГИЧЕСКИЙ ИНСТИТУТ

имени Н.Н. Поликарпова

ФАКУЛЬТЕТ СРЕДНЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Кафедра: «Вычислительной техники и информационных технологий»

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

Студент Яловик Ярослав Леонидович

Специальность 230105 «Программное обеспечение вычислительной техники и автоматизированных систем».

Преподаватель Кирюхина Елена Николаевна

Орел,2012

Содержание

• Введение
• 1. Постановка задачи
• 2. Основные теоретические сведения
• 3. Построение математической модели
• 4. Решение задачи симплекс-методом
• 5. Решение задачи графическим методом
• 6. Решение задачи в EXCEL
• Заключение
• Список литературы

Введение

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

С помощью различных методов можно решать все виды задач.

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

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

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

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

Название оборудования	Затраты времени на обработку изделия	Общий фонд рабочего времени
	A	B
Фрезерное	3	1	75
Токарное	1	1	30
Сварочное	1	4	84
Прибыль	3	4

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

2. Основные теоретические сведения

Алгоритм симплекс-метода:

1) Определить число и состав базисных и свободных переменных.

2) Выразить базисные переменные через свободные переменные.

3) Выразить целевую функцию через свободные переменные.

4) Построить начальную симплекс-таблицу.

5) Проверить решение на оптимальность: если в F-строке (кроме С0) все Сj0, то получено оптимальное решение: X=(B1,...,Bm,0,...,0), F=C0. Если же существует Cj<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.

6) Проверить существование решения: рассмотрим все столбцы, у которых Сj<0, если существует хотя бы один столбец, у которого все коэффициенты Ai,j<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу.

7) Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением Сj (пусть это k-й столбец)

8) Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. Ai,k>0; для всех этих элементов находим отношение Bi/Ai,k и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменная Xi выводится из базиса; при нескольких одинаковых отношениях берем любую строку; элемент Ai,k называется разрешающим элементом.

9) Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных Xi на Xk; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).

10) После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.

3. Построение математической модели

Пусть X₁ - первый вид продукции, a X₂ - второй вид продукции. Получаем следующие уравнения:

3Х₁ + Х₂ ? 75;

Х₁ + Х₂ ? 30;

Х₁ + 4Х₂ ? 84;

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

Z(X) = 3X₁ + 4X₂ > max

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

Z(X) = 3X₁ + 4X₂ > max

3X₁ + X₂ ? 75

X₁ + X₂ ? 30

X₁ + 4X₂ ? 84

X₁, X₂ ? 0

4. Решение задачи симплекс-методом

Приведение задачи к каноническому виду:

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

3Х₁ + Х₂ ? 75 3Х₁ + Х₂ +Х₃=75

Х₁ + Х₂ ? 30 => Х₁ + Х₂ + Х₄= 30

Х₁ + 4Х₂ ? 84 Х₁ + 4Х₂ + Х₅ = 84

Х₁,Х₂ ? 0 Х₁,Х₂,Х₃,Х₄,Х₅ ? 0

Если система ограничений содержит знак «<», то к левой части неравенства добавляется дополнительная переменная со знаком «+». Если

знак.« > », то добавляется переменная со знаком «-».

Дополнительные переменные вводят в целевую функцию с коэффициентом, равным нулю X₁,X₂,X₃,X₄

Система ограничений этой задачи является системой уравнений, разрешенной относительно переменных X₃,X₄,X₅

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

Z(X) = 3X₁ + 4X₂ > max

3Х₁ + Х₂ +Х₃=75

Х₁ + Х₂ + Х₄= 30

Х₁ + 4Х₂ + Х₅ = 84

Х₁,Х₂,Х₃,Х₄,Х₅ ? 0

Система ограничений этой задачи является системой уравнений, разрешенной относительно переменных X₃, X₄, X₅. Получаем:

X₃ = 75 - (3X₁ - X₂₎;

X₄ = 30 - (X₁ - X₂);

X₅ = 84 - (X₄ - 4X₂).

Для нахождения начального опорного решения строим начальную симплекс - таблицу:

Таблица 2 - начальная симплекс-таблица

Ci	БП	3	4	0	0	0	Z(x)
		X1	X2	X3	X4	X5	bi
0	X3	3	1	1	0	0	75
0	X4	1	1	0	1	0	30
0	X5	1	4	0	0	1	84
	Дj	-3	-4	0	0	0	0

Начальное опорное решение не является оптимальным, так как в рассматриваемой задаче на максимум векторам X1 и Х2 соответствуют отрицательные значения: Дj = -3, а Д2 = -4.

Построим новую симплекс таблицу. Выбираем базисную переменную, которую нужно ввести в базис, -4 - наименьшее значение Дj, поэтому Х₂ вводим в базис.

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

Заполняем строку переменной Х₂, для этого записываем в нее элементы строки X₅ поделенные на разрешающий элемент.

После заполняем оставшиеся строки. Для этого строку Х₂ последовательно умножаем на такие числа, чтобы после сложения ее с каждой строкой таблицы получить в столбце Х₂ нули (кроме 1 в новой строке) (Табл. 3).

Таблица 3

Ci	БП	3	4	0	0	0	Z(x)
		X1	X2	X3	X4	X5	bi
0	X3	11/4	0	1	0	-1/4	54
0	X4	3/4	0	0	1	-1/4	9
50	X2	3/4	1	0	0	1/4	21
	Дj	- 2	0	0	0	1	84

Начальное опорное решение не является оптимальным, так как в рассматриваемой задаче на максимум векторам X₁ соответствует отрицательные значения: Дj = -2.

В индексной строке F(X) выбираем максимальный по модулю элемент. В качестве ведущего выберем столбец, соответствующий переменной X₁, так как это наибольший коэффициент по модулю.

Вычислим значения по строкам как частное от деления: bi / ai1 и из них выберем наименьшее: min (54: 11/4, 9: 3/4, 21: 3/4)

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (3/11) и находится на пересечении ведущего столбца и ведущей строки.

Строим новую симплекс-таблицу (Табл. 4).

Таблица 4 - итоговая таблица

Ci	БП	40	50	0	0	0	Z(x)
		X1	X2	X3	X4	X5	bi
	X3	0	0	1	-11/3	2/3	21
	X1	1	0	0	4/3	-1/3	12
	X2	0	1	0	- 1/3	1/3	18
	Дj	0	0	0	8/3	1/3	108

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

Критерий оптимальности выполнен:

R max = 108; оптимальное базисное решение (12; 18; 21; 0; 0)

Таким образом при производстве 12 тракторных и 18 автомобильных глушителей мы получим максимальную прибыль в размере 108 денежных единиц. Ответ: max Z(X) = 108

5. Решение задачи графическим методом

Графическим методом решаются задачи линейного программирования, записанные в каноническом виде и удовлетворяющие условию X< 2, где n - число неизвестных системы ограничений; r - ранг системы векторов условий.

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

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

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

Необходимо найти минимальное значение целевой функции

F= 3X₁ + 4X₂ > max при системе ограничений

3X₁ + X₂ ? 75

X₁ + X₂ ? 30

X₁ + 4X₂ ? 84

X₁, X₂ ? 0

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

3X₁ + X₂ = 75 X₁ + X₂ = 30 X₁ + 4X₂ = 84

X1	0	25
X2	75	0
X1	0	30
X2	30	0
X1	0	84
X2	21	0

ABCD - многоугольник решений.

Построим линию уровня:

F = 3X₁ + 4X₂ = C при С = 0 получим:

3X₁ + 4X₂ = 0



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

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

X₂ = -0,75X₁

Рисунок. 1 (графическое изображение решения)

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

X₁ + 4X₂ = 84 3X₂ = 54 X₂ = 18

X₁ + X₂ = 30 X₁ = 30 - X₂ X₁ = 12

C (12; 18)

F(max) = F (12; 18) = 3*12 + 4*18 = 108

Таким образом, следует производить 12 тракторных и 18 автомобильных глушителей, при этом прибыль составит 108 денежных единиц.

6. Решение задачи в EXCEL

Для разработки математической модели необходима подготовка входной информации (Рис. 2):

Рисунок 2 (входная информация)

Пусть X1 - продукты А, a X2 - продукты В. Получаем следующие уравнения: 3Х1 + Х2 ? 2, Х1 + Х2 ? 1, Х1 + 4Х2 ? 3.

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

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

Вся разработанная информация сводится в развернутую математическую модель и заносится в рабочий лист MS Excel.

Для искомых величин переменных X1, Х2 нами были оставлены пустые ячейки - соответственно В4, С4, в которые мы написали значения целевой функции (Рис. 3).

Рисунок 3

Столбец D, названный «Сумма произведений», предназначен для определения суммы произведений значений искомых неизвестных (ячеек D3, D4, D5) с помощью функции MS Excel =«СУММПРОИЗВ(B2:C2;B3:C3)» (пример для D3).

Далее из имеющихся данных поэтапно заполняем ограничения (Рис. 4).

Рисунок 4

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



Рисунок 5

Выполним одно из следующих действий - сохраним найденное решение (рис. 6):

Рисунок 6

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

глушитель линейное программирование excel

Рисунок 6

Ответ: max Z(Х)= 3*12 + 4*18 = 108

Вывод: При изготовлении хлеба с максимальной прибылью, имеется следующий план производства: 3 ед. - первый вид хлеба, 9 ед. - второй вид хлеба.

Заключение

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

Таким образом, в ходе проделанной курсовой работы было использовано три метода для решения задачи: симплекс-метод, графический метод и метод решения в excel. Из этого мы делаем вывод, что подобные задачи удобнее решать в табличном редакторе MS Excel.

Список литературы

1) Гмурман В.Е Теория вероятностей и математическая статистика: учеб. пособие. - 12 - е изд., перераб. - М.: Высшее образование, 2008. - 479 с.

2) Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике: учебное пособие. - 11-е изд., пераб. - М.: Высшее образование, 2008. - 404 с.

3) Красс М.С., Чупрынов Б.П. Математические методы и модели для магистров экономики: учебное пособие. - СПб.: Питер, 2006. - 496 с.

4) Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Exel: Учеб. Пособие. СПб.: Изд - во Политехн. ун - та, 2007. - 88 с.

5) Сборник задач по высшей математике для экономистов: учебное пособие/ Под ред. В.И. Ермакова. - М.:ИНФРА - М, 2008. - 575 с.

6) Оуэн Г. Теория игр / Г. Оуэн; Пер. с англ. И.Н. Врублевской, Г.Н. Дюбина, А.Н. Ляпунова. - 2-е изд. - М.: Вузовская книга, 2007. - 216 с.

Размещено на Allbest.ru