183660 (Решения задачи планирования производства симплекс методом)

Федеральное агентство по образованию

Санкт-Петербургский Государственный Политехнический Университет

Факультет технической кибернетики

Кафедра «Системный анализ и управление»

Работа допущена к защите

Заведующий кафедрой

____________ В.Н. Козлов

«___» __________ 2010 г.

ДИПЛОМНАЯ РАБОТА

Тема: Решения задачи планирования производства симплекс методом.

Специальность:230201 – Информационные системы и технологии

Выполнил студент гр. 6082/2 Дегтярёв И.В.

Руководитель, к.т.н., доцент Болотин И.В.

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

2010

Санкт-Петербургский государственный политехнический университет

Факультет технической кибернетики

Кафедра «Системный анализ и управление»

УТВЕРЖДАЮ

«___» ____________2010 г.

Зав. кафедрой _______________

ЗАДАНИЕ

по дипломному проектированию

студенту Дегтярёву И.В.

группа 6082/2

1. Тема проекта (работы)______________________________________

_________________________________________________________________________________________________________________________________

2. Срок сдачи студентом законченного проекта (работы)___________________________________________________________

3. Исходные данные к проекту (работе)_________________________ __________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

4. Содержание расчетно-пояснительной записки (перечень подлежащих разработке вопросов)___________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

5. Перечень графического материала (с точным указанием обязательных чертежей)________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

6. Консультанты по проекту (с указанием относящихся к ним разделов проекта, работы)___________________________________________________ ____________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

7. Дата выдачи задания________________________________________

Руководитель_________________________________________________

Задание принял к исполнению___________________________________

Реферат

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

В данной дипломной работе решается задача планирования производства, являющаяся общей задачей линейного программирования (ЛП). Для решения поставленной задачи использовался симплекс-метод, т.к. он является наиболее известным, достаточно эффективным и широко применяемым на практике для решения прикладных задач линейного программирования. Во вспомогательных целях была использована надстройка MS Excel «Поиск решения».

Так же в среде объектно-ориентированного программирования С++ была реализована программа для решения задач линейного программирования симплекс-методом (в частности поставленной задачи планирования производства).

Перечень используемых сокращений

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

ЦЛП – Целочисленное линейное программирование;

ЗЛП – Задача линейного программирования;

ОДР – Область допустимых решений;

MS Excel – Microsoft Excel;

ОС – Операционная система

Содержание

Введение

1. Обзор научно-технической литературы

1.1 История развития экономико-математического планирования

1.2 Необходимость решения задач линейного программирования

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

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

1.5 Постановка задачи целочисленного программирования

2. Обзор основных алгоритмов решения задач ЛП

2.1 Целочисленное линейное программирование - метод отсечений Гомори

2.1.1 Отсечения

2.1.2 Описание алгоритма

2.2 Целочисленное линейное программирование - метод ветвей и границ

2.2.1 Общее описание

2.2.2 Применение

2.2.3 Алгоритм решения

2.3 Симплекс метод

2.3.1 Описание

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

2.3.2.1 Усиленная постановка задачи

2.3.2.2 Алгоритм

2.4 Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel

2.4.1 Описание

2.4.2 Процедура поиска решения

2.4.3 Параметры средства «Поиск решения»

3. Задача планирования производства

3.1 Постановка задачи планирования производства в общем случае

3.2 Математическое описание поставленной задачи планирования симплекс методом

3.3 Решение поставленной задачи планирования производства

3.3.4 Проверка признака допустимости и оптимальности базиса

3.3.5 Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса

3.3.6 Пересчет симплекс-таблицы

3.4 Результат решения задачи планирования производства

4. Программа для решения задач ЛП симплекс методом

4.1 Описание

4.2 Графическое представление программы

4.3 Работа с программой

4.4 Схема программы

Заключение

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

Введение

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

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

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

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

улучшение финансовых показателей;

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

наращивание объемов производства.

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

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

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

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

2) Основные производственные фонды нуждаются в постоянной эксплуатации, наладке и обслуживании. Простои оборудования – это всегда неблагоприятный фактор для производства.

Планом выпуска продукции определяются:

Количественные показатели производства;

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

Для каждого периода, охватываемого планом, необходимо определить две переменные: объём производства в данный период; количество ресурсов, используемых в данный период.

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

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

Целесообразно совершенствовать структуру выпуска только той продукции, удельный вес которой в общем объеме выпуска достаточно высок.

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

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

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

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

1. Обзор научно-технической литературы

1.1 История развития экономико-математического планирования

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

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

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

1.2 Необходимость решения задач линейного программирования

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