Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.
Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.
· Удельная прибыль при возможном выпуске четырех видов изделий с использованием трех видов продукции: вектор С:
На предприятии предполагается организовать выпуск четырех видов изделий в количествах соответственно:
Фабрика располагает тремя видами ресурсов, количество которых определяется вектором В. Известны также нормы расходов ресурсов (матрица А) и прибыль от реализации одного изделия (матрица С).
Требуется составить такой план выпуска изделий, при котором предприятие уложится в имеющиеся ресурсы, а суммарная прибыль будет максимальной.
· – норма ресурсов на изготовление j-го изделия с использованием i-го ресурса;
Найти производственную программу максимизирующую целевую функцию прибыли:
Для решения задачи линейного программирования используется симплексный метод, для которого учитываются следующие условия:
· Задача должна быть классической, т.е. на минимум (максимум);
· В каждом уравнении должна быть базисная переменная.
1. Для решения систему ограничений (1.1.), состоящую из неравенств, следует преобразовать в равенства при помощи дополнительных неотрицательных неизвестных , т.е. заменить ее системой алгебраических уравнений. В целевую функцию также добавляются дополнительные переменные с коэффициентами 0:
где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Для них также существует условие неотрицательности:
Дополнительные переменные с коэффициентом +1 à являются базисными.
| Б | Н | ||||||||
| 168,00 | 3,00 | 2,00 | 0,00 | 3,00 | 1,00 | 0,00 | 0,00 | 84,00 | 0,67 |
| 60,00 | 0,00 | 1,00 | 4,00 | 2,00 | 0,00 | 1,00 | 0,00 | 60,00 | 0,33 |
| 112,00 | 1,00 | 3,00 | 5,00 | 0,00 | 0,00 | 0,00 | 1,00 | 37,33 | — |
| 0,00 | -18,00 | -19,00 | -8,00 | -5,00 | 0,00 | 0,00 | 0,00 | — | -6,33 |
– коэффициент целевой функции при базисных переменных;
3. Выбирается разрешающий столбец по максимальной по величине двойственной оценке (второй столбец)
4. Выбирается разрешающая строка с помощью коэффициента – отношения элементов столбца Н и соответствующих элементов ключевого столбца.
5. Производится перерасчет таблицы по методу Жордано-Гаусса: вычисляется столбец β делением ключевого разрешающего на ключевой элемент, затем из каждой строки вычитается разрешающая строка, умноженная на соответствующий коэффициент β. Сама разрешающая строка делится на ключевой элемент.
Признак окончания расчетов – значения всех двойственных оценок больше или равны 0 (в задаче на максимум).
Критерий оптимальности в задаче на максимизацию прибыли – отсутствие отрицательных двойственных оценок.
Двойственные оценки фактических переменных ( ) показывают, насколько уменьшится значение целевой функции (прибыль), если ввести в план одно изделие соответствующего вида.
Двойственные оценки дополнительных переменных ( ) показывает, насколько уменьшится целевая функция (прибыль) при уменьшении величины соответствующего ресурса на единицу (или увеличится при его увеличении).
Решение задачи с помощью программы Excel (на примере)
Предприятие выпускает четыре вида изделий ( ) . Для их изготовления используется три вида ресурсов ( ). Известны нормы расходов ресурсов на единицу продукции каждого вида, цена за единицу продукции и запасы ресурсов.
1. Для расчета следует организовать данные следующим образом: в первой таблице указать виды изделия, цены за единицу, план выпуска, в отдельной ячейке ввести формулу расчета значения целевой функции; во второй таблице указать ресурсы, нормы расходов, формулы с указанием фактических расходов ресурсов и их запасов.
2. С помощью функции «Поиск решения» производится решение задачи симплекс-методом. Для этого в окне поиска указать: целевую ячейку (целевая функция), условие максимизации целевой функции, изменяемые ячейки (план выпуска).
3. Ввести ограничения, указанные в условии задачи: суммарные расходы ресурсов не должны превышать заданного объема. Также следует указать условие неотрицательности переменных.
Из отчетов по пределам и устойчивости можно сделать следующие выводы:
· Какие ресурсы использованы полностью, а для каких имеется резерв;
· При каких изменениях цен оптимальный план выпуска будет оставаться неизменным;
· При каких изменениях объемов ресурсов структура оптимального плана будет неизменной;
· Теневые цены показывают, на сколько изменится прибыль при увеличении объема ресурса.
2. Двойственность в линейном программировании. Симметричная пара двойственных задач, правила составления, их экономическое содержание.
(См. №1)Предприятие выпускает продукцию, используя те же ресурсы, что и первое предприятие. Первому предлагается предлагается продать все имеющиеся у него ресурсы по следующим ценам: ; и .
Известны объемы ресурсов на первом предприятии (матрица В), нормы расходов ресурсов на производство изделий (матрица А) и прибыль от реализации одного изделия (матрица С).
Необходимо определить цены , при которых первое предприятие примет предложение продажи ресурсов.
Найти вектор , максимизирующий суммарный прирост прибыли
при условии сохранения двойственных оценок ресурсов и структуры производственной программы (по примеру):
Пусть – вектор дополнительных объемов ресурсов. Для решения будут использоваться найденные ранее двойственные оценки, следовательно, должно выполняться равенство:
Т.к. «узкими местами производства» являются только первый и третий ресурсы, а второй ресурс находится в избытке, то задача состоит в том, чтобы найти вектор , максимизирующий суммарный прирост прибыли:
Для дальнейшего решения неравенства (3.3.) и (3.3.) следует переписать в виде систем:
Получена задача линейного программирования: максимизировать функцию (3.1.) при условиях (3.5.), (3.6.) и (3.4.).
Т.к. задача имеет только две переменные, ее можно решить графически.
Введем параметр состояния – количество средств, выделяемых нескольким предприятиям, и определим функцию состояния – максимальную прибыль на первых k предприятиях, если они вместе получают руб.
Если из рублей k-е предприятие получит рублей, то каково бы ни было это значение, оставшиеся ( рублей следует распределить между предприятиями от первого до k-го так, чтобы была получена максимальная прибыль . Тогда прибыль k предприятий будет равна . Нужно выбрать такое значение между 0 и чтобы эта сумма была максимальной, и мы переходим к рекуррентному соотношению:
Первым этапом решения задачи является составление таблицы 2. Значения складываются со значениями и на каждой северо-западной диагонали отмечается максимальное значение:
Отмеченными значениями заполняется таблица 3 и указываются соответствующие значения :
Следующий этап – табулирование функции , (таблица 4) и составление таблицы 5:
В таблице 6 заполняется только диагональ для значения . Максимальное значение на этой диагонали следовательно четвертому предприятию должно быть выделено
На долю остальных предприятий остается 700 – 200 = 500 тыс. руб. Согласно таблице 5 третьему предприятию должно быть выделено:
Аналогично находим значение для второго предприятия:
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:
Максимальный прирост прибыли составит (согласно таблице 1):
10. Оптимизация плана распределения ресурсов между производственными подразделениями с помощью двойственных оценок при двухуровневой системе управления.
А – нормы расходов на единицу продукции каждого вида:
С – удельная прибыль по каждому виду продукции:
Предприятие имеет три филиала, каждый из которых производит по два вида продукции, требующей одних и тех же видов ресурсов. Каждая фабрика располагает двумя видами ресурсов (матрицы , суммарные количества которых равны 242 ед. и 185 ед. соответственно.
Известны нормы расходов для каждого вида продукции отдельно по филиалам (матрицы ), а также удельная прибыль по каждому виду продукции по филиалам (матрицы ).
Требуется перераспределить ресурсы между филиалами таким образом, чтобы суммарная прибыль по предприятию была максимальной.
Найтивекторы (распределение ресурсов между филиалами) и оптимальный план:
Соответственно, и суммарную прибыль L , при следующих ограничениях:
| Изделия | Изд1 | Изд2 | Целевая функция/объем продаж |
| Цена за единицу | |||
| План выпуска |
| Изделия | Изд1 | Изд2 | Целевая функция/объем продаж |
| Цена за единицу | |||
| План выпуска | 13,4 | 720,4 |
| Изделия | Изд1 | Изд2 | Целевая функция/объем продаж |
| Цена за единицу | |||
| План выпуска | 5,25 | 433,5 |
Разница для второй пары максимально, следовательно, второй и третий филиалы выбираются для перераспределения.
| Изделия | Изд1 | Изд2 | Изд3 | Изд4 | Целевая функция |
| Цена за единицу | |||||
| План выпуска | 18,6 | 11,2 | 1344,4 |
Переменная , что означает, что первое изделие в третьем филиале выпускать не следует.
Распределение ресурсов принимает следующие значения:
Объем ресурсов в первом филиале остается неизменным.
Прибыль по всему предприятию увеличилась и составляет L = 1344,5 + 550 = 1894,5 д. ед.
Следующий этап – распределение ресурсов между первым и вторым филиалами, для которых разница между двойственными оценками составляет 4,6. Объединенная задача для этих филиалов будет иметь вид:
| Изделия | Изд1 | Изд2 | Изд3 | Изд4 | Целевая функция |
| Цена за единицу | |||||
| План выпуска | 25,04 | 18,39 | 1666,082 |
Переменные что означает, что в первом филиал выпускать продукцию второго вида не следует.
Разница между двойственными оценками между вторым и третьим предприятием составляет 4,9.
Объем ресурсов в третьем филиале остается неизменным.
Прибыль по всему предприятию увеличилась и составляет L = 1666,08 + 436,8 = 2103,6д. ед..
По решению двух объединенных задач, общая прибыль по предприятию увеличилась на 399,6 единиц. Продолжая выполнять последовательные шаги оптимизации, мы будем увеличивать суммарную прибыль шаг за шагом. Процесс продолжается до тех пор, пока двойственные оценки задачи не станут примерно одинаковыми.
11. Применение метода динамического программирования для оптимального управления запасами и производством.
12. Модель экономически выгодных размеров заказываемых партий (модель ЭВРП). Формула Уилсона, характеристическое свойство оптимального размера партии.
13. Задача формирования оптимального портфеля ценных бумаг. Математическая модель задачи, её решение и анализ.
| Б | Н | ||||||
| 53,33 | -0,33 | 0,33 | 0,00 | 0,00 | 1,00 | 0,33 | -1,00 |
| 33,33 | 0,67 | 0,33 | 0,00 | 1,00 | 0,00 | 0,33 | 0,00 |
| 4,58 | 1,67 | 0,08 | 1,00 | 0,00 | 0,00 | -0,42 | 0,25 |
| 11175,00 | 136,00 | 62,00 | 0,00 | 0,00 | 0,00 | 55,00 | 0,00 |
Отрицательных двойственных оценок нет, следовательно, получен оптимальный план:
Не выполняется условие целочисленности решения: элементы базисного плана нецелочисленны.
Если в найденном плане задачи (1) – (3), (4) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (1) – (3), либо устанавливают ее неразрешимость.
Рассмотрим задачу с двумя переменными, вошедшими в базис, и решим ее методом «ветвей и границ» для поиска целочисленного решения.
Системы уравнений (1) и (2) определяют область допустимых значений ОАВС, где координаты вершины В определяют оптимальный план производства.
Переменная в оптимальном плане не является целой, следовательно, относительно нее будет производится ветвление.
Процесс ветвления делит исходную задачу на две подзадачи а) и б). Одна из них отличается добавлением условия , во второй подзадаче добавляется условие . При этом из области ОАВС исключается подобласть .
В результате преобразований получен оптимальный целочисленный план производства:
Для проверки решения в программе Excel с помощью средств «Поиск решений» при описании ограничений необходимо учесть условия целочисленности для изменяемых ячеек – т.е. указать, что изменяемые ячейки (план выпуска) могут быть только целыми числами.
· Если критерии на min, их следует привести к max умножением на -1;
· Критерии следует ранжировать по степени важности для предприятия;
· Назначаются уступки (величина допустимого отклонения .
Для данной задачи переговорное множество совпадает с областью допустимых значений, построенной по системе (5.4). Максимизируем функцию при условиях (5.4.). Для этого удобно воспользоваться графическим методом (рисунок 5)
Переходим к максимизации функции при условиях (8.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как , то дополнительное ограничение будет иметь вид: 6 (5.6.)
Графическое решение задач (5.2.), (5.4.), (5.5.) представлено на рисунке 6.
Переходим к максимизации функции при условиях (5.4) и дополнительном ограничении, учитывающем, что по критерию нельзя уступать более чем на . Так как 7,25 , то дополнительное ограничение будет иметь вид: (5.7.)
Графическое решение задач (5.2.), (5.4.), (5.5.) и (5.7.) представлено на рисунке (7).
Получено оптимальное решение многокритериальной задачи:
Задача линейного программирования, формулировка, математическая модель, алгоритм решения симплексным методом и в Excel. Постоптимизационный анализ решения задачи.
· Удельная прибыль при возможном выпуске четырех видов изделий с использованием трех видов продукции: вектор С:
На предприятии предполагается организовать выпуск четырех видов изделий в количествах соответственно:
Фабрика располагает тремя видами ресурсов, количество которых определяется вектором В. Известны также нормы расходов ресурсов (матрица А) и прибыль от реализации одного изделия (матрица С).
Требуется составить такой план выпуска изделий, при котором предприятие уложится в имеющиеся ресурсы, а суммарная прибыль будет максимальной.
[expert_bq id=»1570″]Изделия А , В и С могут производиться в любых соотношениях сбыт обеспечен , но производство ограничено выделенным предприятию сырьем каждого вида. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Поскольку среди векторов имеются три единичных вектора, для данной задачи можно непосредственно записать опорный план. Таковым является план Х =(0; 0; 0; 360; 192; 180), определяемый системой трехмерных единичных векторов которые образуют базис трехмерного векторного пространства.
Симплекс-метод, составление симплекс-таблиц
Т.к. «узкими местами производства» являются только первый и третий ресурсы, а второй ресурс находится в избытке, то задача состоит в том, чтобы найти вектор , максимизирующий суммарный прирост прибыли:
| Изделия | Изд1 | Изд2 | Целевая функция/объем продаж |
| Цена за единицу | |||
| План выпуска | 5,25 | 433,5 |
Алгоритм и пример симплекс-метода (ММЭ)
Симплекс-метод — это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.
. Алгоритм симплекс-метода
Пример 5.1. Решить следующую задачу линейного программирования симплекс-методом:
1 этап: формирование исходной симплекс-таблицы.
Исходная задача линейного программирования задана в стандартной форме. Приведем ее к каноническому виду путем введения в каждое из ограничений-неравенств дополнительной неотрицательной переменной, т.е.
В полученной системе уравнений примем в качестве разрешенных (базисных) переменные х3, х4, х5, х6, тогда свободными переменными будут х1,х2. Выразим базисные переменные через свободные:
На основе полученной задачи сформируем исходную симплекс-таблицу:
2 этап: определение базисного решения.
Согласно определению базисного решения свободные переменные равны нулю, а значения базисных переменных – соответствующим значениям свободных чисел, т.е.:
3 этап: проверка совместности системы ограничений ЗЛП.
На данной итерации (в таблице 5.3) признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).
4 этап: проверка ограниченности целевой функции.
На данной итерации (в таблице 5.3) признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).
5 этап: проверка допустимости найденного базисного решения.
Так как найденное базисное решение не содержит отрицательных компонент, то оно является допустимым.
Найденное базисное решение не является оптимальным, так как согласно признаку оптимальности (признак 4) в строке целевой функции не должно быть отрицательных элементов (свободное число данной строки при рассмотрении данного признака не учитывается). Следовательно, согласно алгоритму симплекс-метода переходим к 8 этапу.
8 этап: определение разрешающего элемента.
Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной.
В таблице 5.4 наименьшее положительное оценочное отношение соответствует строке «х5», следовательно, она будет разрешающей.
Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент , который расположен на пересечении строки «х5» и колонки «х2».
9 этап: преобразование симплекс-таблицы.
Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х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. Преобразование остальных элементов симплекс-таблицы.
Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».
В результате данных преобразований получили новую симплекс- таблицу (таблица 5.5).
По результатам симплекс-преобразований предыдущей итерации составляем новую симплекс-таблицу:
Симплекс-таблица II итерации
Метод симплекса для чайников — описание с примером подробного решения — Помощник для школьников
Решение любой задачи линейного программирования можно найти симплексным методом . Прежде чем применять симплекс-метод, следует записать исходную задачу в форме основной задачи линейного программирования, если она не имеет такой формы записи.
