Рис. 1.1 Рис. 1.1 Рис. 1.3
Рис. 1.4 Рис. 1.5 Рис. 1.6
Решение задачи линейного программирования можно получить, если допустимая область существует. Заметим, что допустимая область представляет собой выпуклый многогранник. Задача линейного программирования имеет свои особенности:
если целевая функция имеет максимум (минимум) на выпуклом многограннике допустимых решений, то он достигается в вершине этого многогранника;
если целевая функция имеет максимум (минимум) более чем в одной вершине выпуклого многогранника допустимых решений, то он достигается в любой точке, являющейся линейной комбинацией этих вершин.
Решение задач линейного программирования с использованием симплекс-таблицы
Для составления симплекс-таблицы ограничения должны быть записаны в виде равенств
;
; (1.14)
и неравенств Целевая функция формируется в виде
. (1.15)
Данный подход предусматривает выполнение следующих этапов:
формирование целевой функции и определение граничных условий, которые могут иметь вид равенств или неравенств;
преобразование ограничений из неравенств в систему равенств путем ввода вспомогательных переменных (эти переменные имеют экономическое содержание и характеризуют резерв тех ресурсов, по которым вводится ограничение);
построение исходной симплексной таблицы-матрицы, в которой в формируемый план входят только свободные переменные. Таблица имеет следующий вид (табл. 1.3);
построение опорного плана;
Таблица 1.3
Симплекс-таблица Базис … … … 1 0 0 … 0 1 0 … … … … … … … … … … 0 0 1 … 0 0 0
ввод в исходный вариант плана реальных переменных и вычисление значений целевой функции;
определение аргумента, доставляющего экстремум целевой функции и запись его в качестве элемента плана.
При этом каждый из показателей, характеризующий ограничительное условие, делится на соответствующий коэффициент при вводимой переменной — удельный расход данного ресурса. Тогда наименьшее частное определит максимально возможное в условиях принятых ограничений использование ресурсов при заданном критерии оптимальности. Полученный результат вводится в соответствующую строку симплексной таблицы. По этой строке матрицы весь ресурс исчерпан, она является узким местом и подлежит выводу. На ее место вводится новая строка, предварительно пересчитанная. Формируется новый вариант симплексной таблицы, соответствующийй итерации. Пересчет строки ведется по разрешающему элементу, находящемуся на пересечении строки с номером вводимой переменной и столбца с номером выводимой переменной. Каждый элемент вводимой строки необходимо разделить на разрешающий элемент. Все остальные элементы матрицы пересчитываются по столбцам по следующим правилам:
1) значения столбцов, в которых в строке разрешающего элемента стоит ноль, переносятся в новую матрицу без изменения;
1) при пересчете остальных столбцов необходимо из первоначального значения соответствующих элементов вычесть произведение элемента вводимой строки этого столбца на соответствующий коэффициент в столбце разрешающего элемента.
Последовательность расчетов с использованием симплекс-таблицы можно представить в виде блок-схемы (рис. 1).
Рис. 1 Блок-схема последовательности расчетов с использованием симплекс-таблицы
Матрица будет оптимальной, если первая строка не содержит отрицательных чисел, т. е. располагаемые ресурсы полностью использованы. Если матрица неоптимальная, то вводятся новые переменные, выбираемые из набора, сформированного по ограничительным условиям и критериальной функции, и содержащиеся в последнем варианте симплекс-таблицы, т. е. производится следующий шаг по улучшению матрицы. Далее расчет осуществляется аналогичным образом, как описано выше.
Особенности задач линейного программирования
Особенностями задач линейного программирования является то, что множество допустимых решений представляет собой выпуклый многогранник, а наибольшее значение целевая функция принимает в одной из его вершин. В геометрической интерпретации симплекс-метод представляет собой метод целенаправленного перебора вершин допустимого многогранника. Поэтому его иногда называют методом градиентного, или наискорейшего, спуска вдоль ребер выпуклого многогранника допустимых решений. Для поиска экстремума необходимо:
выбрать направление спуска;
определить величину шага.
В симплекс-методе выбирается направление спуска вдоль того ребра многогранника, на котором проекция градиента целевой функции максимальна. Таким образом, обеспечивается выбор направления скорейшего увеличения целевой функции.
Пример. Пусть дана задача ЛП
2x + y → max
— x + y ≤ 2
x + 2y ≤ 7
4x — 3y ≤ 6
x ≥ 0, y ≥ 0/
Геометрическая интерпретация задачи приведена на рис. 1. Ясно, что решением является точка пересечения прямых
x + 2y = 7 и 4x — 3y = 6, т. е. (x*, y*) = (3, 2).
Рис. 1
Очевидно, что графический метод решения задач ЛП применим лишь в случае малой размерности пространства. В общем случае для решения задач линейного программирования в пространстве произвольной размерности широко используется симплекс-метод. Симплекс-метод решения задач ЛП основан на «разумном» переборе граничных точек допустимого множества.
1. Абчук В. А. Экономико — математические методы. — СПб., Союз, 1999.
2. Багриновский К. А., Матюшок В. М. Экономико — математические методы и модели. — М.: РУДН, 1999.
3. Гаркас В. А. Использование VS Excel и VBA в экономике и финансах. — СПб., 1999.
4. Горбовцов Г. Я. Методы оптимизации и: Учебно — практическое пособие. — М.: МЭСИ, 2000.
5. Горчаков А. А., Орлова И. В. Компьютерные экономико — математические модели. — М.: ЮНИТИ, 1995.
6. Жданов С. А. Экономические модели и методы в управлении. — М.: ДиС, 1998.
7. Зайцев М. Г. Методы оптимизации управления для менеджеров. Компьютерно — ориентированный подход: Учеб. Пособие. — М.: Дело, 2002.
8. Замков О. О., Толтопятенко А. В., Черемных Ю. П. Математические методы в экономике: Учебник. — М.: ДИС, 1997.
9. Касимов Ю. Ф. Основы теории оптимального портфеля ценных бумаг. — М. ИИД «Филинъ», 1998.
10. Кремер Н. Ш. Исследование операций в экономике. — М.: ЮНИТИ, 1997.
11. Мельник М. М. Экономико — математические методы в планировании и управлении материально — техническим снабжением. — М.: Высшая школа, 1990.
12. Орлова И. В. Экономико — математические методы и модели. Выполнение расчетов в среде Excel. Практикум. — М.: Финстатинформ, 2000.
13. Орлова И. В., Половников В. А., Федосеева Г. В. Курс лекций по экономико — математическому моделированию. — М.: Экономическое образование, 1993.
14. Солодовников А. С., Бабайцев В. А., Браилов А. В. Математика в экономике: Учебник. В 2-х частях. Ч.
1. -М.: Финансы и статистика, 1999.
15. Уотшем Т. Дж., Паррамоу К. Количественные методы в финансах. — М.: Финансы, ЮНИТИ, 1999.
16. Федосеев В. А., Гармаш А. Н., Дайтбегов Д. М., Орлова И. В., Половников В. А. Экономико — математические методы и прикладные модели: Учеб. Пособие для вузов/ Под ред. В. В. Федосеева. — М.: ЮНИТИ, 1999.
17. Федосеев В. В., Гармаш А. Н. и др. Экономико — математические методы и прикладные модели. — М.: ЮНИТИ, 1999.
18. Хазинова Л. Э. Математическое моделирование в экономике. — М.: БЕК, 1998.
19. Шипин Е. В., Чхартиневили А. Г. Математические методы и модели в управлении. — М.: Дело, 2000.
20. Эддоус М., Стенсфилд Р. Методы принятия решения. — М.: ЮНИТИ, 1997.
21. Экономико — математические методы и прикладные модели: Учебное пособие для вузов/ Под ред. В. В. Федосеева. — М.: ЮНИТИ, 1999.
