Теория игр и программирование

Содержание

Ведение
Глава 1. Теория линейного  программирования
§1. Задача линейного програмирования и свойства ее решений
п. 1.1. Понятие линейного програмирования
п. 1.2. Свойства решений
§2. Графический способ  решения задачи линейного программирования
§3. Симплексный метод
§4. Метод искусственного  базиса
§5. Понятие двойственности
Глава 2. Создание модели линейного программирования
§6. Постановка задачи
§7. Математическое решение
§8. Оценка полученных результатов и выводы

                                                                                                            

 

 

 

 

 

Введение.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§1.Задача линейного  программирования  и  свойства ее решений.

 

1.1 Понятие  линейного программирования.

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

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

 

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

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

  (1)

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

  (2)

  (3)

       (4)

     (5)

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

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

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

 

1.2 Свойства решений.

Пусть ЗПЛ представлена в следующей  записи:

          (7)

     (8)

                     (9)

Чтобы задача (7) – (8) имела  решение, системе её ограничений (8) должна быть совместной. Это возможно, если  r этой системы не больше числа неизвестных n. Случай r>n вообще невозможен. При r= n система имеет единственное решение, которое будет при оптимальным. В этом случае проблема выбора оптимального решения теряет смысл. Выясним структуру координат угловой точки многогранных решений. Пусть r<n. В этом случае система векторов содержит базис — максимальную линейно независимую подсистему векторов, через которую любой вектор системы может быть выражен как ее линейная комбинация. Базисов, вообще говоря, может быть несколько, но не более . Каждый из них состоит точно из r векторов. Переменные ЗЛП, соответствующие r векторам базиса, называют, как известно, базисными и обозначают БП. Остальные n – r переменных будут свободными, их обозначают СП. Не ограничивая общности, будем считать, что базис составляют первые m векторов . Этому базису соответствуют базисные переменные , а свободными будут переменные .

Если свободные переменные приравнять нулю, а базисные переменные при этом примут неотрицательные значения, то полученное частное решение системы (8) называют опорным решением (планом).

 

Теорема. Если система векторов содержит m линейно независимых векторов , то допустимый план    (10) является крайней точкой многогранника планов.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§2.Графический способ решения  ЗЛП.

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

Пусть дана задача

           (11)

         (12)

                         (13)

Дадим геометрическую интерпретацию  элементов этой задачи. Каждое из ограничений (12), (13) задает на плоскости некоторую полуплоскость. Полуплоскость — выпуклое множество. Но пересечение любого числа выпуклых множеств является выпуклым множеством. Отсюда следует, что область допустимых решений задачи (11) — (13)  есть выпуклое множество.

Перейдем к геометрической интерпретации  целевой функции. Пусть область  допустимых решений ЗЛП — непустое множество, например многоугольник .

 

 Выберем произвольное значение  целевой функции . Получим . Это уравнение прямой  линии. В точках прямой NМ целевая функция сохраняет одно и то же постоянное значение . Считая в равенстве (11) параметром, получим уравнение семейства параллельных прямых, называемых линиями уровня целевой функции (линиями постоянного значения).

Найдём частные производные  целевой функции по и

           (14)

           (15)

Частная производная (14)  ((15)) функции показывает скорость ее возрастания вдоль данной оси. Следовательно, и — скорости возрастания соответственно вдоль осей и . Вектор называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции:

Вектор —   указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом.

Вектор  перпендикулярен к прямым семейства

Из геометрической интерпретации  элементов ЗЛП вытекает следующий порядок ее графического решения.

1. С учетом системы ограничений строим область допустимых решений
2. Строим вектор наискорейшего возрастания целевой функции — вектор градиентного направления.
3. Проводим произвольную линию уровня 
4. При решении задачи на максимум перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в ее крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня перемещают в антиградиентном направлении
5. Определяем оптимальный план и экстремальное значение целевой функции .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

§3.Симплексный  метод.

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

Для использования симплексного метода ЗЛП должна быть приведена  к каноническому виду, т.е. система  ограничений должна быть представлена в виде уравнений.

Оптимизационные исследования ЗЛП удобно проводить, пользуясь  симплекс-таблицами. Существует достаточно большое количество форм симплекс-таблиц. Воспользуемся одной из форм, по которой рекомендуется следующий  порядок решения ЗЛП:

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

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

3. Составляется исходная симплекс-таблица (таблица 1), в которую записывают параметры, соответствующие начальному базисному допустимому решению:

3.1. Весовые коэффициенты c_j при переменных x_j  (j = 1,...,n) целевой функции (строка C).

3.2. Весовые коэффициенты c_i при базисных переменных x_i (i = 1,...,m) целевой функции (столбец C_b).

3.3. Переменные x_i (i = 1, ... ,m) , которые входят в текущий базис (столбец A_b ).

3.4. Свободные коэффициенты  b_i (i =1, ... ,m) уравнений ограничений (столбец B). В этом же столбце находим оптимальный план задачи.

3.5. Элементы a _ij (i = 1, ... ,m ; j = 1, ... ,n) матрицы условий задачи (столбцы A₁, .., A_n ).

 

Таблица 1

Аб	Сб	В	c1	...	cj	...	ck	...	cn
			A1	...	Aj	...	Ak	...	An
А1	c1	b1	a11	...	a1j	...	a1k	...	a1n
…	...	...	...	...	...	...	...	...	...
Аi	ci	bi	ai1	...	aij	...	aik	...	ain
…	...	...	...	...	...	...	...	...	...
Ar	cr	br	ar1	...	arj	...	ark	...	arn
…	...	...	...	...	...	...	...	...	...
Am	cm	bm	am1	...	amj	...	amk	...	amn
m+1		S	S1	...	Sj	...	Sk	...	Sn

 

3.6. Оценки  S_j   (j=1, ... ,n)  векторов условий A_j , которые определяются по формуле:

 

где c_i - весовые коэффициенты при базисных переменных.

Из этой формулы следует, что  коэффициенты z_j вычисляются для каждого столбца как сумма почленных произведений коэффициентов c_i на одноименные коэффициенты j-го столбца. При заполнении симплекс-таблицы при условии, что рассматривается задача максимизации целевой функции, необходимо иметь в виду:

• если S_j ³ 0 для всех j = 1, ..., n, то полученное решение является оптимальным;
• если имеются  S_j < 0 и в столбцах A_j, соответствующих этим отрицательным оценкам, существует хотя бы один элемент a_ij > 0, то возможен переход к новому решению, связанному с большим значением целевой функции;
• Из отрицательных оценок выбирают ту, у которой значение по абсолютной величине больше. Если имеется несколько одинаковых отрицательных оценок, то выбирают ту, которой соответствует максимальный коэффициент целевой функции c_i.
• если имеются S_k<0 и в столбце A_k все элементы a_ik £ 0, то в области допустимых решений целевая функция не ограничена сверху.