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

Математическая модель представляет собой стройную и глубокую совокупность знаний о математических моделях со своими проблемами, с собственными путями развития, обусловленными внутренними и внешними причинами и задачами. Математика дает удобные и плодотворные способы описания самых разнообразных явлений реального мира и тем самым выполняет в этом смысле функцию языка. Эту роль математики прекрасно осознавал Галилей, сказавший: «Философия написана в грандиозной книге – Вселенной, которая открыта нашему пристальному взгляду. Но понять эту книгу может лишь тот, кто научился понимать ее язык и знаки, которыми она изложена. Написана же она на языке математики».

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

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

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

В курсовой работе по методам оптимизации предлагается две задачи: задача линейного программирования и общая задача оптимизации, решаемая графическим методом.

  Объект исследования: процесс исследования задач оптимизационного моделирования.

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

  Цель: освоить решения задач в Excel.

  Задачи: 

1)                     познакомиться с задачами оптимизации как разделом прикладной математики.

2)                     Освоить графический метод решения задач линейного программирования.

3)                     Освоить решения задач в Excel с использованием специального средства – поиск решения.

4)                     Разработать и оформить практические занятия для изучения.

5)                     Составить и оформить сборник задач.

Линейное программирование – это раздел методов оптимизации. К числу задач линейного программирования можно отнести задачи:

ü     рационального использования сырья и материалов;

ü     задачи оптимизации раскроя;

ü     оптимизации производственной программы предприятий;

ü     оптимального размещения и концентрации производства;

ü     составления оптимального плана перевозок, работы транспорта;

ü     управления производственными запасами;

ü     и многие другие, принадлежащие сфере оптимального планирования.

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

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

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

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

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

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

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

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

Рассмотрим задачу и решим её графическим способом.

Задача 1:

Предприятие электронной промышленности выпускает две модели радиоприемников, причем каждая модель производится на отдельной технологической линии. Суточный объем первой линии - 60 изделий, второй линии - 80 изделий. На радиоприемник первой модели расходуется 15 однотипных элементов электронных схем, на радиоприемник второй модели - 10 таких же элементов. Максимальный суточный запас используемых элементов равен 950 единиц. Прибыли от реализации одного радиоприемника первой и второй моделей равны 40$ и 20$ соответственно. Определите оптимальные суточные объемы производства первой и второй моделей на основе графического решения задачи.

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

Переменные задачи


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

 – суточный объем производства радиоприемников первой модели, [шт/сутки];

 – суточный объем производства радиоприемников второй модели, [шт/сутки];

Целевая функция


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

·                   их объемы производства, т.е.  и  радиоприемников в сутки;

·                   прибыль от их реализации  – согласно условию, соответственно 40 и 20 $.

Таким образом, доход от продажи суточного объема производства радиоприемников первой модели равен $ в сутки, а от продажи радиоприемников второй модели – $  в сутки. Поэтому запишем ЦФ в виде суммы дохода от продажи радиоприемников первой и второй модели:

 [$/сутки]

Ограничения


Возможные объемы производства радиоприемников  и  ограничиваются следующими условиями:

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

· суточный объем первой технологической линии (производство радиоприемников первой модели) не может превышать 60 шт в сутки, второй (производство радиоприемников второй модели) – 80 шт;

· объемы производства радиоприемников не могут быть отрицательными.

Таким образом, все ограничения задачи делятся на 3 группы, обусловленные:

1) расходом элементов электронных схем;

2) суточным объемом технологических линий;

3) неотрицательностью объемов производства.

Запишем эти ограничения в математической форме:

1)                     Т.к. из условия на радиоприемники первой и второй модели необходимо 15 и 20 элементов соответственно, то данное ограничение имеет вид:

[шт/сутки]

2)                     Ограничения по суточному объему первой и второй технологических линий имеют вид:

 [шт/сутки]

3)                     Неотрицательность объемов производства задается как

.

Таким образом, математическая модель этой задачи имеет вид





Нахождение оптимального решения задачи с помощью линейного метода.

  Математическую модель задачи о радиоприёмниках мы нашли на предыдущем шаге:





Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (рис.3.1).



прямая (1) – точки (0;95) и (63,(3);0), прямая (2) проходит через точку  параллельно оси , прямая (3) проходит через точку  параллельно оси .



Рис.3.1. Графическое решение задачи о производстве радиоприемников.

Определим ОДР. Например, подставим точку (0;0) в исходное ограничение (1), получим , что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную правее и ниже прямой (1). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рис.3.1). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является многоугольник ABCDE.

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



Точки пересечения с осями – (0;75) и (37,5;0)

Строим вектор  из точки (0;0) в точку (40;20). Точка D – это последняя вершина многоугольника допустимых решений ABCDE, через которую проходит целевая прямая, двигаясь по направлению вектора . Поэтому D – это точка максимума ЦФ. Определим координаты точки D из системы уравнений прямых ограничений (1) и (2)



Получили точку D(60;5) [шт/сутки].

Максимальное значение ЦФ равно [$/сутки].

Таким образом, наилучшим режимом работы предприятия является ежесуточное производство радиоприемников первой модели в количестве 60 штук и радиоприемников второй модели в количестве 5 штук. Доход от продажи составит  2500$ в сутки.

Эту задачу решили графическим методом. Теперь рассмотрим задачу и решим ее  с использованием специального средства – «поиск решения». Для использования программы необходимо произвести установку надстройки ”Поиск решения”. Для этого следует выполнить следующее действие: из пункта меню выбрать Сервис/Надстройки, в открывшемся окне отметить галочкой “Поиск решения” и нажать ОК (Рис. 1).



Рис. 1. Установка надстройки ”Поиск решения”.

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

Задача.

Школьный кондитерский цех готовит пирожки и пирожные. В силу ограниченности емкости склада за день можно приготовить в совокупности не более 700 изделий. Рабочий день в кондитерском цехе длится 8 часов. Если выпускать только пирожные, за день можно произвести не более 250 штук, пирожков же можно произвести 1000, если при этом не выпускать пирожных. Стоимость пирожного вдвое выше, чем пирожка. Требуется составить дневной план производства, обеспечивающий кондитерскому цеху наибольшую выручку.

 Вначале надо подготовить электронную таблицу к решению задачи оптимального планирования. В режиме отображения формул таблица показана на рис. 3. Ячейки B5 и C5 зарезервированы соответственно для значений x(план по изготовлению пирожков) и y(план по изготовлению пирожных). Ниже этих ячеек представлена система неравенств, определяющая ограничения на искомые решения. Неравенства разделены на левую часть(столбец В) и правую часть (столбец D). Знаки неравенств в столбце С имеют чисто оформительское значение. Целевая функция занесена в ячейку В15.

	A	B	C	D
1	Оптимальное планирование
2
3	Плановые показатели
4		X (пирожки)	Y (пирожные)
5
6
7	ограничения
8
9		Левая часть	Знак	Правая часть
10	Время производства:	=B5+4*C5	<=	1000
11	Общее количество:	=B5+C5	<=	700
12	Положительность Х:	=B5	>=	0
13	Положительность Y:	=C5	>=	0
14
15	Целевая функция	=B5+2*C5
16

Рис. 3. таблица,подготовленная к вычислению оптимального плана

Теперь следует вызвать программу оптимизации «Поиск решения» и сообщить е, где расположенные данные. Для этого надо выполнить команду => Сервис => Поиск решения. На экране откроется соответствующая форма (рис. 4).



Рис. 4. начальное состояние формы «Поиск решения»

Далее надо выполнить следующий алгоритм:

1.    Ввести координату ячейки с целевой функцией. В нашем случае это В15. (заметим , что если перед этим установить курсор на ячейку В15, то ввод произойдет автоматически.

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

3.    В поле «Изменяя ячейки» ввести В5:С5, то есть сообщить, какое место отведено под значения переменных - плановых показателей.

4.    В поле «Ограничения» надо ввести информацию о неравенствах – ограничениях, которые имеют вид В10<= D10; B11<= D11;B12<= D12; B13<= D13. ограничения вводятся следующим образом:

В появившемся диалоговом окне «Добавление ограничения» ввести ссылку на ячейку В10, выбрать изменю знак неравенства <= и ввести ссылку на ячейку D10; снова щелкнуть по кнопке «добавить» и аналогично ввести второе ограничение B11<=D11 и так далее. В конце надо щелкнуть по кнопке ОК.

    5. Закрыть диалоговое окно «Добавление ограничения». Снова появится форма «Поиск решения» (рис.5).



Рис. 5. Форма  «Поиск решения» после ввода информации

6.     Теперь надо дать последние указания: задача является линейной (это многократно облегчит программе ее решение). Для этого следует щелкнуть по кнопке «Параметры поиска решения» (рис 6 ).



 рис. 6. «Параметры поиска решения»

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

8.     Вся информация введена. Далее надо щелкнуть по кнопке «Выполнить» - мгновенно в ячейкахВ5 и С5 появится оптимальное решение (600 и 100), а также число 800 в ячейке В15 – максимальное значение целевой функции (рис. 7).

	A	B	C	D
1	Оптимальное планирование
2
3	Плановые показатели
4		X (пирожки)	Y (пирожные)
5
6
7	ограничения
8
9		Левая часть	Знак	Правая часть
10	Время производства:	1000	<=	1000
11	Общее количество:	700	<=	700
12	Положительность Х:	600	>=	0
13	Положительность Y:	100	>=	0
14
15	Целевая функция	800
16

Рис. 7. результаты решения задачи

Кроме того, на экране появилась еще одна форма – «Результаты поиска решения» (рис.8).



Рис. 8. Форма «Результаты поиска решения»

Итак, в результате применения инструмента «Поиск решения», мы получим следующий оптимальный план дневного производства кондитерского цеха: нужно выпускать 600 пирожков и 100 пирожных.