Вопросы 1) 1) Экономический смысл основных и дополнительных переменных в канонической форме задачи об оптимальном использовании ограниченных ресурсов. 2) 2) Основные свойства задачи линейного программирования. Основы симплекс-метода: общая схема алгоритма метода. 3) 3) Алгоритм симплексного метода с естественным базисом. 4) 4) особые случаи решения ЗЛП симплексным методом. 1

Экономический смысл основных и дополнительных переменных в канонической форме задачи об оптимальном использовании ограниченных ресурсов (на примере задачи о коврах). 7x 1 +2x 2 +2x 3 +6x 4 +х 5 = 80, 5x 1 +8x 2 +4x 3 +3x 4 +х 6 = 480, 2x 1 +4x 2 +x 3 +8 x 4 +х 7 =130, x 1, x 2, x 3, x 4, х 5, х 6, х

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

Симплексный метод Планом, или допустимым решением задачи КЗЛП, называется вектор, удовлетворяющий условиям функциональным и прямым ограничениям КЗЛП. Если все компоненты базисного решения системы ограничений КЗЛП неотрицательны, то такое решение называется опорным решением или опорным планом. Число положительных компонент опорного плана не может превышать. Опорный план называется невырожденным, если он содержит положительных компонент, в противном случае опорный план называется вырожденным. Оптимальным планом или оптимальным решением задачи линейного программирования называется план, доставляющий наибольшее значение линейной функции. 4

Алгоритм метода рассмотрим на примере. Для производства двух видов продукции предприятие использует два вида сырья. Данные приведены в таблице. Составить opt план производства на max прибыли. Сырье Расход сырья на производство ед. прод. Количество сырья, т I вида II вида A13300 B11150 Прибыль, д. ед. / ед. продукции 23 Пример

Решение Введем обозначения: Введем обозначения: x 1 - объем производимой продукции I вида; x 2 - объем производимой продукции II вида Составим экономико-математическую модель: Составим экономико-математическую модель: max f( x ) = 2· x 1 + 3· x 2, max f( x ) = 2· x 1 + 3· x 2, 1· x 1 + 3· x 2 300, 1· x 1 + 3· x 2 300, 1· x 1 + 1· x 2 150, 1· x 1 + 1· x 2 150, x 1, x 2 0. x 1, x 2 0. Запишем ЭММ задачи в каноническом виде: Запишем ЭММ задачи в каноническом виде: max f( x ) = 2· x 1 + 3· x 2 + 0· x 3 + 0· x 4, max f( x ) = 2· x 1 + 3· x 2 + 0· x 3 + 0· x 4, 1· x 1 + 3· x 2 + 1· x 3 + 0· x 4 = 300, 1· x 1 + 1· x 2 + 0· x 3 + 1· x 4 = 150, x 1, x 2, x 3, x 4 0. x 1, x 2, x 3, x 4 0. Исходный опорный план X = (x 1, x 2, x 3, x 4 ). = ( 0, 0, 300, 150 ). Исходный опорный план X = (x 1, x 2, x 3, x 4 ). = ( 0, 0, 300, 150 ). небазисные базисные Единичная подматрица Наличие единичной подматрицы обязательно для решения задачи симплексным методом ! 6

Дальнейшее решение ведем в симплекс-таблице Дальнейшее решение ведем в симплекс-таблице Готовим макет симплекс-таблицы Готовим макет симплекс-таблицы 7

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. отнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 8

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A max f(x) = 2·x 1 + 3·x 2 + 0·x 3 + 0·x 4, 1·x 1 + 3·x 2 + 1·x 3 + 0·x 4 = 300, 1·x 1 + 3·x 2 + 1·x 3 + 0·x 4 = 300, 1·x 1 + 1·x 2 + 0·x 3 + 1·x 4 = 150, 1·x 1 + 1·x 2 + 0·x 3 + 1·x 4 = 150, A 1 A 2 A 3 A 4 B A 1 A 2 A 3 A 4 B x 1, x 2, x 3, x 4 0. x 1, x 2, x 3, x 4 0. max f(x) = 2·x 1 + 3·x 2 + 0·x 3 + 0·x 4, 1·x 1 + 3·x 2 + 1·x 3 + 0·x 4 = 300, 1·x 1 + 3·x 2 + 1·x 3 + 0·x 4 = 300, 1·x 1 + 1·x 2 + 0·x 3 + 1·x 4 = 150, 1·x 1 + 1·x 2 + 0·x 3 + 1·x 4 = 150, A 1 A 2 A 3 A 4 B A 1 A 2 A 3 A 4 B x 1, x 2, x 3, x 4 0. x 1, x 2, x 3, x 4 0. Заполнение клеток начинаем с нулевой итерации. Для заполнения таблицы потребуется ЭММ в каноническом виде. Далее проверяем исходный план на оптимальность. 9

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A ij Для проверки данного плана на оптимальность оценки рассчитаем по формуле: План считается оптимальным, если среди оценок j нет отрицательных. j нет отрицательных. Симплекс-таблица

Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A Для оценки оптимальности плана рассчитываем оценки: Симплекс-таблица

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A Аналогично рассчитываем остальные оценки: Исходный план не оптимален, поскольку среди оценок Δ j имеются отрицательные. Исходный план не оптимален, поскольку среди оценок Δ j имеются отрицательные. Согласно признака оптимальности, на следующей итерации в базис войдет вектор A 2, имеющий минимальную отрицательную оценку, т.е. Δ 2 = -3. Вектор, входящий в базис обозначим A k. Δ 3 =0, Δ 4 =0 12

Симплекс-таблица Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A Для этого по формуле: Q i = b i /a ik рассчитываем оценочные отношения Q 3 = 300/3=100, Q 4 = 150/1=150. Далее определяем вектор A r, который выйдет из базиса. Из базиса выходит вектор, имеющий минимальное положительное оценочное отношение Q. В данном случае – это вектор A 3. Обозначим его A r. Из базиса выходит вектор, имеющий минимальное положительное оценочное отношение Q. В данном случае – это вектор A 3. Обозначим его A r. 13

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A A2A2A2A /3 11/30 A4A4A4A40502/30-1/31 Рассчитывается опорный план Рассчитываются a ij r-строка k-столбец a rk Заполняем симплекс-таблицу на новой итерации. 14

Симплекс-таблица Ите ра ция Базис Коэффи- циент ц. ф., с i Опорный план, b i Векторы коэффициентов Оценочн. oтнош., Q A1A1A1A1 A2A2A2A2 A3A3A3A3 A4A4A4A4 0 A3A3A3A A4A4A4A A2A2A2A /3 11/30300 A4A4A4A40502/30-1/ A2A2A2A /2-1/2 A1A1A1A /23/2 000,51,5 Среди оценок Δ j нет отрицательных. Поэтому план X=(75, 75, 0, 0) оптимален. 15

Подсчитаем максимальное значение целевой функции: max f(x) = 2·x 1 + 3·x 2 = 2·75 + 3·75 = 375 д.ед. Вывод. Предприятие получит максимальную прибыль в 375 д. ед., если будет производить по 75 единиц продукции первого и второго вида, все другие сочетания объемов выпуска продукции дадут меньшую прибыль. 16

Решение задачи о коврах симплексным методом. Базис Cj Ci План Q A1A2A3A4A5A6 A7 A A A A A A A A A

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 кг. ковров третьего вида. При этом ресурсы труд и оборудование будут использованы полностью, а из 480 кг пряжи (ресурс сырье) будет использовано 280 (200= ). Оптимальный план Х=(0, 30,10, 0). A A A

Технология решения оптимизационных задач с помощью надстройки Поиск решений в среде Excel Решение задач линейного программирования Поиск решения – это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения. После выбора команд Сервис Поиск решения появится диалоговое окно Поиск решения. 19

В Microsoft Office 2007 загрузка надстройки для Поиска решения выполняется следующим образом: - Выберите команду Надстройки, а затем в окне Управление выберите пункт Надстройки Excel. - Нажмите кнопку Перейти. - В окне Доступные надстройки установите флажок Поиск решения и нажмите кнопку ОК. Если Поиск решения отсутствует в списке поля Доступные надстройки, чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для Поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее. - Щелкните значок кнопка Microsoft Office, а затем щелкните Параметры Excel. 20

Оособые случаи при решении ЗЛП симплексным методом: Неединственность оптимального решения – присутствуют нулевые оценки Δ j для некоторой небазисной переменной. Неединственность оптимального решения – присутствуют нулевые оценки Δ j для некоторой небазисной переменной. Отсутствие оптимального решения – отсутствуют положительные элементы в k-столбце. Отсутствие оптимального решения – отсутствуют положительные элементы в k-столбце. Неразрешимость из-за противоречия ограничений – искусственные переменные не выводятся из базиса. Неразрешимость из-за противоречия ограничений – искусственные переменные не выводятся из базиса. 21