Эффективное решение производственных проблем и задач

Реферат: решения задачки планирования производства симплекс способом — xreferat.ru — банк рефератов, сочинений, докладов, курсовых и дипломных работ

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

Санкт-Петербургский
Муниципальный
Политехнический
Институт

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

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

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

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

____________ В.Н. Козлов

«___» __________ 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 Необходимость
решения задач
линейного
программирования

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

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

К числу их
следует отнести:
сложность
определения
аспекта
оптимальности
в ряде экономических
задач; трудности
при решении
препядствия
«встраивания»
математических
моделей в
существующую
систему планирования
и управления,
приводящие
к необходимости
сотворения новейшей
технологии
планирования,
базирующегося
на системном
использовании
экономико-математических
способов и ЭВМ;
стохастический
и динамический
нрав
экономических
процессов,
требующий
усложнения
применяемого
математического
аппарата и
программного
обеспечения
ЭВМ, роста
объема вычислений;
трудность
измерений
многих экономических
явлений и получения
массовой достоверной
инфы
для заполнения
разработанных
моделей; трудность
проверки корректности
(верификации)
экономикоматематических
моделей, нацеленных
не столько на
доказательство
реальности,
сколько на
решение новых
социально-экономических
задач (это в
первую очередь
относится к
моделям планирования
и прогнозирования),
и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

Первым исследованием
по линейному
программированию
является работа
Л. В. Канторовича
"Математические
способы организации
и планирования
производства",
размещенная
в 1939 г. В нем дана
постановка
задач линейного
программирования,
разработан
способ разрешающих
множителей
решения задач
линейного
программирования
и дано его
теоретическое
обоснование.

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

Математическое
программирование
– это прикладная
ветвь арифметики,
которая является
теоретической
основой решения
задач рационального
планирования.

Есть
последующие
разделы математического
программирования:
линейное,
параметрическое,
нелинейное
и динамическое
программирование.
Более
разработанным
и обширно используемым
разделом
математического
программирования
является линейное
программирование,
целью которого
служит отыскивание
оптимума (max, min)
данной линейной
функции при
наличии ограничений
в виде линейных
уравнений либо
неравенств.

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

Линейное
программирование
— математическая
дисциплина,
посвященная
теории и способам
решения задач
об экстремумах
линейных функций
на огромных количествах
n-мерного векторного
места,
задаваемых
системами
линейных уравнений
и неравенств.

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

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

Термин
«программирование»
необходимо осознавать
в смысле «планирования».
Он был предложен
посреди
1940-х годов Джорджем
Данцигом, одним
из основоположников
линейного
программирования,
еще до того,
как компы
были применены
для решения
линейных задач
оптимизации.

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

Необходимо найти
максимум линейной
мотивированной функции
(линейной формы)

при
критериях

при

Время от времени
на xi также накладывается
некий набор
ограничений
в виде равенств,
но от их можно
избавиться,
поочередно
выражая одну
переменную
через другие
и подставляя
ее во всех других
равенствах
и неравенствах
(также в функции
f).

Такую
задачку именуют
"основной"
либо "стандартной"
в линейном
программировании.

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

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

Задачка линейного
целочисленного
программирования
формируется
последующим
образом: отыскать
такое решение
(план) X = (x1,x2,...,xn), при
котором линейная
функция

(1)

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

=bi,
i=1, 2…,m. (2)

хj і
0, j=1, 2,...,n.(3)

xj — целые числа
(4)

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

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

Целочисленное
линейное
программирование
(сокращенно
ЦЛП) занимается
задачками линейного
программирования
с целочисленными
переменными,
общая задачка
формулируется
последующим
образом: отыскать
maxАх ≤ b; х - целочисленный.
ЦЛП может
рассматриваться
так же, как поиск
точки решетки,
принадлежащей
полиэдру
либо как решение
системы линейных
уравнений с
целыми неотрицательными
переменными.
Другими словами,
в ЦЛП рассматриваются
совместные
ограничения
неотрицательность
и целочисленность.

2.1.1 Отсечения

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

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

Описываемая
ниже версия
метода
предназначена
для решения
стопроцентно
целочисленных
задач, т.е. таких,
у каких все
характеристики aij,
cj, bi – целые.

2.1.2 Описание
метода

Приведем
обобщенную
схему метода
Гомори. Структурно
он делится на
так именуемые
огромные итерации.
Любая большая
итерация содержит
этапы:

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

2. В рациональном
плане (симплекс-таблице)
выбирают строчку,
в какой целая
часть дробного(!)
свободного
члена (P0) воспринимает
наибольшее
значение.

3.Построение
для отысканной
составляющие
условия отсечения.

Исходя из
уравнения по
данной строке
xr=P0r - ar,1*x1 - … - ar,n*xn в систему
ограничений
добавляем
неравенство,
в каком
коэффициенты
будут дробными
частями коэффициентов
данного уравнения:

{P0r} –{ar,1}*x1 - … -{ar,n}*xn ≤ 0.

Переводим
к каноническому
виду добавляя
новейшую переменную
xn+1, получим:

{P0r} –{ ar,1}*x1 - … - {ar,n}*xn+xn+1= 0

И соответственно
добавляем в
симплекс-таблицу
новый базовый
вектор по новейшей
переменной
xn+1.

4.Переход на
начало последующей
большой итерации.

Замечание:

При добавлении
в симплекс-таблицу
нового базового
вектора по
новейшей переменной
xn+1 мы получаем
недопустимое
(отрицательное)
решение. Для
того, чтоб
избавиться
от недопустимого
решения избираем
столбец замещения
так, чтоб строчкой
замещения стала
новенькая добавленная
строчка по переменной
xn+1. Продолжаем
пересчет
симплекс-таблицы.
Если опять
получаем дробное
решение, то еще
вводим дополнительный
базовый вектор,
и так до получения
целочисленного
решения. Но
следует увидеть,
что если область
допустимых
решений очень
мала, то она
может и не содержать
целых значений,
это нужно
проверить
графически.
Если область
допустимых
решений не
содержит
целочисленного
решения, то в
применении
способа Гомори
нет необходимости,
целого решения
не будет!

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

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

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

Способ был
в первый раз предложен
Ленд и Дойг в
1960 г. для решения
задач целочисленного
линейного
программирования.

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

Общая мысль
способа может
быть описана
на примере
поиска минимума
и максимума
функции f(x) на
огромном количестве
допустимых
значений x. Функция
f и x могут быть
случайной
природы. Для
способа веток
и границ нужны
две процедуры:
ветвление и
нахождение
оценок (границ).

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

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

В базе
способа веток
и границ лежит
последующая мысль
(для задачки
минимизации):
если нижняя
граница для
подобласти
A дерева поиска
больше, чем
верхняя граница
какой-нибудь
ранее просмотренной
подобласти
B, то A может быть
исключена из
предстоящего
рассмотрения
(правило отсева).
Обычно, наименьшую
из приобретенных
верхних оценок
записывают
в глобальную
переменную
m; хоть какой узел
дерева поиска,
нижняя граница
которого больше
значения m, может
быть исключен
из предстоящего
рассмотрения.

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

2.2.2 Применение

Способ употребляется
для решения
неких
NP-трудных задач,
такие как:

Задачка коммивояжера

Задачка о портфеле

2.2.3 Метод
решения

Сначало
находим симплексным
способом либо
способом искусственного
базиса лучший
план задачки
без учета
целочисленности
переменных.
Пусть им является
план X0. Если посреди
компонент этого
плана нет дробных
чисел, то тем
самым найдено
разыскиваемое решение
данной задачки
и Fmax = F(Xo).

Если же посреди
компонент плана
X0 имеются дробные
числа, то X0 не
удовлетворяет
условию целочисленности
и нужно
выполнить
упорядоченный
переход к новым
планам, пока
не будет найдено
решение задачки.
Покажем, как
это можно сделать,
за ранее
отметив, что
F(X0) і
F(X) для всякого
следующего
плана X.

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

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

Найдем решение
задач линейного
программирования
(I) и (II). Разумеется,
тут вероятен
один из последующих
4 случаев:

1. Одна из задач
неразрешима,
а другая имеет
целочисленный
лучший
план. Тогда
этот план и
значение мотивированной
функции на нем
и дают решение
начальной задачки.

2. Одна из задач
неразрешима,
а другая имеет
лучший
план, посреди
компонент
которого есть
дробные числа.
Тогда рассматриваем
вторую задачку
и в ее рациональном
плане избираем
одну из компонент,
значение которой
равно дробному
числу, и строим
две задачки,
подобные
задачкам (I) и (II).

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

Если же значение
мотивированной функции
больше на плане,
посреди компонент
которого есть
дробные числа,
то следует
взять одно из
таких чисел
и для задачки,
план которой
рассматривается,
нужно
выстроить две
задачки, подобные
(I) и (II).

4. Обе задачки
разрешимы, и
посреди хороших
планов обеих
задач есть
дробные числа.
Тогда вычисляем
значение мотивированной
функции на
данных хороших
планах и рассматриваем
ту из задач,
для которой
значение мотивированной
функции является
большим.
В рациональном
плане этой
задачки избираем
одну из компонент,
значение которой
является дробным
числом, и строим
две задачки,
подобные
(I) и (II).

Таким макаром,
описанный чуть повыше
итерационный
процесс может
быть представлен
в виде некого
дерева, на котором
начальная верхушка
отвечает хорошему
плану Х0 задачки
(1)-(3), а любая
соединенная
с ней ветвью
верхушка отвечает
хорошим
планам задач
(I) и (II). Любая из
этих вершин
имеет свои
ветвления. При
этом на каждом
шаге выбирается
та верхушка, для
которой значение
функции является
большим.
Если на неком
шаге будет
получен план,
имеющий целочисленные
составляющие,
и значение
функции на нем
окажется больше
либо равно, чем
значение функции
в других вероятных
для ветвления
верхушках, то
данный план
является хорошим
планом начальной
задачки целочисленного
программирования
и значение
мотивированной функции
на нем является
наибольшим.

Итак, процесс
нахождения
решения задачки
целочисленного
программирования
(1)-(4) способом веток
и границ включает
последующие
главные этапы:

1). Находят
решение задачки
линейного
программирования
(1)-(3).

2). Составляют
дополнительные
ограничения
для одной из
переменных,
значение которой
в рациональном
плане задачки
(1)-(3) является
дробным числом.

3). Находят
решение задач
(I) и (II), которые
получаются
из задачки (1)-(3) в
итоге
присоединения
дополнительных
ограничений.

4). В случае
необходимости
составляют
дополнительные
ограничения
для переменной,
значение которой
является дробным,
определяют
задачки, подобные
задачкам (I) и (II), и
находят их
решение.

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

Описанный
выше способ
веток и границ
имеет более
ординарную логическую
схему расчетов,
чем способ Гомори.

В узлах способа
веток и границ
употребляется
симплекс-метод.

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

2.3 Симплекс
способ

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

2.3.1 Описание

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

2.3.2 Метод
симплекс-метода

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

Задачки линейного
программирования
имеет последующий
вид:

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

и

— наилучшее
решение задачки
и изначальное
приближение
для симплекс-метода,
которые в
симплекс-методе
являются базовыми
решениями,
определяемыми
ниже. Векторы

и

представляют
собой следующее
и предшествующее
решения в
симплекс-методе.

2.3.2.2 Метод

Метод
симплекс-метода
формулируется
для задачки
линейного
программирования
последующим
образом:

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

в симплекс-таблицу(*),
а коэффициенты
мотивированной функции

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

Таблица (*)

#№
Базовые
столбцы
Bs
Базовое
решение Xs
C1
C2
…
Cm
Cm+1
…
Ck
…
Cn

A1
A2
…
Am
Am+1
…
Ak
…
An
1
A1

1
0
…
0

…

…

2
A2

0
1
…
0

…

…

…
…
…
…
…
…
…
…
…
…
…
…
…
l
Al

0
0
…
0

…

…

…
…
…
…
…
…
…
…
…
…
…
…
…
m
Am

0
0
…
1

…

…

Оценки

…

…

…

Шаг 2. Вычисление
характеристических
разностей
(оценок) по формулам
и запись оценок
в