Математическая модель задачи

Лекция 3. Линейное программирование

План лекции:

1. Основные понятия и определения.

2. Математическая модель задачи.

3. Графический метод решения.

Основные понятия и определения

Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась ещё в XIX веке. При математическом анализе процесса расширенного производства использовались алгебраические соотношения, анализ их проводился с помощью дифференциального исчисления. Это давало возможность получить общее представление о проблеме.

Развитие экономики потребовало количественных показателей, и в 1920 годы был создан межотраслевой баланс (МОБ). Он-то и послужил толчком в деле создания и исследования математических моделей. Разработка МОБ в 1924-1925 годах в СССР повлияла на работы экономиста и статистика Василия Васильевича Леонтьева. Он разработал межотраслевую модель производства и распределения продукции.

В 1938 году Леонид Витальевич Канторович в порядке научной консультации приступил к изучению чисто практической задачи по составлению наилучшего плана загрузки лущильных станков (фанерный трест). Эта задача не поддавалась обычным методам. Стало ясно, что задача не случайная.

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

Изучение подобных задач привело к созданию новой научной дисциплины линейного программирования и открыло новый этап в развитии экономико-математических методов.

В 1949 году американский математик Джордж Бернард Данциг разработал эффективный метод решения задач линейного программирования (ЗЛП) - симплекс-метод.

Термин «программирование» нужно понимать в смысле «планирования» (один из переводов англ. programming). Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, ещё до того, как компьютеры были использованы для решения линейных задач оптимизации.

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

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

Математическая модель задачи

Формы записи задачи линейного программирования:

Общей задачей линейного программирования называют задачу

(1)

при ограничениях

(2)

(3)

(4)

(5)

- произвольные (6)

где - заданные действительные числа; (1) – целевая функция; (1) – (6) –ограничения;

- план задачи.

Наиболее часто используются оптимизационные модели принятия решений. Их общий вид таков:

F(X) → max;

X ϵ A,

где Х — параметр, который менеджер может выбирать (управляющий параметр). Он может иметь различную природу — число, вектор, множество и т.п.

Цель менеджера — максимизировать целевую функцию F(X), вы­брав соответствующий Х. При этом он должен учитывать ограничения X ϵ A на возможные значения управляющего параметра Х — он должен лежать в множестве А. Рассмотрим примеры оптимизационных задач менеджмента.

Среди оптимизационных задач менеджмента наиболее известны задачи линейного программирования, в которых максимизируемая функция F(X) линейная, а ограничения А задаются линейными не­равенствами.