6266

Симплексный метод принятия оптимального управленческого решения

Реферат

Менеджмент, консалтинг и предпринимательство

Симплексный метод принятия оптимального управленческого решения Содержание Виды математических моделей ЗЛП. Идея симплексного метода нахождения оптимального решения. Алгоритм симплексного метода. Нахождение оптимального решен...

Русский

2012-12-31

113 KB

39 чел.

Симплексный метод принятия оптимального управленческого решения

Содержание

  1.  Виды математических моделей ЗЛП.
  2.  Идея симплексного метода нахождения оптимального решения.
  3.  Алгоритм симплексного метода.
  4.  Нахождение оптимального решения производственной задачи.

1. Виды математических моделей ЗЛП

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

Если все ограничения системы заданы уравнениями и все переменные  неотрицательные, то такая модель ЗЛП называется канонической. Математическая модель ЗЛП в канонической форме имеет вид

при ограничениях

,  

Если хотя бы одно ограничение является неравенством, то модель задачи ЛП является неканонической.

Чтобы перейти от неканонической модели к канонической, необходимо в каждое неравенство ввести балансовую переменную . Если знак   неравенства , то балансовая переменная вводится со знаком плюс, если знак неравенства , то - минус. В целевую функцию балансовые переменные не вводятся.

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

Множество допустимых решений ЗЛП называют областью допустимых решений ЗЛП. 

Допустимое решение , при котором целевая функция  достигает экстремального значения, называют оптимальным решением ЗЛП и обозначается .

2. Идея симплексного метода нахождения оптимального решения

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

Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс–таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.

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

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

3. Алгоритм симплексного метода

Математическую модель задачи привести к каноническому виду.

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

2. Найти разрешающий столбец (в строке коэффициентов ЦФ найти значение с наименьшим отрицательным числом. Этот столбец и будет разрешающим).

3. Определить разрешающую строку (почленно разделить столбец свободных членов на элементы разрешающего столбца, за исключением строки ЦФ. Выбрать наименьшее из частных. Эта строка будет разрешающей). Разрешающий элемент будет на пересечении разрешающего столбца и разрешающей строки.

4. Построить вторую симплекс-таблицу.

Построение элементов разрешающей строки (почленно поделить всю разрешающую строку на разрешающий элемент).

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

                                         .

Схематично «правило прямоугольника» выглядит так:

                                                                       

                                                                          

Здесь  - пересчитываемый элемент,  - новое значение элемента ,  - разрешающий элемент.

При построении новой таблицы «убирается» из базиса строка с переменной разрешающей строки в предыдущей таблице, а «вводится» в базис строка с названием разрешающего столбца предыдущей таблицы.

5. Проверяем полученную симплекс-таблицу второго шага на оптимальность.

Если в строке целевой функции нет отрицательных элементов, тогда симплекс-таблица имеет оптимальный план.

6. Записать оптимальное решение задачи и значение целевой функции, используя столбец свободных членов. В решении Х базисные переменные приравниваются свободным членам, а остальные переменные приравниваются к нулю: . Значение целевой функции равно свободному члену в строке ЦФ.

Если в строке ЦФ есть отрицательный элемент (элементы), тогда переходят к следующему (третьему) шагу.

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

8. Замечание.

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

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

Задача. На предприятии имеется возможность выпускать  вида продукции , , , . При ее изготовлении используются ресурсы , , , размеры которых ограничены соответственно величинами , , . 4Расход -го ресурса на единицу продукции -го вида составляют  и образуют «технологическую матрицу» .

Прибыль от реализации единицы продукции , , ,  равна  ден. ед.

  1.  Построить математическую модель задачи. Раскрыть экономический смысл всех переменных.
  2.  Найти оптимальный план производства симплекс-методом.

Математическая модель задачи

  •  основные переменные  (=1,…,4) – количество произведенной продукции ; ;
  •  целевая функция – прибыль от реализации всей продукции.

,

  •  ограничения: расход ресурсов не превышает запасов:

Канонический вид математической модели для решения симплексным методом (добавим дополнительные переменные):

Экономический смысл дополнительных переменных:

  •    (=5, 6,  7) – количество неиспользованного ресурса , , .

Симплексные таблицы.

Таблица 1

Базис

х1

х2

х3 

х4

х5

х6

х7

bi

Отношение

х5

х6

х7

2

4

3

3

1

5

2

3

2

1

2

2

1

0

0

0

1

0

0

0

1

25

30

42

12,5

7,5

14

–6

–5

–4

–3

0

0

0

0

Таблица 2

Базис

х1

х2

х3 

х4

х5

х6

х7

bi

Отношение

х5

х1

х7

0

1

0

2,5

0,25

4,25

0,5

0,75

-0,3

0

0,5

0,5

1

0

0

-0,5

0,25

-0,8

0

0

1

10

7,5

19,5

4

30

4,59

0

-3,5

0,5

0

0

1,5

0

45

-

Таблица 3

Базис

х1

х2

х3 

х4

х5

х6

х7

bi

Отношение

х2

х1

х7

1

0

0

0

1

0

0,2

0,7

-1,1

0

0,5

0,5

0,4

-0,1

-1,7

-0,2

0,3

0,1

0

0

1

4

6,5

2,5

0

0

1,2

0

1,4

0,8

0

59

Анализ оптимального решения  и значения целевой функции .

Чтобы получить наибольшую прибыль  ден. единиц, необходимо произвести 6,5 ед. продукции первого вида , 4 ед. продукции второго вида , а продукции третьего  и четвертого  видов не производить. Ресурсы  и  дефицитны (остаток ресурсов ), ресурс  избыточен (остаток ресурса равен ).


Контрольные вопросы

Симплексный метод решения ЗЛП

  1.  Запишите задачу ЛП в канонической, стандартной  форме.
  2.  С помощью каких преобразований можно перейти от общей или стандартной ЗЛП к канонической?
  3.  Сформулируйте основную идею симплексного метода решения ЗЛП.
  4.  Дайте определения допустимого решения, оптимального решения  ЗЛП.
  5.  Сформулируйте алгоритм симплексных преобразований в симплексных таблицах.
  6.  Таблица какого вида называется симплексной, как она заполняется?
  7.  Как по симплексной таблице записать компоненты опорного решения ЗЛП?
  8.  По каким правилам преобразуются элементы в симплексной таблице при переходе к новой симплексной таблице?
  9.  Как определить по симплексной таблице, что имеющееся опорное решение не является оптимальном, но его можно улучшить?
  10.  Чтобы перейти от опорного решения к улучшенному опорному решению, как нужно для ЗЛП выбрать разрешающий элемент?
  11.  Дайте понятие альтернативного оптимума ЗЛП.
  12.  Как получить общее оптимальное решение, если ЗЛП имеет альтернативный оптимум?
  13.  Дайте экономическую и математическую постановку прямой ЗЛП об использовании сырья для производства продукции нескольких видов. Каков экономический смысл основных и дополнительных переменных  в оптимальном решении ЗЛП об использовании ресурсов?


 

А также другие работы, которые могут Вас заинтересовать

47414. Автоматизация бухгалтерского учета в ООО «Иртех» 913 KB
  Целью данной выпускной квалификационной работы является систематизация, закрепление и расширение теоретических знаний и практических навыков бухгалтерского учета и экономического анализа расчетов по оплате труда, изучение организации бухгалтерского учета расчетов с персоналом по оплате труда в ООО «Иртех», экономический анализ фонда оплаты труда данного предприятия.
47415. Судебный контроль за принятием решений о возбуждении уголовного дела и об отказе в возбуждении уголовного дела 946.48 KB
  Понятие содержание и соотношение прокурорского надзора и судебного контроля на досудебных стадиях уголовного судопроизводства . Ретроспективный анализ развития прокурорского надзора в досудебных стадиях уголовного судопроизводства . Развитие идеи судебного контроля в досудебных стадиях уголовного судопроизводства . Соотношение прокурорского надзора и судебного контроля на досудебных стадиях уголовного судопроизводства .
47416. СОВЕРШЕНСТВОВАНИЕ УПРАВЛЕНИЯ ФИНАНСАМИ МУНИЦИПАЛЬНОГО ДОШКОЛЬНОГО ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ № 481 Г. ЧЕЛЯБИНСКА 662 KB
  Распорядители и получатели бюджетных средств на муниципальном уровне. Особую актуальность им придают хроническая нехватка средств местных бюджетов а также переход на казначейское исполнение бюджета в результате которых перед администрациями городов и районов остро стоят задачи оптимизации управления финансовыми ресурсами территории усиления контроля за целевым использованием бюджетных средств их получателями. Рассматриваются распорядители и получатели бюджетных средств на муниципальном уровне а также содержание...
47417. Опыт развития малых городов как туристских центров 1.44 MB
  Для сравнения будут взяты следующие населенные пункты: города Светлогорск Калининградской области Торжок Тверской области и Углич Ярославской области. Это объясняется тем что в Липецкой области Постановлением администрации Липецкой области №195 от 29. была создана Особая экономическая зона регионального уровня туристскорекреационного типа ОЭЗ РУ и согласно этому постановлению туристскорекреационный вид деятельности является одним из стратегических направлений развития области в целом и перспективным видом хозяйственного освоения её...
47418. Особенности государственной поддержки малого бизнеса в Республике Мордовия 578.5 KB
  Место и роль малого предпринимательства в рыночной экономики 1.1 Правовое регулирование малого бизнеса в России.2 Проблемы развития малого бизнеса в России 1.3 Методы и инструменты государственного регулирования малого бизнеса 2 Формы государственной поддержки малого бизнеса в России.
47419. Измельчительное оборудование 475.5 KB
  Применение современного измельчительного оборудования позволяет повысить производительность труда, сократить затраты и облегчить труд работников предприятий массового питания, улучшить качество изделий и сократить время обслуживания клиентов.
47420. Разработка дидактических средств развития пространственных представлений младшего школьника 1.6 MB
  Однако несмотря на то что необходимость изучения геометрического материала в курсе математики начальных классов и формирования на его основе пространственных представлений и пространственного мышления младших школьников не представляется спорной ни в одной из сегодняшних методических систем обучения математике в начальных классах структурный анализ содержания наиболее популярных сегодня учебных пособий по математике показывает крайне недостаточную содержательную разработанность этого вопроса в курсе математики начальных классов. Проблемами...
47421. Особенности методики развития скоростно-силовых способностей у школьников 5-х классов в процессе занятий физическими упражнениями 359 KB
  Большой вклад в теорию игры внесли Е.Ушинский считал что значение игры в развитии и воспитании личности уникально так как игра позволяет каждому ребенку ощутить себя субъектом проявить и развить свою личность. Одна из причин тому недостаточное внимание к разработке теории игры школьников. Сущность игры заключается в том что в ней важен не результат а сам процесс процесс переживаний связанных с игровыми действиями.
47422. Разработка системы приёмов организации и развития внимания детей 5 – 6 классов 367.5 KB
  Основные свойства внимания. Возрастные особенности внимания школьников. Организация внимания школьника. Наглядность как основной компонент развития внимания на уроках немецкого языка.