Решения задачи планирования производства симплекс методом
![]()
![]()
![]()
![]()
Шаг 2. Вычисление
характеристических
разностей
(оценок) по формулам
и запись оценок
в
-ю
строку симплекс-таблицы.
Шаг 3. Вычисление
оценки
,
удовлетворяющей
условию:
Если все
,
то в соответствии
с выполнением
критерия
оптимальности
вектор
—
оптимальное
решение, и далее
следует перейти
к шагу 9, иначе
— к шагу 4.
Шаг 4. Вычисление
нового базисного
решения
из условия:
![]()
Шаг 5. Вычисление
компонент
нового базисного
решения
по формулам:
![]()
Шаг 6. Вычисление
элементов новой
симплекс-таблицы
для
-й
итерации метода
по формулам:

Шаг 7. Корректировка симплекс-таблицы с учетом изменений коэффициентов целевой функции, соответствующих новому базисному решению. Формируем таблицу (**).
Таблица (**)
| #№ | Базисные столбцы |
|
Базисное
решение Xs |
C1 | C2 | … | Cm | m+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 |
|
… |
|
… |
|
| Оценки |
|
|
… |
|
|
… |
|
… |
|
![]()
![]()
![]()
![]()
Шаг
8. Переход к шагу
2.
Шаг 9. Остановка, регистрация оптимального решения.
Таким образом, сформулированный алгоритм определяет конечную последовательность шагов, необходимых для вычисления оптимального решения.
2.4 Решение задач оптимизации при помощи средства «Поиск решения» в Microsoft Excel
Мощным средством анализа данных MS Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
2.4.1 Описание
Программа «Поиск решений» (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:
количество неизвестных (decision variable) – 200;
количество формульных ограничений (explicit constraint) на неизвестные – 100;
количество предельных условий (simple constraint) на неизвестные – 400.
Разработчик программы Solver, компания Frontline System, уже давно специализируется на разработке мощных и удобных способов оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe Quattro Pro, Lotus 1-2-3).
Высокая эффективность их применения объясняется интеграцией программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel встроенная в его среду программа Solver является наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса.
Средство поиска решения Microsoft Excel использует алгоритм нелинейной оптимизации Generalized Reduced Gradient (GRG2), разработанный Леоном Ласдоном (Leon Lasdon, University of Texas at Austin) и Аланом Уореном (Allan Waren, Cleveland State University), алгоритмы симплексного метода и метода «branch-and-bound» для решения линейных и целочисленных задач с ограничениями разработаны Джоном Уотсоном (John Watson) и Деном Филстра (Dan Fylstra) из Frontline Systems, Inc.
2.4.2 Процедура поиска решения
В меню «Сервис» в разделе «Надстройки» необходимо активизировать функцию «Поиск решения».
Создайте таблицу с формулами, которые устанавливают связи между ячейками. (см. Рис.1)
Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду «Поиск решения». Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.
Установите переключатели Equal To (Равной), задающие значение целевой ячейки, — Мах (максимальному значению), Min (минимальному значению) или Value of (значению). В последнем случае введите значение в поле справа.
Укажите в поле By Changing Cells (Изменяя ячейки), в каких ячейках программа должна изменять значения в поисках оптимального результата.
Создайте ограничения в списке Subject to the Constraints (Ограничения). Для этого щелкните на кнопке Add (Добавить) и в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.

Рис.2 Диалоговое окно надстройки «Поиск решения»
Щелкните на кнопке на кнопке Options (Параметры), и в появившемся окне установите переключатель Неотрицательные значения (если переменные должны быть позитивными числами), Линейная модель (если задача, которую вы решаете, относится к линейным моделям).

Рис.3 Окно параметров надстройки «Поиск решения»
Щелкнув на кнопке Solver (Выполнить), запустите процесс поиска решения.

Рис.4 Результаты поиска решения
2.4.3 Параметры средства «Поиск решения»
Максимальное время - служит для ограничения времени, отпущенного на поиск решения задачи. В этом поле можно ввести время в секундах, не превышающее 32 767 (примерно девять часов); значение 100, используемое по умолчанию, вполне приемлемо для решения большинства простых задач.
Предельное число итераций - управляет временем решения задачи путем ограничения числа вычислительных циклов (итераций).
Относительная погрешность - определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.
Допустимое отклонение - предназначен для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел. Чем больше значение допуска, тем меньше времени требуется на поиск решения.
Сходимость - применяется только к нелинейным задачам. Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается.
Линейная модель - служит для ускорения поиска решения путем применения к задаче оптимизации линейной модели. Нелинейные модели предполагают использование нелинейных функций, фактора роста и экспоненциального сглаживания, что замедляет вычисления.
Неотрицательные значения - позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых не было задано соответствующее ограничение в диалоговом окне Добавить ограничение.
Автоматическое масштабирование - используется, когда числа в изменяемых ячейках и в целевой ячейке существенно различаются.
Показывать результаты итераций - приостанавливает поиск решения для просмотра результатов отдельных итераций.
Загрузить модель - после щелчка на этой кнопке отрывается одноименное диалоговое окно, в котором можно ввести ссылку на диапазон ячеек, содержащих модель оптимизации.
Сохранить модель - служит для отображения на экране одноименного диалогового окна, в котором можно ввести ссылку на диапазон ячеек, предназначенный для хранения модели оптимизации.
Оценка линейная - выберите этот переключатель для работы с линейной моделью.
Оценка квадратичная - выберите этот переключатель для работы с нелинейной моделью.
Разности прямые - используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства Поиск решения.
Разности центральные - используется для функций, имеющих разрывную производную. Данный способ требует больше вычислений, однако его применение может быть оправданным, если выдано сообщение о том, что получить более точное решение не удается.
Метод поиска Ньютона - требует больше памяти, но выполняет меньше итераций, чем в методе сопряженных градиентов.
Метод поиска сопряженных градиентов - реализует метод сопряженных градиентов, для которого требуется меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует использовать, если задача достаточно большая и необходимо экономить память или если итерации дают слишком малое отличие в последовательных приближениях.
В результате исследования основных алгоритмов решения задач ЛП, было принято решение поставленную задачу планирования производства решать симплекс методом. Это обусловлено тем, что симплекс метод является эффективным алгоритмом и наиболее универсальным методом, которым можно решить любую задачу линейного программирования. В качестве вспомогательного средства, для составления конкретной задачи планирования производства (подбора таких значений, чтобы задача имела решение) было использовано средство «Поиск решения» в MS Excel.
3. Задача планирования производства
Задача планирования производства относится к категории экономических проектов, к которым предъявлены определенные требования. Проект - это ограниченное по времени целенаправленное изменение отдельной системы с установленными требованиями к качеству результатов, возможными рамками расхода средств и ресурсов и специфической организацией.
3.1 Постановка задачи планирования производства в общем случае
Некоторое
предприятие
производит
n типов продукции,
затрачивая
при этом m типов
ресурсов. Известны
следующие
параметры: aij
– количество
i-го ресурса,
необходимое
для производства
единичного
количества
j-й продукции;
aij
0
(i=1,…,m; j=1,…,n);
bi-запас i-го ресурса на предприятии, bi>0;
cj-цена единичного количества j-й продукции, cj>0.
Предполагается, что затраты ресурсов растут прямо пропорционально объему производства. Пусть xj – планируемый объем производства j-й продукции. Тогда допустимым является только такой набор производимой продукции x=(x1,x2,…,xn), при котором суммарные затраты каждого вида i-го ресурса не превосходят его запаса:
(1)
Кроме того,
имеем следующее
ограничение:
xj
0;
j=1,…,n. (2)
Стоимость
набора продукции
x выражается
величиной:
(3)
Задача планирования производства ставится следующим образом: среди всех векторов x, удовлетворяющим ограничениям (1), (2), найти такой, при котором величина (3) принимает наибольшее значение.
3.2 Математическое описание поставленной задачи планирования симплекс методом
Пусть некоторое предприятие производит 5 видов продукции A, B, C, D и E, затрачивая при этом 5 типов ресурсов. На производство продукции типа A требуется следующее количество имеющихся на предприятии ресурсов (дается количество каждого ресурса, необходимого для производства единицы продукции типа A): 1 – количество ресурса 1, 4 – количество ресурса 2, 2 – количество ресурса 3, 1 – количество ресурса 4, 3 – количество ресурса 5. На производство единицы продукции типа B требуется (в условных единицах): 2 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа C требуется (в условных единицах): 4 – количество ресурса 1, 1 – количество ресурса 2, 3 – количество ресурса 3, 1 – количество ресурса 4, 2 – количество ресурса 5. На производство единицы продукции типа D требуется (в условных единицах): 3 – количество ресурса 1, 2 – количество ресурса 2, 4 – количество ресурса 3, 2 – количество ресурса 4, 1 – количество ресурса 5. На производство единицы продукции типа E требуется (в условных единицах): 1 – количество ресурса 1, 2 – количество ресурса 2, 1 – количество ресурса 3, 4 – количество ресурса 4, 4 – количество ресурса 5.
Допустим, что запас ресурса 1 на предприятии составляет 600 условных единиц, запас ресурса 2 – 590 условных единиц, запас ресурса 3 – 750 условных единиц, запас ресурса 4 – 670 условных единиц и запас ресурса 5 – 495 условных единиц.
Цена единицы продукции типа A равна 60 рублям, цена единицы продукции типа B равна 50 рублям, цена единицы продукции типа C равна 37 рублям, цена единицы продукции типа D равна 45 рублям, а единица продукции типа E – 56 рублям.
Нужно спланировать такой набор производимой продукции x=(x1, x2, x3, x4, x5), при котором суммарные затраты каждого вида ресурса не превосходят его запаса, т.е.
x1+4x2+2x3+1x4+3x5
600;
2x1+2x2+x3+4x4+2x5
590;
4x1+x2+3x3+x4+2x5
750;
3x1+2x2+4x3+2x4+x5
670;
x1+2x2+x3+4x4+4x5
495;
и при этом
должны выполняться
следующие
ограничения:
x1, x2, x3, x4, x5
0. Спланированный
набор производимой
продукции
x=(x1, x2, x3, x4, x5) должен
обеспечить
максимум стоимости
данного набора
{60x1+50x2+37x3+45x4+56x5}
max.
Таким образом, мы получим однокритериальную задачу, которая является задачей линейного программирования (ЗЛП). Она сводится к поиску экстремума линейной функции (данная функция называется либо критерием, либо целевой функцией)
f(x)=60x1+50x2+37x3+45x4+56x5
при наличии системы линейных неравенств, ограничивающих область изменения аргументов этой функции
x1+4x2+2x3+1x4+3x5
600;
2x1+2x2+x3+4x4+2x5
590;
4x1+x2+3x3+x4+2x5
750;
3x1+2x2+4x3+2x4+x5
670;
x1+2x2+x3+4x4+4x5
495;
x1, x2, x3, x4, x5
0.
3.3 Решение поставленной задачи планирования производства
Описание метода решения задачи.
Процедура
решения ЗЛП
начинается
с приведения
ее к канонической
форме, то есть
к стандартной
форме задания,
ориентированной
на разработанный
именно для этой
формы метод
решения. Задача
линейного
программирования
в канонической
форме имеет
смысл при условии
n>m. В этом случае
полностью
описывается
область допустимых
решений (ОДР)
ЗЛП, геометрически
являющуюся
выпуклым
многогранником
в евклидовом
пространстве
Rn[1]. Выпуклая
фигура, как
известно,
характеризуется
тем свойством,
что, если две
точки X1 и X2 принадлежат
этой фигуре,
то и весь отрезок
X1X2 принадлежит
ей. Кроме того,
доказано, что
оптимальное
решение ЗЛП
всегда лежит
на границе ОДР.
Поэтому справедлив
вывод о том,
что, по крайней
мере, одна из
угловых (опорных)
точек выпуклого
многогранника
ОДР является
точкой оптимума.
Для того, чтобы
определить
координаты
опорной точки,
все множество
переменных
X={xj}, j=
необходимо
разделить на
два подмножества
:
подмножество
базисных переменных
,
при этом число
m базисных переменных
равно числу
уравнений
(ограничивается)
при условии,
что уравнения
являются
линейно-независимыми;
подмножество
остальных n-m
свободных
(внебазисных)
переменных
{xj}, j
Б[1].
Количество
возможных
вариантов
разделения
переменных
на базисные
и свободные
(число базисов)
равно
.
Наиболее
очевидный метод
решения ЗЛП
состоит в том,
чтобы для каждого
из
базисов найти
координаты
соответствующих
опорных точек,
выделить из
них точки,
принадлежащие
ОДР, а затем из
них, в свою очередь,
выбрать ту,
координаты
которой максимизируют
целевую функцию.
В отличие от
этого метода,
реализующего,
по сути, идею
полного перебора
опорных точек
ОДР, известен
более эффективный
так называемый
симплекс-метод
решения ЗЛП.
В основе симплекс-метода лежит подход, включающий:
выбор опорной точки, принадлежащей ОДР (выбор начального допустимого базиса);
проверку опорной точки на оптимальность;
выбор нового базиса, позволяющего минимизировать число опорных точек на траектории в случае невыполнения условий оптимальности.
Приведение исходной задачи к каноническому виду.
Имеем исходную ЗЛП:
{60x1+50x2+37x3+45x4+56x5}
max.
x1+4x2+2x3+x4+3x5
600;
2x1+2x2+x3+4x4+2x5
590;
4x1+x2+3x3+x4+2x5
750;(4)
3x1+2x2+4x3+2x4+x5
670;
x1+2x2+x3+4x4+4x5
495;
x1, x2, x3, x4, x5
0.
Приведем ЗЛП к канонической форме. Приведение системы ограничений, заданных в форме неравенств, к канонической форме равенств осуществляется посредством соответствующего увеличения размерности вектора X=(x1, x2, x3, x4, x5) с учетом обязательной неотрицательности всех его составляющих.
Таким образом, ЗЛП в канонической форме имеет вид:
max {60x1+50x2+37x3+45x4+56x5};
(5)
Поиск допустимого базиса.
Заполнение симплекс-таблицы.
ЗЛП в канонической форме можно записать в матричном виде:
(6)
b=(600, 590, 750, 670, 495)T,
X=(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10)T,
C=(60,50,37,45,56,0,0,0,0,0),
A=
.
Поиск допустимого базиса начинается с анализа столбцов матрицы A=(A1, A2,…, A10), используемой в записи ограничения (6) канонической формы ЗЛП. В качестве базисных следует выбирать такие 5 переменных, которым соответствует набор столбцов, позволяющих составить единичную матрицу P=(Aj1, Aj2, Aj3, Aj4, Aj5).
Если ОДР
исходной ЗЛП
задана в форме
неравенств
типа
(как в нашем
случае), то начальный
базис может
быть сформирован
из дополнительных
переменных
x6, x7, x8, x9, x10, вводимых
в систему ограничений
с целью приведения
ее к канонической
форме равенств.
В этом случае
матрица P будет
единичной.
Таким образом, выберем в качестве начального базиса XБО=(x6, x7, x8, x9, x10)T, так как столбцы A6, A7, A8, A9, A10 матрицы A образуют единичную матрицу.
Теперь перейдем к заполнению симплекс-таблицы. Пусть ЗЛП сформулирована в канонической форме (5). Мы выбрали базисные переменные x6, x7, x8, x9, x10. Разрешим систему неравенств в (5) относительно базисных переменных.
Система ограничений в форме Такера примет вид:
x6=600-(x1+4x2+2x3+x4+3x5);
x7=590-(2x1+2x2+x3+4x4+2x5);
x8=750-(4x1+x2+3x3+x4+2x5);(7)
x9=670-(3x1+2x2+4x3+2x4+x5);
x10=495-(x1+2x2+x3+4x4+4x5);
Целевую функцию можно представить в виде:
f(x)=f0-(-60x1-50x2-37x3-45x4-56x5), где f0=0.
Симплекс-таблица выглядит следующим образом:
Таблица 1. Исходная симплекс таблица в общем виде
| b | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | |
| x6 | b6 | a61 | a62 | a63 | a64 | a65 | a66 | a67 | a68 | a69 | a610 |
| x7 | b7 | a71 | a71 | a71 | a71 | a71 | a71 | a71 | a71 | a71 | a710 |
| x8 | b8 | a81 | a82 | a83 | a84 | a85 | a86 | a87 | a88 | a89 | a810 |
| x9 | b9 | a91 | a92 | a93 | a94 | a95 | a96 | a97 | a98 | a99 | a910 |
| x10 | b10 | a101 | a102 | a103 | a104 | a105 | a106 | a107 | a108 | a109 | a1010 |
| f(x) | f0 | c1 | c2 | c3 | c4 | c5 | c6 | c7 | c8 | c9 | c10 |
В нашем случае:
Таблица 2. Исходная симплекс таблица поставленной задачи
-
БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X6 600 1 4 2 1 3 1 0 0 0 0 X7 590 2 2 1 4 2 0 1 0 0 0 X8 750 4 1 3 1 2 0 0 1 0 0 X9 670 3 2 4 2 1 0 0 0 1 0 X10 495 1 2 1 4 4 0 0 0 0 1 Y 0 -60 -50 -37 -45 -56 0 0 0 0 0
Составленная симплекс-таблица соответствует начальному базису и начальной опорной точке ОДР. Переход к очередной опорной точке в процессе поиска оптимального решения сопровождается составлением новой симплекс-таблицы.
Каждая симплекс-таблица анализируется по критериям допустимости и оптимальности базиса.
3.3.4 Проверка признака допустимости и оптимальности базиса
Признак допустимости базиса:
в опорной
точке в соответствии
с (7) xj=bi, i=6,…,10; j=6,…,10, поэтому
признак допустимости
базиса формулируется
как условие
bi
0,
i=6,…,10.
Признак оптимальности базиса:
Если для
то найденное
решение оптимально
и единственно.
Если для
то найденное
решение оптимально,
но не единственно.
Если
то решение
неоптимально.
В этом случае
поиск оптимального
решения продолжается
и необходимо
перейти к новой
опорной точке.
Перейдем к конкретному случаю. В нашем случае выполняется условие допустимости базиса, так как b=(600, 590, 750, 670, 495)T<0 и bi<0 (i=6,…,10).
Выбранный нами начальный базис XБО=(x6, x7, x8, x9, x10)T не является оптимальным, так как c1=-60<0, c2=-50<0, c3=-37<0, c4=-45<0 и c6=56<0. Таким образом, необходимо осуществить переход к новой опорной точке (новому базису).
3.3.5 Нахождение разрешающего элемента в симплекс-таблице. Формирование нового базиса
В соответствии с симплекс-методом новая опорная точка выбирается только среди соседних, то есть новый базис лишь одной переменной отличается от прежнего. Таким образом, формирование нового базиса осуществляется на базе прежнего посредством выведения из него одной из базисных переменных xs и введения одной из свободных переменных xr.
Выбор переменной
xr. Выбор переменной
xr осуществляется
по результатам
анализа коэффициентов
cj симплекс-таблицы.
Найдем cr=
.
В нашем случае min{c1, c2, c3, c4, c5}=c1=-60 и xr=x1.
Столбец, который соответствует переменной xr=x1 в симплекс-таблице, будем называть разрешающим.
Выбор переменной xs. Выбор переменной xs проводится по результатам анализа коэффициентов air i=1,2,3,4,5 разрешающего столбца.
Если
,
это означает,
что ОДР такова,
что неограниченное
увеличение
свободной
переменной
xr приводит к
неограниченному
возрастанию
целевой функции
(ОДР не замкнута).
Если
,
то соответствующие
базисные переменные
xi (i=6,7,8,9,10) получают
отрицательные
приращения
при увеличении
xr=x1. Среди этих
переменных
xi необходимо
отыскать xs,
достигающую
нуля при минимальном
значении приращения
xr. Нужно найти
.
В нашем случае min{600/1, 590/2, 750/4,