Обзор научно-технической литературы
Линейное программирование
Целочисленное линейное программирование - метод ветвей и границ
Алгоритм
Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel
Постановка задачи планирования производства в общем случае
Решение поставленной задачи планирования производства
Проверка признака допустимости и оптимальности базиса
Схема программы
Навигация
Решения задачи планирования производства симплекс методом
Решения задачи планирования производства симплекс методом
82416
знаков
8
таблиц
19
изображений
Федеральное агентство по образованию
Санкт-Петербургский Государственный Политехнический Университет
Факультет технической кибернетики
Кафедра «Системный анализ и управление»
Работа допущена к защите
Заведующий кафедрой
____________ В.Н. Козлов
«___» __________ 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 учетной единицы продукции. Ожидаемая средняя цена реализации определяется на основе ретроспективного анализа данных за предыдущие несколько лет с учетом ожидаемых и текущих темпов инфляции.
Для каждого периода, охватываемого планом, необходимо определить две переменные: объём производства в данный период; количество ресурсов, используемых в данный период.
План выпуска продукции отражает номенклатуру и ассортимент производства продукции в соответствии с планом реализации, обязательствами предприятия и экономическими условиями.
Планирование выпускаемой продукции включает решение ряда задач. Прежде всего, планируется номенклатура, ассортимент и объем выпуска продукции. Номенклатура производства представляет собой перечень изделий (готовых изделий, полуфабрикатов и т. п.), подлежащих изготовлению на предприятии в плановом периоде. Ассортимент продукции характеризует соотношение удельных весов отдельных видов изделий в общем, выпуске продукции. Номенклатура, ассортимент и объем изготовляемой предприятием продукции устанавливаются на основе централизованного задания по поставкам важнейших видов продукции и портфеля заказов предприятия с учетом его специализации. При этом учитываются и договоры по кооперированным поставкам, заключенные предприятием.
Целесообразно совершенствовать структуру выпуска только той продукции, удельный вес которой в общем объеме выпуска достаточно высок.
Необходимым условием увеличения количества производства определенных изделий является универсальность оборудования для их производства.
План выпуска продукции может повлиять на величину целого ряда издержек, в том числе: издержки хранения готовой продукции; издержки ведения портфеля отложенных заказав; издержки, связанные с внеурочной работой или простоем работников; издержки, связанные с передачей части работ субподрядчикам; издержки, связанные с наймом и увольнением работников.
Задача оптимизации структуры сырья при планировании выпуска продукции должна решаться на каждом промышленном предприятии, которое заинтересовано в максимизации прибыли от продажи выпускаемой продукции. Такая задача является задачей линейного программирования.
Данная дипломная работа состоит из теоретической и практической частей. В теоретической части рассматривается алгоритм решения оптимизационной задачи линейного программирования. В практической части рассматривается задача планирования производства выпускающего несколько видов продукции из ограниченного количества ресурсов для достижения максимальной прибыли. Так же реализуется программный интерфейс в среде объектно-ориентированного программирования С++, для решения поставленной задачи симплекс методом.
Похожие работы
... положит в такой симплекс-таблице текущие базисные переменные равными Ai,0, а свободные - нулю, то будет получено оптимальное решение. Практика применения симплекс метода показала, что число итераций, требуемых для решения задачи линейного программирования обычно колеблется от 2m до 3m, хотя для некоторых специально построенных задач вычисления по правилам симплекс метода превращаются в прямой ...
... определение базисных решений соответст- вует идентификации экстремальных точек , осуществляемой при геометрическом представлении пространства решений . Таким об- разом , максимальное число итераций при использовании симплекс- метода равно максимальному числу базисных решений задачи ЛП , представленной в стандартной форме . Это означает , что количество итерационных процедур симплекс-метода не ...
... - метод для решения задач линейного программирования. Задачи курсовой заботы: 1. привести теоретический материал; 2. на примерах рассмотреть симплекс метод; 3. представить данную курсовую работу в виде презентации. Математическое программирование Математическое программирование занимается изучение экстремальных задач и поиском методов их решения. Задачи ...
... предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации. Формулировка задачи линейного программирования Нужно максимизировать при условиях при i = 1, 2, 3, . . ., m.. Иногда на xi также накладывается некоторый набор ограничений в виде равенств, но от ...
0 комментариев