- § 3. Общая постановка задачи линейного программирования. Симплекс- метод
- 1. Множество решений системы (1) из § 2 является выпуклым многогранником (напомним, что выпуклое множество вместе с любыми двумя точками содержит все точки соединяющего их отрезка).
- 2. Вершины многогранника называются угловыми точками.
- Тема: Решение задач линейного программирования симплекс-методом
- 2.1 Алгоритм симплекс-метода
§ 3. Общая постановка задачи линейного программирования. Симплекс- метод
Как мы уже отмечали, графический метод, описанный в предыдущих примерах, приемлем в отношении задач с не более, чем двумя переменными. В большинстве же практических ситуаций число неизвестных может быть гораздо больше. Симплекс- метод- один из наиболее известных алгебраических подходов к решению задач линейного программирования с более, чем с двумя переменными. Отметим прежде всего
Основной принцип линейного программирования
1. Множество решений системы (1) из § 2 является выпуклым многогранником (напомним, что выпуклое множество вместе с любыми двумя точками содержит все точки соединяющего их отрезка).
2. Вершины многогранника называются угловыми точками.
3. Оптимальное решение (глобальный максимум) достигается хотя бы в одной угловой точке выпуклого многогранника, число которых конечно. Отсюда, принципиальный путь поиска оптимального решения: перебрать все угловые точки (их конечное число!) и среди них выбрать ту в которой целевая функция достигает максимума. Однако, как отмечается в [13] , технические сложности подобной процедуры настолько существенны, что за исключением простейших случаев, этот метод практически бесполезен.
Поэтому, необходимо научиться отбрасывать заведомо “плохие” угловые точки и работать только с перспективными, не прибегая к грaфикам.
Именно это и реализовал Данциг в разработанном им симплекс-методе. Суть метода – “направленный перебор”, когда вначале находят, какую нибудь угловую точку, а затем переходят к таким соседним угловым точкам, в которых значения целевой функции увеличиваются. Такой направленный перебор позволяет резко сократить число шагов (итераций).
Ясно, что для реализации симплекс- метода необходимо математически:
— выбрать начальное опорное решение (угловую точку)
— проверить его на оптимальность
— при необходимости перейти к лучшему
— уметь распознавать ситуации отсутствия оптимального решения.
Рассмотрим этапы “ручного” cимплекс — метода, когда необходимые преобразования осуществляются в таблицах стандартного вида.
Фирма намеревается приступить к изготовлению трех видов изделий, используя три вида ресурсов. Исходные данные приведены в таблице стандартного вида.
Расходные коэффициенты
Тема: Решение задач линейного программирования симплекс-методом
Симплексный метод решения задач линейного программирования основан на последовательном переходе от одного опорного плана (решения) ЗЛП к другому , при этом значения целевой функции изменяются.
2.1 Алгоритм симплекс-метода
Алгоритм симплексного метода состоит:
- Составление первого опорного плана.
а) Симплексная таблица начального опорного решения методом Гаусса при стремлении целевой функции к максимуму.
| Коэффициенты целевой функции | c1 | c2 | cn | 0 | 0 | 0 | 0 | ||||
| План | Базисные переменные | Значения базисных переменных | х1 | х2 | … | xn | xn+1 | xn+2 | …. | xn+m | zi |
| 1 | xn+1 xn+2…… xn+m | b1 b2….. bm | а11 а21….. аm1 | a12 a22….. am2 | а1n а2n….. аmn | 1 0 0 0 | 0 1 0 0 | 1 | 0 0 0 1 | ||
| Индексная строка | F(X) | 0 | — c1 | — c2 | — cn | 0 | 0 | 0 | 0 | ||
б) При стремлении целевой функции к минимуму опорное решение находится методом М- базиса.
| Коэффициенты целевой функции | C * 1 | C * 2 | C*n | 0 | 0 | 0 | 0 | |||||
| План | Базисные переменные | Значения базисных переменных | х1 | х2 | … | xn | y1 | y2 | …. | ym | zi | |
| 1 | y1 y2…… ym | b1 b2….. bm | а11 а21 аm1 | a12 a22 am2 | а1n а2n аmn | 1 0 0 | 0 1 0 | 0 0 1 | ||||
| Индексная строка | F(X) | M(b1+…+bm) | -C * 1 | -C * 2 | -C * n | 0 | 0 | 0 | 0 | |||
Для нахождения значенийC * i надо переменные уiвыразить через основные переменные (в уравнениях-ограничениях) и подставить в целевую функцию.
- Проверка плана (решения) на оптимальность.Если все коэффициенты последней строки симплексной таблицы (f) при решении на максимум неотрицательны, то план оптимален (решение оптимальное). Если хотя бы одно значение строкиfменьше нуля, то план не оптимален и его можно улучшить. (При решении ЗЛП на минимум целевой функции признаком оптимального плана являются отрицательные значения коэффициентов индексной строки) симплексной таблицы. Переходим к следующему этапу.
- Определение ведущих столбцов и строк. Из отрицательных значений последней строки выбираем наибольший по модулю, что и определяет ведущий столбец, который показывает, какая переменная на следующем приближении перейдет из свободных в базисные. Затем столбец свободных членов симплексной таблицы делим на элементы того же знака ведущего столбца. Делятся только элементы одинаковых знаков. Результаты заносим в отдельный столбецzi. Строка, соответствующая минимальнойziявляется ведущей. Она определяет переменную, которая в следующем плане выйдет из базиса и станет свободной. Элемент, находящийся на пересечении ведущей строки и ведущего столбца, называют разрешающим и выделяют.
- Построение нового опорного плана. Разделяем элементы ведущей строки предыдущей таблицы на разрешающий элемент и результаты деления заносим в строку следующей симплексной таблицы. Записываем значения, соответствующие введенной в базис переменной (на месте разрешающего элемента появится 1), а в остальные клетки ведущего столбца, включая и строкуf, записываем нули.
Остальные новые элементы нового плана находятся по правилу прямоугольника НЭ = СЭ — (А*В)/РЭ где НЭ — новый элемент, СЭ — старый элемент, РЭ — разрешающий элемент, А и В – элементы старого плана образующие прямоугольник с элементами СЭ и РЭ. Далее возвращаемся ко второму этапу — проверке на оптимальность. Пример (см. методы нахождения опорного решения) Коммерческое предприятие реализует три группы товаров (А,В,С). плановые нормативы затрат ресурсов на 1 т в рублях товарооборота, доход от продажи товаров на 1 т в рублях товарооборота , а так же объем ресурсов заданы. Определить плановый объем продаж и структуру товарооборота так, чтобы доход торгового предприятия был максимальным.
 Виды ресурсов | Нормы затрат на 1т в рублях товарооборота. | Объем ресурсов | ||
| А | В | С | ||
| Рабочее время продавцов Площадь торговых залов Площадь складских помещений Доход | 0,1 0,05 3 3 | 0,2 0,02 1 5 | 0,4 0,02 2 4 | 110 20 800 максимальный |
1) Запишем математическую модель: х1, х2,х3 — количество продаваемых товаров. Доход (целевая функция ) определяется: F(X)= max(3 х1+5 х2+4 х3) При условии: х1≥0; х2≥0; х3≥0; и ограничениях: 0
,1х1 + 0,2х2 + 0,4х3 ≤1100 0,05х1 + 0,02х2 +0,02х3≤120 3х1 + х2 + 2х3≤8000 2) Для построения первого опорного плана приведем запись ОЗЛП в канонической форме: F(X)= max(3 х1+5 х2+4 х3) При условии: х1≥0; х2≥0; х3≥0; и ограничениях: 0
,1х1 + 0,2х2 + 0,4х3 = 1100 0,05х1 + 0,02х2 +0,02х3 = 120 3х1 + х2 + 2х3 = 8000 3) Запишем математическую модель в векторном виде: F(X)=max(C*X), где С=(3 5 4 0 0 0 ) – вектор-строка из коэффициентов целевой функции. 
х1 х2 Х= х3 — вектор-столбец переменных х4 х5 х6 при условии, что вектор Х ≥0 
и ограничениях: А*Х=Р 0 , 
где матрица 
0,1 0,2 0,4 1 0 0 1100 А= 0,05 0,02 0,02 0 1 0 , Р 0 = 120 3 1 2 0 0 1 8000 4) Находим первый опорный план. Базисные переменные: х3; х4; х5. Свободные переменные: х1=0; х2=0; х3=0; В этом случае значения базисных переменных равны значениям свободных членов. 5) Построим таблицу:
| Коэффициенты целевой функции | 3 | 5 | 4 | 0 | 0 | 0 | |||
| План | Базисные переменные | Значения базисных переменных | х1 | х2 | х3 | х4 | х5 | х6 | zi |
| 1 | х4 x5 x6 | 1100 120 8000 | 0,1 0,05 3 | 0,20,021 | 0,4 0,02 2 | 1 0 0 | 0 1 0 | 0 0 1 | 5500 6000 8000 |
| Индексная строка | F(X) | 0 | — 3 | — 5 | -4 | 0 | 0 | 0 | |
Первый опорный план не оптимален, т.к. в индексной строке находятся отрицательные коэффициенты. Это значит, что необходимо построить новый план. 6) За ведущий столбец выбираем столбец с максимальным по модулю отрицательным элементом индексной строки (-5) (в таблице — выделен). Переменная х2переходит из свободных в базисные. 7) Для определения ведущей строки находим значения z. Значения базисных переменных делим на значения элементов ведущего столбца, учитывая знак. 8) Минимальное значение zопределяет ведущую строку. Базисная переменная х4переходит в свободные. Разрешающий элемент равен 0.2. 9) Формируем второй план таблицы. Новые значения ведущей строки равны значению старого элемента деленного на разрешающий элемент. Новые значения ведущего столбца равны нулю (включая и индексную строку), кроме элемента, находящегося на пересечении ведущего столбца и ведущей строки. (Он равен 1). Остальные элементы находятся по правилу прямоугольника: НЭ = СЭ — А*В/РЭ 
Например, для элемента на пересечении х5и х1НЭ= 0,05 -0.01*0.02/0,2 = 0,04 и т.д.
| План | Базисные переменные | Значения базисных переменных | х1 | х2 | х3 | х4 | х5 | х6 | zi |
| 2 | х2 х5 x6 | 5500 10 2500 | 0,5 0,04 2,5 | 1 0 0 | 2 -0,02 0 | 5 -0,1 -5 | 0 1 0 | 0 0 1 | 11000 250 1000 |
| Индексная строка | F(X) | 27500 | — 0,5 | 0 | 6 | 0 | 0 | 0 |
Этот план не оптимален. По вышеописанному алгоритму строим следующий план решения:
| План | Базисные переменные | Значения базисных переменных | х1 | х2 | х3 | х4 | х5 | х6 | zi |
| 2 | х2 х1 x6 | 5375 250 1875 | 0 1 0 | 1 0 0 | 2,25 -0,5 1,25 | 5 -0,1 -5 | 6,25 -2,5 1,25 | 0 0 1 | |
| Индексная строка | F(X) | 27625 | 0 | 0 | 5,75 | 23,75 | 12,5 | 0 |
При третьей итерации (приближении) получаем оптимальный план. Следовательно, фирма должна продавать 250 единиц товара А , 5375 единиц товара В , товар С не реализуется. При этом максимальный доход получается в размере 27625 рублей. В результате недоиспользованной оказывается площадь складских помещений на 1875 м 2 . Индексная строка свободных переменных 3-го плана (х3,х4,х5) имеет ненулевые элементы. Это говорит о том, что данный план линейной задачи является единственным.