Курс лекций по линейному программированию

Курс лекций по линейному программированию.

Лекция № 1: «Предмет курса. Оптимизационные задачи. Основы линейного программирования».

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

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

Требуется определить максимум и минимум функции f(x₁ , … , x_n ) при условиях:

1.) g(x₁ , … , x_n ) {≤, =, ≥} b_i i=

2.) x_j ≥0 j=

- показатель качества решения (целевая функция)

* - ограничения, которые определяют множество допустимых решений.

Для того чтобы решить задачу, достаточно найти её оптимальное значение (указать значение всех переменных, удовлетворяющих ограничениям задачи, которые доставляют функции f наибольшее или наименьшее значение среди всех значений функции на допустимых значениях переменных, или доказать что таких решений нет).

Процедура нахождения решений экстремальных задач называется процедурой оптимизации.

Задача № 1 называется неразрешимой, если она не имеет решения. Это возможно в случае, когда целевая функция неограниченно на допустимом множестве решений.

Решить задачу – это найти её оптимальное решение, либо установить её неразрешимость.

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

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

Для линейных задач существует универсальный алгоритм решения, для нелинейных – алгоритма нет.

Линейное программирование

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

Общей задачей ЛП является задача нахождения max :

1.) ∑a_ij x_j {<, =, >} b_i ; i= j=

2.) x_j ≥0 j=

где a_ij , b_i , c_j – заданные постоянные, при этом целевая функция называется линейной формой.

Условие 1 – ограничение задачи

Условие 2 – условие неотрицательности переменных.

Стандартной (симметричной) задачей ЛП называется задача, в которой опред. экстремум целевой функции при выполнении условия 1 только ву одну сторону и условия 2 для всех переменных.

Каноническая задача ЛП называется задача, в которой:

1. функция цели исследуется на максимум и минимум

2. ограничение задач только типа равенство

3. все переменные неотрицательны

4. все элементы правых частей положительны

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

План х^* при котором целевая функция достигает максимума, называется оптимальным => решение состоит в нахождении хотя бы одного оптимального плана.

Различные формы записи задачи ЛП:

1. векторная форма

=(x₁ , … , x_n )

=(x₁ , … , x_n )

Тогда векторная запись будет состоять в следующем:

Z=Cx→max

A₁ x₁ +…+A_n x_n <b x>0

2. матричная форма записи

Где А – матрица условий; Сх – скалярное произведение векторов; Ах – умножение матрицы на вектор.

Элементы выпуклого анализа.

Линейная комбинация векторов называется выпуклой, если выполняется условие

В двумерном случае линейная комбинация векторов есть отрезок, соединяющий эти точки.

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

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

Угловая точка многогранника решений – это точка, которая не является выпуклой комбинацией никаких других точек данного многогранника.

Если система ограничений содержи конечное число неравенств и имеется хотя бы одно допустимое решение, то угловых точек всегда конечно и не более чем число сочетаний из n элементов по m.

Угловые точки многогранника – вершины, а полуплоскости, проходящие хотя бы через 2 вершины называются гранями.

Вершины называются соседними, если существует грань их соединяющая.

Теорема № 1:

1. множество решений задач ЛП, если оно не пусто, - есть выпуклый многогранник.

2. целевая функция задач ЛП достигает своего максимума з

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать