Задача линейного программирования

Рецензент: Нестерова С.И, к.э.н., доцент

Печатается по решению

Учебно-методического совета

Международного института рынка

Ó Международный институт рынка, 2014

Методы оптимальных решений

Программа курса для заочной формы обучения

1. Понятие экономико-математической модели, ее переменные и параметры. Сущность методов оптимизации. Основные термины и понятия: целевая функция, ограничения, критерий оптимальности

2. Классификация основных математических методов принятия оптимальных решений

3. Элементы математического программирования. Основные термины и понятия задачи линейного программирования (ЗЛП)

4. Графический метод решения ЗЛП

5. Симплекс метод решения ЗЛП

6. Транспортная задача как пример ЗЛП. Методы построения начального плана

7. Правила и схемы принятия решений на основе математической теории игр: Стратегии. Матрица рещений. Критерии выбора.

8. Принятие решений в условиях неопределенности: правило минимакса, максимина, максимакса, критерий Гурвица

9. Принятие решений в условиях определенности. Использование вероятностей. Оптимизация математического ожидания. Чувствительность решения к изменению вероятностей.

10. Применение теории графов для принятия оптимальных решений. Основные термины и понятия теории графов. Расстояние, путь.

11. Методы нахождения кратчайшего пути от заданной вершины. Остов наименьшего веса.

12. Понятие сетевого графа. Сетевое планирование, сетевой график работ. Критический путь.

13. Дерево решений – особенности графа, основные термины и понятия.

14. Экспертные методы принятия решений. Математические методы анализа экспертных оценок.

Тема 3 «Задача линейного программирования», Темы 7-9 Правила и схемы принятия решений, Тема 11 Нахождение кратчайшего пути и Тема 13 Дерево решений, Тема 14 Экспертные оценки могут быть выполнены как лабораторные работы в компьютерном классе 208. Описание лабораторных работ и требования к отчету находятся в студенческой сети StudentAqua в папке MOR MPUR 15-16.

Остальные темы изучаются реферативно по электронным ресурсам. В качестве примеров можно использовать описание лабораторных работ в компьютерном классе (205). Требование к выполнению контрольной работы – на положительную оценку необходимо выполнить одну лабораторную работу и один теоретический отчет по любой оставшейся теме объемом 2-3 листа формата А4.

Пример теоретического отчета по теме:

Математический аппарат для решения задач оптимизации

Понятие математического программирования

Математическое программирование – это математическая дисциплина, в которой разрабатываются методы отыскания экстремальных значений целевой функции среди множества ее возможных значений, определяемых ограничениями.

Наличие ограничений делает задачи математического программирования принципиально отличными от классических задач математического анализа по отысканию экстремальных значений функции. Методы математического анализа для поиска экстремума функции в задачах математического программирования оказываются непригодными.

Для решения задач математического программирования разработаны и разрабатываются специальные методы и теории. Так как при решении этих задач приходится выполнять значительный объем вычислений, то при сравнительной оценке методов большое значение придается эффективности и удобству их реализации на ЭВМ.

Математическое программирование можно рассматривать как совокупность самостоятельных разделов, занимающихся изучением и разработкой методов решения определенных классов задач.

В зависимости от свойств целевой функции и функции ограничений все задачи математического программирования делятся на два основных класса:

1) задачи линейного программирования

2) задачи нелинейного программирования.

Если целевая функция и функция ограничений – линейные функции, то соответствующая задача поиска экстремума является задачей линейного программирования. Если хотя бы одна из указанных функций нелинейная, то соответствующая задача поиска экстремума является задачей нелинейного программирования.

Задача линейного программирования

Линейное программирование – один из первых и наиболее подробно изученных разделов математического программирования. Именно линейное программирование явилось тем разделом, с которого и начала развиваться дисциплина «математическое программирование». Термин «программирование» обозначает планирование, составление поэтапной программы действий., широко применяется для решения экономико-математических, управленческих, инженерных и других задач.

Термины «линейное программирование», «нелинейное программирование», «математическое программирование» и т.д. в научной и учебной литературе стали общепринятыми и поэтому будут сохранены. Линейное программирование стало быстро развиваться после Второй мировой войны, привлекая внимание математиков, экономистов и инженеров благодаря возможности широкого практического применения, а также математической стройности.

Линейное программирование применяется при решении экономических задач, в таких задачах, как управление и планирование производства; определение оптимального размещения оборудования на морских судах, в цехах; определение оптимального плана перевозок груза (транспортная задача); оптимальное распределение кадров и т.д.

Задача линейного программирования

Задача линейного программирования (ЗЛП), состоит в нахождении минимума (или максимума) линейной функции при линейных ограничениях. Общая форма задачи имеет вид: найти min cx при условиях:

a_ix-b_i≥0,iÎ I₁,

a_ix-b_i=0, iÎ I₂,

x_j≥0, jÎ J₁,

где I₁ È I₂ = {1,…, m }, I₁ Ç I₂ = Æ, J₁ Ì{1,…, n }, x = (x₁,…,x_n)^T,

c = (c₁,…,c_n), a = (a_i1,…, a_in), i = 1,…, m.

Здесь удобнее считать c и a_i вектор-строками,

а x и b = (b₁,…b_m)^T – вектор-столбцами.

Наряду с общей формой используются также каноническая и стандартная формы. Как в канонической, так и в стандартной форме:

J = {1,… n }, все переменные в любом допустимом решении задачи должны принимать неотрицательные значения (в отличие от так называемых свободных переменных, на область значений которых подобное ограничение не накладывается).

Задача линейного программирования в канонической форме:

w = cx ® min,

Ax = b,

x ≥ 0.

Задача линейного программирования в стандартной форме:

w = cx ® min,

Ax ≥ b,

x ≥ 0.

В обоих случаях A есть матрица размерности m×n, i -строка которой совпадает с вектором a_i.

ЗЛП в общей форме сводится к ЗЛП в канонической. Под этим понимается существование общего способа построения по исходной задаче новой ЗЛП (в нужной нам форме), любое оптимальное решение которой преобразуется в оптимальное решение исходной задачи и наоборот. Тем самым возможно, не теряя общности, заниматься изучением ЗЛП, представленных в канонической форме.