Применение МS Excel в линейном программировании

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

Министерство образования и науки Российской Федерации

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

Инженерно-экономический институт

Кафедра предпринимательства и коммерции

КУРСОВАЯ РАБОТА

по дисциплине «Методы Оптимальных Решений»

Применение МS Excel в линейном программировании

Выполнил студент группы з 33707/23

А.М. Герасимова

Принял: Доцент, к.э.н.

Д.В. Тихонов

Санкт-Петербург

2015



Содержание

линейный программирование процессор еxcel

Введение

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

1.1 Динамическое программирование

2. Практическая часть

2.1 Исходные данные

2.2 Исходная задача

2.3 Двойственная задача

2.4 Устойчивость решения

2.5 Двойственная задача

Заключение

Список использованных источников



Введение

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

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

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

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



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

Для решения некоторых типов задач оптимального программирования используется метод динамического программирования (ДП).

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

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

Для решения задач методом динамического программирования не предлагается подходящих программных средств - разобраться в сути принцип оптимальности Беллмана следует с карандашом в руке.

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

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

1.1 Динамическое программирование

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

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

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

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

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

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

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

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

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

Таким образом, на каждом шаге в соответствии с принципом оптимальности ищется решение, обеспечивающее оптимальное продолжение процесса относительно состояния, достигнутого в данный момент. Если при движении от конца к началу оптимизируемого процесса определены условно - оптимальные решения для каждого шага и вычислен соответствующий эффект (эту стадию рассуждений называют иногда условной оптимизацией), то остается «пройти» весь процесс в прямом направлении (стадия безусловной оптимизации) и «прочитать» оптимальную стратегию, которая нас интересует.

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

Рассмотрим применение методов динамического программирования при решении конкретной задачи.

Для реконструкции и модернизации производства на четырех предприятиях выделены денежные средства S₀=80 ден. ед.

По каждому предприятию известен возможный прирост f_i(x) (i =1,2,3,4) выпуска продукции в зависимости от выделенной суммы.

Требуется:

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

2) Используя решение основной задачи, найти оптимальное распределение между тремя предприятиями.

Данные, необходимые для решения, приведены в таблице1.



Таблица 1 - Распределение денежных единиц по предприятиям

Х	1 предприятие f1(х)	2 предприятие f2(х)	3 предприятие f3(х)	4 предприятие f4(х)
20	16	10	15	17
40	28	29	27	23
60	36	42	46	38
80	49	50	58	53

Решение

1) Математическая модель прямой задачи:

4 предприятия Условная оптимизация-1 этап

денег всего S₀=80

Экономический смысл переменных: x_i - количество денег, вкладываемых в i предприятие. S_i - количество денег, оставшихся после вложения в i-предприятие (состояние системы на i-шаге); F(x_i) - прибыль от вложенной суммы денег; S₀- начальный капитал.

На 4-ом предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80 д.ед. Тогда прибыль от вложения денег можно получить следующие значения представленные в таблице 2.

Таблица 2 - Распределение прибыли от вложений

S3	Х4	f (x4)	F4
0	0	0	0
20	20	17	17
40	40	23	23
60	60	38	38
80	80	53	53



На 3-ем и 4-ем предприятии может остаться либо 0, либо 20, либо 40, либо 60, либо 80 д. ед. Рассмотрим первую возможность. Если 3-му предприятию мы выдаем 20 д. ед., то 4-му предприятию ничего не остается, и наоборот. Соответственно 40 д. ед. можно поделить так (0;40), (20;20), (40;0); 60 д. ед. - (0;60), (20;40), (40;20), (60;0) и т.д.

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

Таблица 3 - Третий вариант распределения прибыли

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг		Прибыль на шаге
S2	Х3	S3	f (x3)	F4	f+F	F3
0	0	0	0	0	0	0
20	0	20	0	17	17	17
	20	0	15	0	15
40	0	40	0	23	23	32
	20	20	15	17	32
	40	0	27	0	27
60	0	60	0	38	38	46
	20	40	15	23	38
	40	20	27	17	44
	60	0	46	0	46
80	0	80	0	53	53	63
	20	60	15	38	53
	40	40	27	23	50
	60	20	46	17	63
	80	0	58	0	58

Таблица 4 - Распределение 40 денежных единиц

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг	Сумма	Прибыль на шаге
S1	Х2	S2	f (x2)	F3	f+F	F2
0	0	0	0	0	0	0
20	0	20	0	17	17	17
	20	0	10	0	10
40	0	40	0	32	32	32
	20	20	10	17	27
	40	0	29	0	29
60	0	60	0	46	46	46
	20	40	10	32	42
	40	20	29	17	46
	60	0	42	0	42
80	0	80	0	63	63	63
	20	60	10	46	56
	40	40	29	32	61
	60	20	42	17	59
	80	0	50	0	50

Таблица 5 - Сводная таблица

Вклад	Проект	Остаток	Прибыль из матрицы	Прибыль за шаг	Сумма	Прибыль на шаге
S0	Х1	S1	f (x1)	F2	f+F	F1
80	0	80	0	63	63	63
	20	60	16	46	62
	40	40	28	32	60
	60	20	36	17	53
	80	0	49	0	49

Анализ результатов:

Максимальная прибыль равна 63 д.ед. Распределить денежные средства между предприятиями необходимо следующим способом (в таблице строки выделены серым цветом):

1 предприятие - 0 д. ед.

2 предприятие - 0 д. ед.

3 предприятие - 60 д. ед.

4 предприятие - 20 д.ед.

Используя решение основной задачи, найдем оптимальное распределение между тремя предприятиями.

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

- 2 предприятие - 0 д.ед.;

- 3 предприятие - 60 д.ед.;

- 4 предприятие - 20 д.ед..

Максимальная прибыль равна 63 д.ед.



2. Практическая часть

2.1 Исходные данные

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

Таблица 6 - Нормативы затрат ресурсов

Оборудование	A	B	C	ОФРВ (ч)
Ф	2	4	5	200
Т	1	8	6	300
С	7	4	5	260
Ш	4	6	7	360
Прибыль/ед. (р.)	10	14	12

Требуется определить, сколько изделий каждого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Дополнительное ограничение - производство продукта С не менее 5 единиц. Интервалы для расчета интервала устойчивости - ограничения изменяются: Токарное - 300, Фрезерное - 350.

2.2 Исходная задача

Составим математическую модель задачи.

Обозначим через Х=(х₁,х₂,х₃) - план производства продукции, где х₁ - количество единиц изделия А, х₂ - количество единиц изделия B, х₃ - количество единиц изделия С, планируемое к производству.

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

Z=10х₁+14х₂+12х₃ > max

Составим ограничения на общий фонд рабочего времени каждого из типов используемого оборудования (ОФРВ):

2х₁+4х₂+5х₃ ? 200 - на ОФРВ фрезерного оборудования

х₁+8х₂+6х₃ ? 300 - на ОФРВ токарного оборудования

7х₁+4х₂+5х₃ ? 260 - на ОФРВ сварочного оборудования

4х₁+6х₂+7х₃ ? 360 - на ОФРВ шлифовального оборудования

По смыслу задачи переменные х_i неотрицательны:

х_i ? 0, ()

Задача - это математическая модель задачи.

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

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

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

Загружается пакет MS Excel и проектируется сценарий решения задачи оптимизации.

Формальная постановка задачи оптимизации переносится на рабочий лист MSExcel.

Определяются ячейки для переменных задачи оптимизации.

Определяется ячейка, в которую вводится формула для целевой функции

Определяются ячейки, в которые вводятся формулы для ограничений.

Вызывается диалоговое окно программной надстройки «Поиск решения» (в меню «Сервис» выбирается команда «Поиск решения»).

В поле «Установить целевую ячейку» вводится ячейка, в которой находится формула для целевой функции, причем с помощью переключателя фиксируется направление оптимизации (max или min).

В поле «Изменяя ячейки» вводятся ячейки, в которых планируется размещение переменных задачи оптимизации.

В поле «Ограничения» вводятся данные, определяющие структуру каждого ограничения:

1) ячейка, содержащая формулу для ограничения;

2) тип ограничения;

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

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

Задача оптимизации запускается на выполнение с помощью кнопки «Выполнить».

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

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

- значения переменных задачи оптимизации (элементы решения);

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

- расчетные значения ограничений.

Для повторного решения задачи оптимизации следует удалить содержимое ячеек с элементами решения и сбросить полученные результаты (клавиша «Delete»).

Фрагмент рабочего листа MSExcel с результатами решения задачи оптимизации сохраняется и переносится в документ MSWord (например, с помощью команд «Ctrl&PrintScreen» в среде MSExcel и «Вставить» в документе MS Word или с помощью команд «Копировать» и «Вставить», расположенных на панели инструментов во всех приложениях пакета MSOffice).

Создадим в файле решений лист «Производство продукции». На рабочем листе создадим схему решения (рис.1).

Рис. 1 - Лист «Производство продукции» в Excel

Поясним составление таблицы в Excel:

- в 1-й строке таблицы находится заголовок;

- во 2-й - наименования продукции;

- в 3-й строке отведено место для оптимального решения, которое после вычислений появится в ячейках B3:D3 (в жирной рамке);

- в 4-й строке в ячейках B4:D4 заданы коэффициенты целевой функции, а ячейка E4, в рамке, зарезервирована для вычисления значения целевой функции;

- строки с 6-й по 9-ю содержат коэффициенты, знаки и правые части ограничений;

- в столбце Левая часть после вычислений появятся левые части ограничений;

- в столбце Разница -- появится разность правых и левых частей;

- в ячейку E6 внесем формулу СУММПРОИЗВ(B$3:D$3;B6:D6) и скопируем ее на ячейки Е7:Е9;

- в ячейку H6 внесем формулу G6-E6 и скопируем ее на ячейки Н7:Н9;

- в целевую ячейку Е4 внесем формулу СУММПРОИЗВ(B3:D3;B4:D4).

Выполним поиск решений (рис.2).

Рис.2 - Диалоговое окно «Поиск решения»

Условия поиска:

Условия поиска:

Целевая ячейка: Е4

Равная: максимум

Изменяемые ячейки: B3:D3

Ограничения: E6:E9?G6:G9; B3:D3?0.

Результат поиска представлен на рис.3.



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

Значение функции цели равно 664,62; оптимальный план:

Х^*=(16,92; 35,38; 0).

Таким образом, по оптимальному плану предприятие должно изготовить 16,92 единиц продукции А и 35,38 единиц продукции В. При этом максимальная прибыль будет равна 664,62 р.

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

- значение разницы 24,62 для Ф означает, что остаток фонда рабочего времени фрезерного оборудования равен 24,62 ч, т.е. этот ресурс недефицитен;

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

- значение разницы 0 для С означает, что фонд рабочего времени сварочного оборудования использован полностью, т.е. этот ресурс дефицитен;

- значение разницы 80 для Ш означает, что остаток фонда рабочего времени шлифовального оборудования равен 80 ч, т.е. этот ресурс недефицитен.

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



Рис. 4 - Отчет по устойчивости

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

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

- в столбце Результ. значение - найденное оптимальное решение (16,92; 35,38; 0);

- в столбце Нормир. стоимость - двойственные оценки (0; 0; -1,04). Такая оценка может быть отлична от нуля только для нулевой переменной и показывает, на какую величину в целевой функции следует изменить коэффициент этой переменной, чтобы в оптимальном плане она приняла положительное значение (в нашем случае, прибыль от продажи единицы продукции С следует увеличить на 1,04 р. до 12+1,04=13,04 р., чтобы включить эту продукцию в оптимальный план стало выгодно). Кроме того, эти оценки показывают, на какую величину ухудшится значение целевой функции, если уйти от оптимального плана, добавив в него 1 ед. соответствующего товара;

- в столбце Целевой Коэффициент - коэффициенты целевой функции;

- в последних двух столбцах - допустимые приращения коэффициентов целевой функции, при которых сохраняется прежнее оптимальное решение (при этом 1E+30 означает 10⁺³⁰, то есть фактически +?).

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

для прибыли от продажи ед. продукции А - [6,62; 24,5],

для прибыли от продажи ед. продукции B - [12,5; 80],

для прибыли от продажи ед. продукции C - [0; 13,04].

Во второй таблице отчета по устойчивости выводится следующая информация:

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

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

- в столбце Теневая Цена - теневые цены - двойственные оценки, показывающие, на какую величину изменится целевая функция при увеличении на единицу правой части ограничения, тогда как остальные данные неизменны (в частности при добавлении единицы соответствующего ресурса). В нашем случае, при увеличении фонда рабочего времени токарного оборудования на 1 ч. прибыль увеличится на 1,12 р., а при увеличении фонда рабочего сварочного оборудования на 1 ч. прибыль увеличится на 1,27 р.;

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

- в столбце Ограничение Правая часть - правые части ограничений (запасы ресурсов);

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

При добавлении допустимых приращений к правым частям ограничений получаются интервалы осуществимости (устойчивости). В нашем примере такими интервалами будут:

- для фонда времени фрезерного оборудования (ч) - [175,38; +?),

- для фонда времени токарного оборудования (ч) - [37,14; 364],

- для фонда времени сварочного оборудования (ч) - [150; 366,67],

- для фонда времени шлифовального оборудования (ч) - [280; +?).

2.3 Двойственная задача

Воспользуемся следующими взаимосвязями между прямой и двойственной задачами:

Если прямая задача - на максимум, то двойственная к ней - на минимум, и наоборот.

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

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

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

Если прямая задача - на максимум, то ее система ограничений представляется в виде неравенств типа ?. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа ?.

Если прямая задача - на минимум, то ее система ограничений представляется в виде неравенств типа ?. Двойственная задача решается на максимум, и ее система ограничений имеет вид неравенств типа ?.

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

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

Если на переменную x_j прямой задачи не наложено условие неотрицательности, то j-е ограничение двойственной задачи записывается в виде строгого равенства.

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

Эти требования формализуются в виде следующей двойственной задачи:

F=200y₁+300y₂+260y₃+360y₄> min

2y₁+y₂+7y₃+4y₄ ? 10

4y₁+8y₂+4y₃+6y₄ ? 14

5y₁+6y₂+5y₃+7y₄ ? 12

y_j ? 0, ()

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

Y^*=(0; 1,12; 1,27; 0).

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

F_min =200*0+300*1,12+260*1,27+360*0=664,62

2*0+1,12+7*1,27+4*0 = 10 = 10

4*0+8*1,12+4*1,27+6*0 = 14 = 14

5*0+6*1,12+5*1,27+7*0 = 13,04 > 12

Все ограничения двойственной задачи выполняются, при этом F_min=Z_max=664,62, что подтверждает первую теорему двойственности.

2.4 Устойчивость решения

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

Z=10х₁+14х₂+12х₃ > max

2х₁+4х₂+5х₃ ? 200

х₁+8х₂+6х₃ ? 300

7х₁+4х₂+5х₃ ? 260

4х₁+6х₂+7х₃ ? 360

х₃ ? 5

х_i ? 0, ()

Задача (1^/)-(3^/) - это математическая модель задачи с дополнительным ограничением. Опять же, решим задачу при помощи программы Excel.

На рабочем листе создадим схему решения (рис.5).

Рис. 5 - Лист «Производство продукции» в Excel с дополнительным ограничением



Выполним ПОИСК РЕШЕНИЯ (рис.6).

Рис. 6 - Диалоговое окно «Поиск решения»

Условия поиска:

Целевая ячейка: E4

Равная: максимум

Изменяемые ячейки: B3:D3

Ограничения: E6:E9?G6:G9; E10?G10; B3:D3?0.

Результат поиска представлен на рис.7.

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

Значение функции цели равно 661,5; оптимальный план:

Х^*=(16; 33,25; 3).

Таким образом, в данном случае, по оптимальному плану предприятие должно изготовить 16 единиц продукции А, 33,25 единиц продукции В и 3 единицы продукции С. При этом максимальная прибыль будет равна 661,5 р.

Значит, наложение дополнительного ограничения привело к снижению прибыли на 664,62-661,5=3,12 р.

2.5 Двойственная задача

Помножим 5-е неравенство системы ограничений (2^/) прямой задачи на (-1), получим задачу:

Z=10х₁+14х₂+12> max

2х₁+4х₂+5х₃ ? 200

х₁+8х₂+6х₃ ? 300

7х₁+4х₂+5х₃ ? 260

4х₁+6х₂+7х₃ ? 360

-х₃ ? -5

Двойственная задача:

F=200y₁+300y₂+260y₃+360y₄-5y₅> min

2y₁+y₂+7y₃+4y₄ ? 10

4y₁+8y₂+4y₃+6y₄ ? 14

5y₁+6y₂+5y₃+7y₄-y₅ ? 12

Оптимальный план двойственной задачи - это теневые цены, которые берем из отчета по устойчивости (рис.8):

Y^*=(0; 1,12; 1,27; 0; 1,04).



Рис. 8 - Отчет по устойчивости

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

F_max = 200*0+300*1,12+260*1,27+360*0-5*1,04=661,5

2*0+1,12+7*1,27+4*0 = 10 = 10

4*0+8*1,12+4*1,27+6*0 = 14 = 14

5*0+6*1,12+5*1,27+7*0 - 1,04 = 12 = 12

Все ограничения двойственной задачи выполняются, при этом F_max=Z_min=661,5, что подтверждает первую теорему двойственности.



Заключение

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

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

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



Список использованных источников

1. Акулич И.Л. Математическое программирование в примерах и задачах: Учебное пособие. -- М.: Высшая школа, 1993.

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология: Учебное пособие. -- М.: Высшая школа, 2001.

3. Гарнаев А.Ю. Excel, VBA, Internet в экономике и финансах. -- Спб.: БХВ -- Петербург, 2002.

4. Глухов В.В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента: Учебник. -- Спб.: Лань, 2000.

5. Друри К. Введение в управленческий и производственный учет. -- М.: Аудит, ЮНИТИ, 1998.

6. Исследование операций: В 2-х томах / Под ред. Дж. Моудера, С. Элмаграби; Пер. с англ. -- М.: Мир, 1981.

7. Кузин Б.И., Юрьев В. Н., Шахдинаров Г. М. Методы и модели управления фирмой: Учебник. -- Спб.: Питер, 2001.

8. Кузнецов Ю.Н., Кузубов В. И., Волощенко А. Б. Математическое программирование: Учебное пособие. -- М.: Высшая школа, 1980.

9. Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. -- Спб.: BHV -- Санкт-Петербург, 1997.

10. Кутузов А.Л. Математические методы в экономике и менеджменте: Практикум по использованию пакетов прикладных программ QSB+, QS и программы Excel. -- Спб.: Изд-во СпбГТУ, 2001.

11. Липсиц И.В. Коммерческое ценообразование: Учебник. Сборник деловых ситуаций. Тесты. -- М.: БЕК, 2001.

12. Саати Т.Л. Математические модели конфликтных ситуаций / Пер. с англ. -- М. Советское радио, 1977.

13. Таха Х.А. Введение в исследование операций / Пер. с англ. -- М.: Вильямс, 2001.

14. Шеннон Р. Имитационное моделирование систем -- искусство и наука / Пер. с англ. -- М.: Мир, 1978.

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

...