Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Принцип работы симплекс-метода

ББК 22.161 | Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП) | Примеры задач ЛП | Графический метод решения задач ЛП | Приведение задач ЛП к стандартной форме | Порядок выполнения работ | Теоретическое введение | Определение оптимального решения на основе симплекс-таблиц | Решение задач линейного программирования средствами табличного процессора Ехсеl | Анализ оптимального решения на чувствительность |


Читайте также:
  1. D. Принципи виваженості харчування та поступового розширення обсягу харчових предметів, що споживаються
  2. I. ЗАДАНИЯ ДЛЯ АУДИТОРНОЙ РАБОТЫ
  3. I. Итоговая государственная аттестация включает защиту бакалаврской выпускной квалификационной работы
  4. I. Цель работы
  5. I. Цель работы
  6. I. Цель работы
  7. I. Цель работы.

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

Поиск решения на основе симплекс-метода реализуется с помощью симплекс-таблиц. Основные этапы реализации симплекс-метода следующие.

1. Задача линейного программирования приводится к стандартной форме.

2. Определяется начальное допустимое решение (начальная угловая точка ОДР).

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

Реализация симплекс-метода существенно различается в зависимости от вида математической модели задачи. В данной лабораторной работе рассматривается реализация симплекс-метода для случая, когда математическая модель задачи состоит только из ограничений «меньше или равно», и целевая функция подлежит максимизации (как в примере 2.1). Реализация симплекс-метода для задач с математической моделью любого вида рассматривается в лабораторной работе № 3.

 


Дата добавления: 2015-07-21; просмотров: 83 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Методика выполнения работы| Определение начального допустимого решения

mybiblioteka.su - 2015-2024 год. (0.005 сек.)