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

  - 40 -

                             АМТ.6ДП32

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

АРМАВИРСКИЙ МАШИНОСТРОИТЕЛЬНЫЙ ТЕХНИКУМ

Допущен к защите

Зам. директора по УР

___________И. Г. Крупнова

«__» ________ 2006 г.

ДИПЛОМНЫЙ ПРОЕКТ

Тема: «Геометрическая интерпретация ОЗЛП как метод оптимизации»

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

Выполнила                                                                                                   студентка группы 4ТПс

Н.В.Овсянникова

Руководитель проекта                                                                       преподаватель

Е.П.Яковенко

Проверил                                                                                                  Р.Ф.Баева

2006

Содержание

ВВЕДЕНИЕ

1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1. Описание решаемой задачи

1.2. Экономическое значение решаемой задачи

1.3. Обоснование выбора методов решения задачи

1.4.Описание выбранного алгоритма решения

2. ОПЫТНО-ЭКСПЕРИМЕНТАЛЬНАЯ ЧАСТЬ

2.1. Описание реализации алгоритма решения задачи

2.2. Результаты, полученные в ходе решения задачи

3. ВЫВОДЫ И ЗАКЛЮЧЕНИЕ

4. СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

5. ПРИЛОЖЕНИЕ

5.1. Руководство пользователя для решения задачи с помощью

MS EXCEL

5.2. Список иллюстраций

5.3. Список таблиц

ВВЕДЕНИЕ

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

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

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

Решение экстремальных экономических задач можно разбить на три этапа:

1) построение экономико-математической модели;

2) нахождение оптимального решения одним из математических методов;

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

Методам линейного программирования посвящено много работ зарубежных и, прежде всего американских ученых. В 1941 г. Хичкок поставил транспортную задачу. Основной метод решения линейного программирования - симплексный метод - был опубликован в 1949 г. Данцигом. Дальнейшее развитие методы линейного и нелинейного программирования получили в работах Форда, Фалкерсона, Куна, Лемке, Гасса, Чарнеса, била и др. в настоящее время методы линейного программирования развиваются главным образом в направлении выявления конкретных экономических задач, к решению которых оно быть применено, а также по пути создания более удобных алгоритмов для решения задач на электронно-вычислительных машинах.

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

1.ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1. Описание решаемой задачи

Представим себе группу из трех станков, каждый из которых может производить два типа деталей, условно А и Б. Производительность каждого из станков по разным типам деталей, как правило, различна: станок № 1 производит в одну минуту 5 деталей А и 5 деталей Б, станок № 2 – 6 деталей А и 2 детали Б, станок № 3 – 5 деталей А и 3 детали Б. При решении задачи необходимо учитывать два ограничения:

1) ни один из станков не должен простаивать;

2) продукция должна быть комплектна: количество произведенных деталей А должно равняться числу деталей Б.

Прежде всего, попытаемся получить глазомерное решение задачи. Все расчеты будем производить исходя из общей продолжительности времени работы в 6 ч.=360 мин. (одна смена).

На все указанное время загрузим станок № 1 деталями А, а станки № 2 и № 3 – деталями Б. Результат такого решения изобразим следующим образом: слева покажем время загрузки станков по различным деталям, а справа – соответствующее количество произведенной продукции (произведение времени работы на минутную производительность):

Таблица 1              Глазомерное решение задачи             

Общее количество выпущенной продукции составит 1800+1800=3600 деталей. Это решение отвечает поставленным условиям: во-первых, все станки полностью загружены в течение рабочего времени; во-вторых, количество произведенных деталей А в точности равно числу полученных деталей Б.

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

1.2. Экономическое значение решаемой задачи

Для решения конкретных практических экономических задач можно рекомендовать такую последовательность:

1.      Уясняем задачу - ее экономический смысл. На этой основе устанавливаем цель решения.

2.      Оцениваем экономическую ситуацию – определяем, от чего зависит достижение установленной цели.

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

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

5.      С помощью математической модели и найденного экономическо-математического метода решаем задачу.

6.      Проверяем правильность найденного решения.

Постановка задачи: Представим себе группу из трех станков, каждый из которых может производить два типа деталей, условно А и Б. Производительность каждого из станков по разным типам деталей, как правило, различна: станок № 1 производит в одну минуту 5 деталей А и 5 деталей Б, станок № 2 – 6 деталей А и 2 детали Б, станок № 3 – 5 деталей А и 3 детали Б. При решении задачи необходимо учитывать два ограничения:

1) ни один из станков не должен простаивать;

2) продукция должна быть комплектна: количество произведенных деталей А должно равняться числу деталей Б.

Итак, по порядку:

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

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

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

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

Формулировка математической модели задачи:

                        Переменные для решения задачи: хij – время работы i–го станка, занятого производством j–той детали.

                        Определение функции цели (критерии оптимизации). Суммарная суточная прибыль от производства продукции равна L.

                        Ограничения на переменные:

- время работы каждого станка не должно быть отрицательным, т.е. хij≥0;

- станки не должны простаивать, т.е.

х11 +х12=360,

х21 +х22=360,

х31 +х32=360,

- количество произведенной продукции на станке А должно равняться количеству произведенной продукции на станке Б, т.е.

5х11+6х21+5х31 =5х12+2х22+3х32.

           Найти максимум следующей функции:

L=5х11+5х12+6х21+2х22+5х31+3х32→max

           При ограничениях вида:

х11 +х12=360,

х21 +х22=360,

х31 +х32=360,

5х11+6х21+5х31 =5х12+2х22+3х32.

5.           Прежде всего, попытаемся получить глазомерное решение задачи. Все расчеты будем производить исходя из общей продолжительности времени работы в 6 ч.=360 мин. (одна смена). Суть метода удобнее всего выразить с помощью наглядного геометрического представления, графика (рисунок 1). Здесь показан построенный по правилам математического программирования многоугольник ОАВСD (он выделен).

Рисунок 1

График решения станковой задачи

Многоугольник соответствует условиям нашей задачи и представляет собой область допустимых решений распределения времени работы станков № 2 и № 3 над деталью А. По соответствующим осям графика отмечена продолжительность работы этих станков. (В своих расчетах мы вполне можем обойтись двумя станками и одной деталью, так как по этим данным нетрудно рассчитать и все остальные.) В теории математического программирования убедительно показывается, что оптимальному решению соответствует одна из вершин многоугольника допустимых планов, а именно та, для которой общая производительность окажется максимальной. В нашем случае это вершина С. Как видно из графика, этой точке соответствует время работы над деталью А станка № 2, равное 360, станка № 3 – 90 мин. По этим данным нетрудно составить план распределения станков, причем время, отводимое на производство детали Б станками № 2 и № 3, получится как дополнение до 360 минут времени, снятого с графика, - станки не должны простаивать. Что касается станка № 1, то его время работы подбираем таким, чтобы общее количество деталей А и Б совпадало.