Краткая теория
Для решения задач линейного программирования предложено немало различных методов. Однако наиболее эффективным и универсальным среди них оказался симплекс-метод. При этом следует отметить, что при решении некоторых задач могут оказаться более эффективными другие методы. Например, при ЗЛП с двумя переменными оптимальным является , а при решении - метод потенциалов. Симплекс-метод является основным и применимым к любой ЗПЛ в канонической форме.
В связи с основной теоремой линейного программирования естественно возникает мысль о следующем пути решения ЗЛП с любым числом переменных. Найти каким-нибудь способом все крайние точки многогранника планов (их не больше, чем ) и сравнить в них значения целевой функции. Такой путь решения даже с относительно небольшим числом переменных и ограничений практически неосуществим, так как процесс отыскания крайних точек сравним по трудности с решением исходной задачи, к тому же число крайних точек многогранника планов может оказаться весьма большим. В связи с этими трудностями возникла задача рационального перебора крайних точек.
Суть симплексного метода в следующем. Если известны какая-нибудь крайняя точка и значение в ней целевой функции, то все крайние точки, в которых целевая функция принимает худшее значение, заведомо не нужны. Отсюда естественно стремление найти способ перехода от данной крайней точки к смежной по ребру лучшей, от нее к еще лучшей (не худшей) и т. д. Для этого нужно иметь признак того, что лучших крайних точек, чем данная крайняя точка, вообще нет. В этом и состоит общая идея наиболее широко применяемого в настоящее время симплексного метода (метода последовательного улучшения плана) для решения ЗЛП. Итак, в алгебраических терминах симплексный метод предполагает:
Пример решения задачи
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве , , , единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве единиц, ресурса второго вида в количестве единиц, ресурса третьего вида в количестве единиц. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве , единиц, ресурсов второго вида в количестве , единиц, ресурсов третьего вида в количестве , единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно , , тыс. руб.
Если ваш допуск к сессии зависит от решения блока задач, а у вас нет ни времени, ни желания садиться за расчёты – используйте возможности сайта сайт. Заказ задач – дело нескольких минут. Подробно (как оставить заявку, цены, сроки, способы оплаты) можно почитать на странице Купить решение задач по линейному программированию...
Через обозначим товарооборот 1-го, 2-го и третьего вида товаров соответственно.
Тогда целевая функция, выражающая получаемую прибыль:
Ограничения по материально-денежным ресурсам:
Кроме того, по смыслу задачи
Получаем следующую задачу линейного программирования:
Приведем задачу к каноническому виду. Для преобразования неравенств в равенства введем дополнительные переменные . Переменные входят в ограничения с коэффициентом 1. В целевую функцию все дополнительные переменные введем с коэффициентом, равным нулю.
Ограничение имеет предпочтительный вид, если при неотрицательности правой части левая часть имеет переменную, входящую с коэффициентом, равным единице, а остальные ограничения-равенства - с коэффициентом, равным нулю. В нашем случае 1-е, 2-е, 3-е ограничения имеют предпочтительный вид с соответствующими базисными переменными .
Заполняем симплексную таблицу 0-й итерации.
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 520 | 16 | 18 | 9 | 1 | 0 | 0 | 65/2 | 0 | 140 | 7 | 7 | 2 | 0 | 1 | 0 | 20 | 0 | 810 | 9 | 2 | 1 | 0 | 0 | 1 | 90 | 0 | -8 | -6 | -4 | 0 | 0 | 0 |
Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.
Переход к следующей итерации осуществляем следующим образом:
Ведущий столбец соответствует .
Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е.7.
Теперь приступаем к составлению 1-й итерации. Вместо единичного вектора вводим вектор .
В новой таблице на месте разрешающего элемента пишем 1, все остальные элементы ключевого столбца –нули. Элементы ключевой строки делятся на разрешающий элемент. Все остальные элементы таблицы вычисляются по правилу прямоугольника.
Получаем таблицу 1-й итерации:
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 0 | 200 | 0 | 2 | 31/7 | 1 | -16/7 | 0 | 1400/31 | 8 | 20 | 1 | 1 | 2/7 | 0 | 1/7 | 0 | 70 | 0 | 630 | 0 | -7 | -11/7 | 0 | -9/7 | 1 | - | 160 | 0 | 2 | -12/7 | 0 | 8/7 | 0 |
Ключевой столбец для 1-й итерации соответствует .
Находим ключевую строку, для этого определяем:
На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 31/7.
Вектор выводим из базиса и вводим вектор .
Получаем таблицу 2-й итерации:
| БП |
Симплексные отношения |
8 | 6 | 4 | 0 | 0 | 0 | 4 | 1400/31 | 0 | 14/31 | 1 | 7/31 | -16/31 | 0 | 8 | 220/31 | 1 | 27/31 | 0 | -2/31 | 9/31 | 0 | 0 | 21730/31 | 0 | -195/31 | 0 | 11/31 | -65/31 | 1 | 7360/31 | 0 | 86/31 | 0 | 12/31 | 8/31 | 0 |
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
Таким образом, необходимо продавать 7,1 тыс.р. товара 1-го вида и 45,2 тыс.р. товара 3-го вида. Товар 2-го вида продавать невыгодно. При этом прибыль будет максимальна и составит 237,4 тыс.р. При реализации оптимального плана остаток ресурса 3-го вида составит 701 ед.
Запишем модель двойственной задачи.
Для построения двойственной задачи необходимо пользоваться следующими правилами:
1) если прямая задача решается на максимум, то двойственная - на минимум, и наоборот;
2) в задаче на максимум ограничения-неравенства имеют смысл ≤, а в задаче минимизации - смысл ≥;
3) каждому ограничению прямой задачи соответствует переменная двойственной задачи, и наоборот, каждому ограничению двойственной задачи соответствует переменная прямой задачи;
4) матрица системы ограничений двойственной задачи получается из матрицы системы ограничений исходной задачи транспонированием;
5) свободные члены системы ограничений прямой задачи являются коэффициентами при соответствующих переменных целевой функции двойственной задачи, и наоборот;
6) если на переменную прямой задачи наложено условие неотрицательности, то соответствующее ограничение двойственной задачи записывается как ограничение-неравенство, если же нет, то как ограничение-равенство;
7) если какое-либо ограничение прямой задачи записано как равенство, то на соответствующую переменную двойственной задачи условие неотрицательности не налагается.
Транспонируем матрицу исходной задачи:
Приведем задачу к каноническому виду. Введем дополнительные переменные. В целевую функцию все дополнительные переменные введем с коэффициентом, равным нулю. Дополнительные переменные прибавим к левым частям ограничений, не имеющих предпочтительного вида, и получим равенства.
Соответствие между переменными исходной и двойственной задачи:
На основании симплексной таблицы получено следующее решение двойственной задачи линейного программирования (выписываем из нижней строки):
Таким образом, наиболее дефицитным
является ресурс первого вида. Его оценка максимальна и равна
. Ресурс третьего вида является избыточным -его
двойственная оценка равна нулю
. Каждая дополнительно проданная единица товара 2-й
группы будет снижать оптимальную прибыль на
Рассмотрен графический метод решения задачи линейного программирования (ЗЛП) с двумя переменными. На примере задачи приведено подробное описание построения чертежа и нахождения решения.
Решение транспортной задачи
Подробно рассмотрена транспортная задача, ее математическая модель и методы решения - нахождение опорного плана методом минимального элемента и поиск оптимального решения методом потенциалов.
Принятие решений в условиях неопределенности
Рассмотрено решение статистической матричной игры в условиях неопределенности с помощью критериев Вальда, Сэвиджа, Гурвица, Лапласа, Байеса. На примере задачи подробно показано построение платежной матрицы и матрицы рисков.
Рассмотрен пример решения задачи симплекс методом, а также пример решения двойственной задачи.
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс. руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
К прямой задаче планирования товарооборота, решаемой симплекс методом
, составить двойственную задачу
линейного программирования.
Установить сопряженные пары переменных
прямой и двойственной задачи.
Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи
, в которой производится оценка ресурсов
, затраченных на продажу товаров.
F = 4·x 1 + 5·x 2 + 4·x 3 ->max
0}}}{~}" title="delim{lbrace}{matrix{4}{1}{{2x_1 + 3x_2 + 6x_3= 0}}}{~}">
Решаем симплекс методом.
Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.
В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.
Данные заносим в симплекс таблицу
Целевая функция:
0 · 240 + 0 · 200 + 0 · 160 = 0
Вычисляем оценки по формуле:
Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Вводим переменную x 2 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .
= 26.667
Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса
3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2
Вычисляем:
Получаем новую таблицу:
Целевая функция:
0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3
Вычисляем оценки по формуле:
Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6
Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.
Вводим переменную x 1 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .
Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса
3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3
Вычисляем:
Получаем новую таблицу:
Целевая функция:
0 · 160 + 0 · 40 + 4 · 40 = 160
Вычисляем оценки по формуле:
Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи:
То есть необходимо реализовать товар первого вида в объеме 40 тыс. руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.
Двойственная задача имеет вид:
Z = 240·y 1 + 200·y 2 + 160·y 3 ->min
Title="delim{lbrace}{matrix{4}{1}{{2y_1 + 4y_2 + 4y_3>=4} {3y_1 + 2y_2 + 6y_3>=5} {6y_1 + 4y_2 + 8y_3>=4} {y_1, y_2, y_3>= 0}}}{~}">
Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.
Сопряженные пары переменных прямой и двойственной задач имеют вид:
Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
Решение:
I итерация:
х3 , х4 , х5 , х6 х1 ,х2 . Выразим базисные переменные через свободные:
Приведем целевую функциюк следующему виду:
На основе полученной задачи сформируем исходную симплекс-таблицу:
Таблица 5.3
Исходная симплекс-таблица
Оценочные отношения |
||||
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
6 этап: проверка оптимальности.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
Так как найденное базисное решение допустимое, то поиск разрешающей колонки будем производить по следующей схеме: определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.3, таких колонок две: колонка «х1 » и колонка «х2 ». Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х2 » содержит наименьший элемент (–3) в сравнении с колонкой «х1
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
Таблица 5.4
Исходная симплекс-таблица
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5 », следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5 » и колонки «х2 ».
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х5 и х2 , в новой симплекс-таблице (таблице 5.5) их меняем местами.
9.1. Преобразование разрешающего элемента.
Разрешающий элемент таблицы 5.4 преобразовывается следующим образом:
Полученный результат вписываем в аналогичную клетку таблицы 5.5.
9.2. Преобразование разрешающей строки.
Элементы разрешающей строки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей строки приведены в таблице 5.5.
9.3. Преобразование разрешающей колонки.
Элементы разрешающей колонки таблицы 5.4 делим на разрешающий элемент данной симплекс-таблицы, а результат берется с обратным знаком. Полученные результаты вписываются в аналогичные ячейки новой симплекс-таблицы (таблицы 5.5). Преобразования элементов разрешающей колонки приведены в таблице 5.5.
9.4. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
К примеру, рассмотрим преобразование элемента, расположенного на пересечении строки «х3 » и колонки «», условно обозначим его «х3 ». В таблице 5.4 мысленно вычерчиваем прямоугольник, одна вершина которого располагается в клетке, значение которой преобразуем (т.е. в клетке «х3 »), а другая (диагональная вершина) – в клетке с разрешающим элементом. Две другие вершины (второй диагонали) определяются однозначно. Тогда преобразованное значение клетки «х3 » будет равно прежнему значению данной клетки минус дробь, в знаменателе которой разрешающий элемент (из таблицы 5.4), а в числителе произведение двух других неиспользованных вершин, т.е.:
«х3 »: .
Аналогично преобразуются значения других клеток:
«х3 х1 »: ;
«х4
»: 
;
«х4 х1 »: ;
«х6
»: 
;
«х6 х1 »: ;
«»: 
;
«х1
»: 
.
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
II итерация:
1 этап: составление симплекс-таблицы.
Таблица 5.5
Симплекс-таблица II итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.5):
Как видно, при данном базисном решении значение целевой функции =15, что больше чем при предыдущем базисном решении.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.5) содержится отрицательный элемент: –2 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.5, такой колонкой является только одна колонка: «х1 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.6, минимальным является отношение, соответствующее строке «х3 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.6
Симплекс-таблица II итерации
Оценочные отношения |
||||
3/1=3 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.6) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.7.
III итерация
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.7
Симплекс-таблица III итерации
Оценочные отношения |
||||
| ||||
|
|
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение (таблица 5.7):
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.7 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.7 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 не оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.7) содержится отрицательный элемент: –3 (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, переходим к 8 этапу.
8 этап: определение разрешающего элемента.
8.1. Определение разрешающей колонки.
Найденное базисное решение допустимое, определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Согласно таблице 5.7, такой колонкой является только одна колонка: «х5 ». Следовательно, ее принимаем в качестве разрешенной.
8.2. Определение разрешающей строки.
Согласно полученным значениям положительных оценочных отношений в таблице 5.8, минимальным является отношение, соответствующее строке «х4 ». Следовательно, ее принимаем в качестве разрешенной.
Таблица 5.8
Симплекс-таблица III итерации
Оценочные отношения |
||||
5/5=1 – min |
||||
9 этап: преобразование симплекс-таблицы.
Преобразования симплекс-таблицы (таблицы 5.8) выполняются аналогично, как и в предыдущей итерации. Результаты преобразований элементов симплекс-таблицы приведены в таблице 5.9.
IV итерация
1 этап: построение новой симплекс-таблицы.
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Таблица 5.9
Симплекс-таблица IV итерации
Оценочные отношения |
||||
| –(–3/5)=3/5 | |||
–(1/5)=–1/5 | ||||
| –(9/5)=–9/5 | |||
|
| –(–3/5)=3/5 |
2 этап: определение базисного решения.
В результате проведенных симплекс-преобразований получили новое базисное решение, согласно таблице 5.9 решение следующее:
3 этап: проверка совместности системы ограничений.
Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.9 не выявлена.
4 этап: проверка ограниченности целевой функции.
Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.9 не выявлена.
5 этап: проверка допустимости найденного базисного решения.
Найденное базисное решение в соответствии с признаком 3 допустимое, так как не содержит отрицательных компонент.
6 этап: проверка оптимальности найденного базисного решения.
Найденное базисное решение в соответствии с признаком 4 оптимальное, так как в строке целевой функции симплекс-таблицы (таблица 5.9) нет отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
7 этап: проверка альтернативности решения.
Найденное решение является единственным, так как в строке целевой функции (таблица 5.9) нет нулевых элементов (свободное число данной строки при рассмотрении данного признака не учитывается).
Ответ: оптимальное значение целевой функции рассматриваемой задачи =24, которое достигается при.
Пример 5.2. Решить вышеприведенную задачу линейного программирования при условии, что целевая функция минимизируется:
Решение:
I итерация:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3 , х4 , х5 , х6 , тогда свободными переменными будут х1 ,х2 . Выразим базисные переменные через свободные.
Данный метод является методом целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет за конечное число шагов либо найти оптимальное решение, либо установить, что оптимальное решение отсутствует.
Основное содержание симплексного метода заключается в следующем:Решить симплексным методом задачу:
Решение:
Приводим задачу к каноническому виду.
Для этого в левую часть первого ограничения-неравенства вводим дополнительную переменную x 6 с коэффициентом +1. В целевую функцию переменная x 6 входит с коэффицентом ноль (т.е. не входит).
Получаем:
Находим начальное опорное решение. Для этого свободные (неразрешенные) переменные приравниваем к нулю х1 = х2 = х3 = 0.
Получаем опорное решение Х1 = (0,0,0,24,30,6) с единичным базисом Б1 = (А4, А5, А6).
Вычисляем оценки разложений векторов условий по базису опорного решения по формуле:
Δ k = C б X k — c k
Оценки векторов входящих в базис всегда равны нулю. Опорное решение, коэффиценты разложений и оценки разложений векторов условий по базису опорного решения записываются в симплексную таблицу :
Сверху над таблицей для удобства вычислений оценок записываются коэффициенты целевой функции. В первом столбце "Б" записываются векторы, входящие в базис опорного решения. Порядок записи этих векторов соответствует номерам разрешенных неизвестных в уравнениях ограничениях. Во втором столбце таблицы "С б " записываются коэффициенты целевой функции при базисных переменных в том же порядке. При правильном расположении коэффициентов целевой функции в столбце "С б " оценки единичных векторов, входящих в базис, всегда равных нулю.
В последней строке таблицы с оценками Δ k в столбце "А 0 " записываются значения целевой функции на опорном решении Z(X 1).
Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ 1 = -2, Δ 3 = -9 для векторов А 1 и А 3 отрицательные.
По теореме об улучшении опорного решения, если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.
Определим, введение какого из двух векторов приведет к большему приращению целевой функции.
Приращение целевой функции находится по формуле: .
Вычисляем значения параметра θ 01 для первого и третьего столбцов по формуле:
Получаем θ 01 = 6 при l = 1, θ 03 = 3 при l = 1 (таблица 26.1).
Находим приращение целевой функции при введении в базис первого вектора ΔZ 1 = — 6*(- 2) = 12, и третьего вектора ΔZ 3 = — 3*(- 9) = 27.
Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ 03 достигается в первой строке (l = 1).
Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5). (таблица 26.2)
Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.
Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ 02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х 22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5) (таблица 26.3).
Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные
Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.
Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).
Метод линейного программирования дает возможность обосновать наиболее оптимальное экономическое решение в условиях жестких ограничений, относящихся к используемым в производстве ресурсам (основные фонды, материалы, трудовые ресурсы). Применение этого метода в экономическом анализе позволяет решать задачи, связанные главным образом с планированием деятельности организации. Данный метод помогает определить оптимальные величины выпуска продукции, а также направления наиболее эффективного использования имеющихся в распоряжении организации производственных ресурсов.
При помощи этого метода осуществляется решение так называемых экстремальных задач, которое заключается в нахождении крайних значений, то есть максимума и минимума функций переменных величин.
Этот период базируется на решении системы линейных уравнений в тех случаях, когда анализируемые экономические явления связаны линейной, строго функциональной зависимостью. Метод линейного программирования используется для анализа переменных величин при наличии определенных ограничивающих факторов.
Весьма распространено решение так называемой транспортной задачи с помощью метода линейного программирования. Содержание этой задачи заключается в минимизации затрат, осуществляемых в связи с эксплуатацией транспортных средств в условиях имеющихся ограничений в отношении количества транспортных средств, их грузоподъемности, продолжительности времени их работы, при наличии необходимости обслуживания максимального количества заказчиков.
Кроме этого, данный метод находит широкое применение при решении задачи составления расписания. Эта задача состоит в таком распределении времени функционирования персонала данной организации, которое являлось бы наиболее приемлемым как для членов этого персонала, так и для клиентов организации.
Данная задача заключается в максимизации количества обслуживаемых клиентов в условиях ограничений количества имеющихся членов персонала, а также фонда рабочего времени.
Таким образом, метод линейного программирования весьма распространен в анализе размещения и использования различных видов ресурсов, а также в процессе планирования и прогнозирования деятельности организаций.
Все же математическое программирование может применяться и в отношении тех экономических явлений, зависимость между которыми не является линейной. Для этой цели могут быть использованы методы нелинейного, динамического и выпуклого программирования.
Нелинейное программирование опирается на нелинейный характер целевой функции или ограничений, либо и того и другого. Формы целевой функции и неравенств ограничений в этих условиях могут быть различными.
Нелинейное программирование применяется в экономическом анализе в частности, при установлении взаимосвязи между показателями, выражающими эффективность деятельности организации и объемом этой деятельности, структурой затрат на производство, конъюнктурой рынка, и др.
Динамическое программирование базируется на построении дерева решений. Каждый ярус этого дерева служит стадией для определения последствий предыдущего решения и для устранения малоэффективных вариантов этого решения. Таким образом, динамическое программирование имеет многошаговый, многоэтапный характер. Этот вид программирования применяется в экономическом анализе с целью поиска оптимальных вариантов развития организации как в настоящее время, так и в будущем.
Выпуклое программирование представляет собой разновидность нелинейного программирования. Этот вид программирования выражает нелинейный характер зависимости между результатами деятельности организации и осуществляемыми ей затратами. Выпуклое (иначе вогнутое) программирование анализирует выпуклые целевые функции и выпуклые системы ограничений (точки допустимых значений). Выпуклое программирование применяется в анализе хозяйственной деятельности с целью минимизации затрат, а вогнутое — с целью максимизации доходов в условиях имеющихся ограничений действия факторов, влияющих на анализируемые показатели противоположным образом. Следовательно, при рассматриваемых видах программирования выпуклые целевые функции минимизируются, а вогнутые — максимизируются.
Рассмотрим симплекс -метод
для решения задач линейного программирования (ЛП). Он основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает.
Алгоритм симплекс-метода следующий:
Рассмотрим решение задачи с использованием рассмотренного выше алгоритма.
Дано:
Приводим задачу к каноническому виду:
Составляем вектора:
Заполняем симплекс – таблицу:
:
Пересчитаем первый элемент вектора Р 0
, для чего составляем прямоугольник из чисел: и получаем: 
.
Аналогичные расчеты выполним для всех остальных элементов симплекс – таблицы:
В полученном плане f – строка содержит один отрицательный элемент – (-5/3), вектора P 1 . Он содержит в своем столбце единственный положительный элемент, который и будет разрешающим элементом. Сделаем пересчет таблицы относительно этого элемента:
Отсутствие отрицательных элементов в f
– строке означает, что найден оптимальный план
:
F* = 36/5, Х = (12/5, 14/5, 8, 0, 0).
Заказать любые задания по этой дисциплине можно у нас на сайте. Прикрепить файлы и указать сроки можно на
