Реферат: Нахождение оптимального плана производства продукции с использованием пакетов прикладных программ Math Cad

СОДЕРЖАНИЕГлава 1. Задание

Цель курсовой работы

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

Глава 2. Ознакомительный курсисследования операций

Введение

Линейное программирование

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

Глава 3.Практическое обоснование теории

Список использованной литературы

ГЛАВА I. ЗАДАНИЕ

Цель курсовой работы

ЦЕЛЬ — научиться:

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

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

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

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

Задача: ОАО «Красногорсклексредства» являетсяежемесячным поставщиком следующих лекарственных сборов аптеке «Эскулап»:

-          «Грудной сбор №4»

-          «Желчегонный сбор №3»

-          «Элекасол» (противомикробныйпрепарат)

Предполагается, что предприятие имеет 560000 тысяч рублей на развитие производства в течение пяти лет. В первоначальныймомент предприятие располагает ресурсами:

b1 – цветки ромашки аптечной

b2 – цветки календулы

b3 – листья мяты перечной

b4 –листья эвкалипта

 Ценына используемые ресурсы меняются в течение пяти лет :

/> — стоимость i- того ресурса k-тогогода, k=1,..,5

Виды ресурсов в течение пяти лет 1-ый год 2-ой год 3-й год 4-ый год 5-ый год в рублях на единицу ресурса

b1

10 9 9,4 8 8,4

b2

7 10 8 9 9,1

b3

8 7 9 8 8,1

b4

10 8 8,2 8 7

Пусть х1- количество единиц первойпродукции

х2- количество единиц второй продукции

х3- количество единиц третьей продукции.Прибыль от реализации единицы продукции каждого вида равна />:

Вид продукции 1-ый год 2-ой год 3-й год 4-ый год 5-ый год в рублях на единицу продукции х1 52 50 55 53 54 х2 41,20 42 44 45 43 х3 49,09 52 54 49,90 50

Математическая модель деятельности предприятия:

/>

При следующей системе ограничений:

/>

При чем: />

Распределение денежных средств на пять лет (в рублях):80 000, 100 000, 110 000, 120 000, 150 000.

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

Введение

В мире деятельность практически всегда не простоосознанная, а целенаправленная, какая-то работа совершается ради достиженияопределенной цели. Конечно, практически всегда ресурсы, необходимые длявыполнения данной работы, ограничены. Достаточно часто существует нескольковозможностей распорядится ресурсами, и хотелось бы сделать это каком-то смысле«получше». Исследование операций как раз и занимается этим кругомвопросом: цель работы – ограниченность необходимых ресурсов – поиск вариантоввозможных решений – определение способа действий. Цель — это желаемый результатдеятельности.

Линейное программирование

Экономико-математическая модель есть математическое описание, закономерности исследуемогоэкономического процесса или объекта.

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

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

/>

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

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

1.        Задачу максимизации можно свести кзадаче минимизации и наоборот:

/>

2.        Любое неравенство можнопредставить в виде равенства путем введения дополнительной отрицательнойпеременной.

/>

3. Переменную, не ограниченную условиемнеотрицательности можно заменить разностью двух неотрицательных переменных:

/>

4. Любое равенство можно представить как систему двухнеравенств:

/>

Геометрическая интерпретация задач ЛП

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

 

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

Симплекс –простейший многогранник. Метод состоит из двух основных этапов:

1.        Нахождение допустимого решения.

2.        Нахождение оптимального решениясреди допустимых решений.

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

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

Составление первой симплекс-таблицы

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

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

1.        Первый столбец включает базисныепеременные.

2.        Составляется второй столбец изсвободных членов.

3.        Последующие столбцы составляютсяиз коэффициентов при свободных переменных с противоположными знаками.

4.        Последней строкой этой таблицыявляется строка целевой функции.

Базисные переменные Свободные члены Свободные переменные

x1

x2

…

xj

…

xn

Xn+1

b1

A11

A12

…

A1j

…

A1n

Xn+2

b2

A21

A22

…

A2j

…

A2n

... … … … … … … …

Xn+i

bi

Ai1

Ai2 …

Aij

…

Ain

… … … … … … …. …

Xn+m

bm

Am1

Am2

…

Amj

…

Amn

z

-c1

-c2

….

-cj

…

-cn

 

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

/>

Признак допустимости базисных решений

-          базисное решение допустимое, еслионо неотрицательное;

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

Признак несовместимости ограничений

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

Признак оптимальности

Если в строке целевой функции все элементыодного знака (кроме свободного члена), то целевая функция принимаетэкстремальное значение, при чем, если все элементы положительны, то — max,если отрицательны – min.

Признак неограниченности целевой функции

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

Признак существования альтернативного(неединственного) решения

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

Нахождение разрешающих элементов

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

1. Разрешается столбец.

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

b)        решение допустимое, неоптимальное:любой столбец, не удовлетворяющий признаку оптимальности, является разрешающимстолбцом.

2. Разрешающая строка.

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

Правила преобразования симплекс-таблицы

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

/>

2.Ячейка разрешающего элемента заполняется обратнымзнаком:

/>

3.   Разрешающая строка делится на разрешающий элемент:

/>

4. Элементы разрешающего столбца делятся наразрешающий элемент с противоположным знаком:

/>

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

/>

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

Динамическое программирование используется дляисследования многоэтапных процессов. Состояние управляемой системыхарактеризуется определенным набором параметров (фазовыми координатами).Процесс перемещения в фазовом пространстве разделяют на ряд последовательныхэтапов и производят последовательную оптимизацию каждого из них, начиная споследнего. На каждом этапе находят условное оптимальное управление привсевозможных предположениях о результатах предыдущего шага. Когда процессдоходит до исходного состояния, снова проходят все этапы, но уже из множестваусловных оптимальных управлений выбирается одно наилучшее. Получается, чтооднократное решение сложной задачи заменяется многократным решением простой.Важно, что значения критерия – сумма частных значений, достигнутых на отдельныхшагах, и предыстория не имеют значения при определении будущих действий.

 

Особенности методов и моделейдинамического программирования

1.        Принятие оптимального решениярассматривается как процесс многоэтапный.

2.        Показатель эффективности всегопроцесса управления является аддитивной функцией показателей эффективностикаждого шага.

/>

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

4.        Состояние Skзависит только от состояния предшествующего шага и управления xk.

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

Принцип оптимальности Беллмана

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

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

Формулы Беллмана для динамического программирования

 

/>

/>

ГЛАВА 3. ПРАКТИЧЕСКОЕ ОБОСНОВАНИЕТЕОРИИ

Линейное программирование с использованиемпакета прикладных программ Math Cad.

Нахождение оптимального плана производства в первыйгод осуществляется с помощью прикладной программы Math Cad.

/>

/>

/>

Во второй год:

/>

/>

/>

/>

В третий год:

/>

/>

В четвертый год:

/>

/>

/>

В пятый год оптимальный план производства:

/>

/>

/>

/>

Динамическое программирование с помощьюпрограммы Microsoft Excel

x

Показатель эффективности предприятия

f(x1) f(x2) f(x3) f(x4) f(x5) z1 z2 z3 z4 z5 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 0,0 80000,0 15206,1 15671,5 16246,9 16514,4 16653,6 15206,1 15671,4 16246,9 16514,4 16653,6 100000,0 19815,5 20769,5 21384,9 21590,6 21737,7 19815,5 30877,6 31918,4 32761,3 21737,7 110000,0 22120,2 23318,5 23953,8 24128,6 24279,7 22120,2 35975,6 37056,3 37899,3 33168,1 120000,0 24424,9 25867,6 26522,8 26666,7 26821,7 24424,9 40585,04 42154,4 43037,3 43328,2 150000,0 31389,0 33514,6 34229,8 34280,9 34447,8 31389,0 43134,06 44723,4 45544,4 45870,2

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

СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ

1.        В.М.Трояновский. Математическоемоделирование в менеджменте, уч. пособие. 2-е изд., испр. и доп. – М.:Издательство РДЛ. 2002. – 256 с.

2.        Теоретические лекции подруководством Смирнова Ю.Н.

3.        Методические пособия.

4.        Пакеты прикладных программ Math Cad, Microsoft Excel, Microsoft Word.