Симплекс-метод решения задачи линейного программирования. Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции. Алгоритм поиска оптимального плана
Симплекс-метод решения задачи линейного программирования
Стандартная форма задачи линейного программирования формулируется так: найти неотрицательные значения переменных , удовлетворяющих условиям:
…
и обращающих в максимум линейную функцию этих переменных
К этой форме можно свести любую задачу линейного программирования, рассмотренную в вопросе №1.
Оптимальное решение при использовании симплексного метода находят в соответствии со следующим алгоритмом.
Вначале находится некоторое допустимое базисное решение. Если n – число неизвестных, а m – число уравнений, то для определения базисного решения следует принять n-m переменных за свободные, приравнивая их число и разрешая получившуюся систему уравнений относительно базисных переменных. В том случае, когда некоторые базисные переменные окажутся отрицательными, необходимо выбрать другие базисные переменные.
Когда базисное решение будет допустимым, целевая функция проверяется на максимум. Если максимума целевой функции нет, то в новый базис включается переменная, увеличение которой приводит к увеличению целевой функции. Если же такой переменной нет, то найденное решение оптимально. В противном случае система уравнений разрешается относительно новых базисных переменных.
Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции
Исходная таблица
| x1 | x2… | xm | xm+1… | xn |
b1 | a11 | a12… | a1m | a1m+1… | a2n |
b2 | a21 | a22… | a2m | a2m+1… | a2n |
bk | ak1 | ak2… | akm | akm+1… | akn |
bm | am1 | am2… | amm | amm+1… | amn |
0 | c1 | c2… | cm | cm+1… | cn |
Переход к базису из векторов
| 1 | 0… | 0 |
|
|
| 0 | 1… | 0 | ….. | ….. |
| 0 | 0… | 0 | ….. | ….. |
| 0 | 0… | 0 | ….. | ….. |
| 0 | 0… | 1 |
|
|
| 0 | 0… | 0 |
|
|
{Нижняя строка – строка оценок; левый столбец – допустимый план; левый нижний квадрат – целевая функция с обратным знаком.}
Cтандартный алгоритм симплекс-метода
Для текущего базисного плана приводится критерий оптимальности: если в строке оценок нет положительного коэф. , план и задача решена.
Если среди ,…, есть >0, план можно улучшить за счет ввода в числе базисных той свободной переменной, для которой оценка макс.
Для определения переменной, которую следует внести из числа базисно, нужно просмотреть столбец матрицы A , соотв. включенной в базис новой переменной. Если все элементы этого столбца <=0, то задача решения не имеет. Если есть элементы> то выбирается тот, для которого величина / - min. Тем самым определяется базис перем., вывед из матрицы.
Столбец с ведущим элементом приводится к виду, в котором ведущий элемент равен 1, остальные – неизм.
Шаги 1-4 повторяют до тех пор, пока не будет получено оптимальное решение.
- Раздел 1. Теория автоматического управления
- Частотные характеристики систем управления и связь между ними
- Временные характеристики систем управления
- Типовые звенья систем управления
- Интегрирующее звено
- Консервативное звено
- Запаздывающее звено
- Частотные методы оценки устойчивости систем
- Методы построения логариф частотных хар-к
- Законы распределения и числовые характеристики случайных сигналов
- Оценка качества регулир. Показатели качества
- Передаточные функции дискретных су
- Алгебраический критерий устойчивости дискретных систем
- Частотный критерий устойчивости дискретных систем
- Метод гармонич линеариз нелин систем
- Раздел 2. Локальные системы управления
- Особенности математического описания объектов управления. Входные и выходные переменные. Векторы состояния, управления и возмущения. Оператор и переходная функция
- Д атчики систем автоматики
- Устойчивость датчиков к действию высокочастотных помех
- Двигатель постоянного тока как элемент автоматики. Принципиальная схема, основные уравнения движения
- Асинхронный двигатель как элемент автоматики. Структурная схема, передаточная функция, переходные характеристики
- Дискретные законы управления. Математическая модель дискретного управляющего устройства. Импульсные передаточные функции каналов дискретного уу
- Раздел 3. Вычислительные машины, системы
- Принципы построения вычислител машин
- Понятие логической функции. Полностью и неполностью определенные логические функции. Способы задания логических функций
- Комбинационные автоматы. Синтез комбинационных конечных автоматов
- Методы минимизации логических функций
- Модели вычислений. Многоуровневая организация вычислительных процессов
- Прерывания. Шина современных пк
- Типы и основные принципы построения периферийных устройств
- Многомашинные комплексы и многопроцессорные системы
- Управляющие вычислительные комплексы
- Раздел 4. Технические средства обработки текста и изображений
- Методика светоэнергетического расчета лазерного фотовыводного устройства
- Методика расчета параметров лазерных выводных устройств, определ скорость сканирования
- Структура, назначение и принцип работы проявочных машин. Основные системы автоматизации процессов обработки фотоматериалов
- Технические средства анализа и ввода изображения в систему допечатной обработки
- Основные виды, параметры и принцип работы источников и модуляторов лазерного излучения
- Структурная схема, назначение и принцип работы формовыводного устройства (рекордера)
- Основные этапы и характеристики электрофотографического процесса цветной электрофотографии. Структурная схема, назначение устройств и принцип работы аппарата цветной электрографии
- Принцип работы, назначение и разновидности струйных принтеров
- Структурная схема, назначение устройств и принцип работы лазерного принтера (одноцветный вариант)
- Структурная схема, назначение устройств и принцип работы лазерного фотонаборного автомата
- Цифровые печатные машины (цпм). Основные типы цпм и принцип работы
- Раздел 5. Автоматизированное управление полиграфическим производством
- Задачи управления дискретным производством: планирование ассортимента выпуска продукции, транспортная задача
- Симплекс-метод решения задачи линейного программирования. Табличная реализация симплекс-метода в задаче об ассортименте выпускаемой продукции. Алгоритм поиска оптимального плана
- Табличный метод решения транспортной задачи. Использование циклов пересчетов и метода потенциалов при поиске оптимального плана перевозок. Достаточное условие оптимальности
- Информационное обеспечение систем управления. Фактографические базы данных. Типы субд и их характеристики
- Документальные информационные системы, их характеристики. Информационный поиск в документальных системах, оценка полноты и релевантности. Модели поисковых образов
- Методы защиты информации в информационно-управляющих системах. Алгоритмы шифрования данных. Метод открытого ключа. Средства анализа защищенности компьютерных сетей