Глава 15. Целочисленные задачи линейного программирования
Цели
Нередко приходится рассматривать задачи, в которых неизвестные величины могут принимать только целочисленные значения. Например, задачи, связанные с определением необходимого числа рабочих мест или количества дорогостоящих станков. При решении таких задач с целочисленными переменными методы линейного (выпуклого) программирования неприменимы.
Другая сфера применения целочисленных моделей — выбор вариантов. В соответствующих задачах все или некоторые переменные могут принимать только два значения: 0 или 1. Такие переменные носят название булевых.
Наиболее известные методы решения целочисленных задач — метод отсечения и метод ветвей и границ. Они разработаны в начале 60-х годов XX века и затем неоднократно усовершенствовались и модифицировались. Решения примеров и задач, приводимых в этой главе, получены с помощью метода ветвей и границ и являются точными.
После того как вы выполните задания, предлагаемые в этой главе, вы будете уметь использовать для экономического анализа следующие понятия:
• неделимость;
• целочисленная задача;
• целочисленная и булева переменные;
• взаимоисключение и взаимообусловленность.
Модели
Дискретные (целочисленные) задачи математического программирования могут возникать различными путями. Существуют задачи линейного программирования, которые формально к целочисленным не относятся (требование целочисленности переменных в них в явном виде не накладывается), но которые при целочисленных исходных данных всегда обладают целочисленным планом. Этим свойством обладают транспортная задача и различные ее варианты (задача о назначениях).
Первоначальным стимулом к изучению целочисленных и дискретных задач явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины (скажем, количество единиц продукции разных видов). Для характеристики этого класса моделей используется термин «задачи с неделимостями».
Другим важным толчком к построению теории дискретного программирования явился новый подход к некоторым экстремальным комбинаторным задачам, для решения которых приходится вводить булевы переменные, носящие логический характер (х = 1 или х = 0).
К целочисленным (точнее, частично целочисленным) задачам линейного программирования удается свести также ряд задач, в которых явное требование целочисленности отсутствует, зато имеются некоторые особенности, выводящие их за рамки линейного программирования. Эти особенности могут относиться либо к целевой функции, либо к области допустимых решений.
Итак, можно выделить следующие основные классы задач дискретного программирования:
1) транспортная задача (см. главу 5) и ее варианты;
2) задачи с неделимостями;
3) экстремальные комбинаторные задачи;
4) задачи с неоднородной разрывной целевой функцией (см. транспортную задачу с фиксированными доплатами в главе 5);
5) задачи на неклассических областях (см. модель оптимального размера заказа с количественными скидками в главе 12).
Целочисленная задача линейного программирования (задача с неделимостями). К данному классу принадлежат задачи распределения капиталовложении и задачи планирования производства.
Целочисленная задача линейного программирования заключается в максимизации функции:
(1)
при условиях
(2)
где J — некоторое подмножество множества индексов N = ={1,2,...,n}.
Если J = N (T.e. требование целочисленности наложено на все переменные), то задачу называют полностью целочисленной; если же J ¹ N, она называется частично целочисленной.
 | ... | 106 | 107 | 108 | 109 | 110 | 111 | 112 | 113 | 114 | 115 | 116 | 117 | 118 | 119 | 120 | ... |
| Книжный магазин Большой выбор книг в интернет-магазине |
| Бюджетирование Ресурсное и финансовое планирование при составлении бюджета предприятия |
| План производства Оптимизация многовариантного производства при ресурсных ограничениях |
| Себестоимость Калькулирование плановой и фактической себестоимостей продукции и услуг |
| Финансовый анализ Анализ бухгалтеской отчетности в MS Excel в документы MS Word |
| Самиздат Статьи и публикации наших партнеров |
Аттестация рабочих мест по условиям труда в организация. Рекомендации и нормативные документы Сборник может быть полезен руководителям и специалистам организаций при подготовке и проведении аттестации рабочих мест по условиям труда. В сборнике даны представления об опасных и вредных производственных факторах на рабочих местах, оценке условий труда по классам, оценки травмоопасности рабочих мест, о сертификации работ по охране труда. Также представлена нормативно-справочная база для проведения аттестации рабочих мест.
5S для офиса. Как организовать эффективное рабочее место Это первая книга в России о том, как при помощи 5S организовать эффективное рабочее место в офисе. Система 5S - это инструмент, позволяющий оптимизировать и поддерживать комфортную и производительную рабочую среду. Помимо этого система 5S полезна при подготовке к сертификации по стандартам ISO 9000 и 9001. В книге представлен пошаговый план внедрения системы 5S с шаблонами форм, контрольных листов и другими необходимыми материалами. Знания, почерпнутые из этой книги, с успехом можно использовать в банках, страховых, консультационных и других компаниях сферы услуг, государственных, социальных и образовательных учреждениях. Предлагаемые советы об организации эффективного рабочего места столь универсальны, что книгу можно рекомендовать широкому кругу читателей.
Моббинг. Психотеррор на рабочем месте и методы его преодоления Моббинг - это отнюдь не новшество, это просто описание старого факта эскалации конфликтов на работе новым термином, что позволяет по-новому взглянуть на проблему. Формы моббинга разнообразны: постоянная критика, игнорирование вплоть до полной изоляции, завышенные или заниженные требования, бессмысленные или вредные для здоровья задания, угрозы и сексуальные домогательства на рабочем месте... Обо всем этом рассказывает данная книга: от истоков конфликтов - до их последствий, от способов предотвратить моббинг - до возможностей его преодолеть. Примеры из жизни показывают атмосферу, в которой оказываются жертвы моббинга, и выявляют те переживания и мысли, которые помогают им, в конце концов, выйти из замкнутого круга. Книга будет полезна психологам и социологам, социальным работникам и практикам, и, прежде всего, менеджерам и специалистам по персоналу.
Великолепный коучинг. Как стать блестящим коучем на своем рабочем месте Коучинг, как способ обучения людей самостоятельному поиску знаний, применению их в жизни и достижению успеха, в последнее время приобрел большую популярность и стал необходим для каждого руководителя. Эта книга посвящена отдельно взятой сфере применения искусства коучинга - коучингу на рабочем месте. Ее автор, Джули Старр, - тренер и консультант с более чем двадцатилетним опытом работы в области коучинга. Метод Старр, специально разработанный и испытанный в сфере бизнеса, основан на психологическом консультировании. Автор учит читателя находить взаимопонимание с собеседником и задавать эффективные вопросы, а также раскрывает принцип "концентрированного" внимания и - главное - показывает действие метода в самых распространенных "сценариях". Кроме того, в книге приведены упражнения, которые помогут вам закрепить полученные знания и в дальнейшем с успехом применять их практике. Благодаря этой книге, вы сможете по-новому взглянуть на знакомые ситуации, в которых принципы...
Великолепный коучинг. Как стать блестящим коучем на своем рабочем месте Коучинг, как способ обучения людей самостоятельному поиску знаний, применению их в жизни и достижению успеха, в последнее время приобрел большую популярность и стал необходим для каждого руководителя. Эта книга посвящена отдельно взятой сфере применения искусства коучинга - коучингу на рабочем месте. Ее автор, Джули Старр, - тренер и консультант с более чем двадцатилетним опытом работы в области коучинга. Метод Старр, специально разработанный и испытанный в сфере бизнеса, основан на психологическом консультировании. Автор учит читателя находить взаимопонимание с собеседником и задавать эффективные вопросы, а также раскрывает принцип "концентрированного" внимания и - главное - показывает действие метода в самых распространенных "сценариях". Кроме того, в книге приведены упражнения, которые помогут вам закрепить полученные знания и в дальнейшем с успехом применять их практике. Благодаря этой книге, вы сможете по-новому взглянуть на знакомые ситуации, в которых принципы...
Заставьте офис работать на вас! Как добиться комфорта, легкости и эффективности на своем рабочем месте Задумывались ли вы когда-нибудь о том, что рабочее место - это ваша визитная карточка? Офис может как способствовать вашему карьерному росту, так и загубить вашу карьеру на корню, кроме того - он влияет на вашу активность и даже самочувствие. Какие же подводные камни скрывается за внешним фасадом благополучия? Доктор социологических наук Джен Ягер провела более 200 открытых и "тайных" исследований и интервью, устраиваясь на временную работу в различные офисы, проанализировала множество анкет респондентов, чтобы выяснить ключевые организационные проблемы, которые должны разрешить все менеджеры для эффективной работы в тех рабочих пространствах, где они руководят. Книга адресована всем тем, кто хочет организовать для себя идеальное рабочее пространство, которое вызывает ощущение комфорта, снижает стресс, повышает производительность труда и создает у посетителей положительное впечатление о его владельце.
Зачем мы работаем. Как найти смысл и вдохновение на рабочем месте Цитата "Тот, кто нашел смысл, ярче и полнее живет в любых обстоятельствах — или находит в себе силы изменить их. Найти смысл в работе — все равно что найти смысл жизни". О чем книга Что наделяет жизнь смыслом — отдых, учеба, любовь, служение ближнему, создание бизнеса? Люди находят смысл в самых разных местах и видах деятельности. Его ищут практически везде. И работа — универсальная среда для этого поиска. Работа всегда остается работой — она бывает и монотонной, и рутинной, и предельно напряженной. И все же мы видим в ней нечто большее, чем просто средство получения денег. Руководитель может помочь своим сотрудникам в поисках смысла. Более того, ему необходимо это сделать, поскольку осмысленная работа прибыльна. Создать смысл на рабочем месте вам помогут семь стимулов, cемь вопросов и семь наборов инструментов, предлагаемых авторами книги. Почему книга достойна прочтения Книга отвечает на два вопроса о смысле труда — зачем и как. "Зачем"...
Журнал регистрации инструктажа на рабочем месте Издание представляет собой журнал регистрации инструктажа на рабочем месте. Формат: 20,5 см х 26 см.
Офисная йога. Снятие усталости на рабочем месте 
Обеспечение защиты персональных данных (+ CD-ROM) Персональные данные хранятся и обрабатываются в любой организации, а это значит, что вопросы защиты таких данных актуальны для широкого круга лиц. К 1 июля 2011 года все информационные системы персональных данных должны быть приведены в соответствие с требованиями Федерального закона от 27.07.2006 №152-ФЗ "О персональных данных". Комплекс необходимых мер по обеспечению безопасности персональных данных включает мероприятия правового, организационного и технического характера. Предлагаемое пособие содержит пошаговые инструкции и типовые формы документов, наличие которые обязательно при осуществлении мероприятий по защите персональных данных. В отдельном разделе пособия рассмотрены вопросы применения программных продуктов, разработанных фирмой "1С", с учетом требований, предъявляемых законодательством Российской Федерации о защите персональных данных. В 3-м издании книги учтены изменения в законодательстве декабря 2010 года! К книге прилагается CD, на котором в...