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

Лекция 1, 2

Математическое программирование. Понятие об оптимизационных задачах. Задача линейного программирования (ЗЛП). Графический метод решения ЗЛП

Вопросы:

1. Предмет — математическое программирование, краткая классификация методов.

2. Основные понятия теории оптимизации.

3. Постановка ЗЛП, различные формы записи. Примеры экономических задач.

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

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

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

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

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

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

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

в технике — управление размерами и оптимизация структур, оптимальное планирование сложных технических систем, как информационные системы, сети компьютеров, транспортные и телекоммуникационные сети и др.;

в автоматике — распознавание систем и объектов, оптимальное управление системами, фильтрация, роботы, автоматизированные линии и т. п.;

в медицине, политике, социологии и т. п., и т. д.

Дадим ряд определений.

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

Экономические возможности формализуются в виде системы ограничений.

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

совокупность неизвестных величин х = (х₁, х₂, …, х_n), действуя на которые систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, стратегией, поведением и т. п.);

целевую функцию, которая позволяет выбрать наилучший вариант из множества возможных. Целевая функция обозначается F (x). Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности и т. д.;

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

Т.о., модель задачи математического программирования примет вид:

Найти план х = (х₁, х₂, …, х_n), доставляющий экстремальное значение целевой функции F(x) > max(min), при ограничениях g_i(x)? (=, ?) b_i, i=.

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

План х, удовлетворяющий системе ограничений задачи, называют допустимым. Допустимый план, доставляющий целевой функции экстремальное значение, называют оптимальным. Оптимальный план обозначают х*, экстремальное значение функции F (x*) = F*.

В зависимости от особенностей целевой функции F (x) и функций ограничений g_i(x), задачи математического программирования делятся на ряд типов.

Задача линейного программирования (ЗЛП) — задача оптимизации линейной функции при линейных ограничениях.

Задача нелинейного программирования (ЗНП) — задача оптимизации нелинейной функции при ограничениях или без них (когда или F (x) и/или g_i(x) нелинейны).

Задача дискретного (в частности целочисленного) программирования — Задача оптимизации, в которой на переменные наложено дополнительное требование принимать лишь дискретные (в частности целочисленные) значения.

Задача динамического программирования — задача оптимизации динамических систем (т.е. развивающихся с течением времени).

Задача вероятностного или стохастического программирования — задача оптимизации, содержащая случайные величины.

Основные понятия теории оптимизации

Говорят, что функция F (x) имеет в т. х*(х₁, х₂, …, х_n) локальный максимум (минимум), если существует такая окрестность т. х*, в которой для любого х выполняется неравенство F (x)? F (x*) (F (x)? F (x*)).

Необходимое условие экстремума: чтобы F (x) имела в т. х* экстремум необходимо, чтобы? F (x*)/?x_j = 0, .

Достаточное условие экстремума: если F (x) в т. х* имеет? F (x*)/?x_j = 0,, то чтобы в этой точке F (x) имела экстремум достаточно, чтобы квадратичная форма

была положительно (минимум) или отрицательно (максимум) определена.

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

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

Функция F(x), определенная на выпуклом множестве S, выпукла, если ее график целиком лежит ниже (не выше) отрезка, соединяющего любые две точки графика:

Функция F(x), определенная на выпуклом множестве S, вогнута, если ее график целиком лежит выше (не ниже) отрезка, соединяющего любые две точки графика:

Теорема 1: пересечение выпуклых множеств является выпуклым множеством.

Теорема 2: сумма выпуклых функций является выпуклой функцией, сумма вогнутых функций — вогнутой функцией.

Теорема 3 (основное свойство выпуклых задач):

Всякий локальный оптимум является глобальным.

Теорема Вейерштрасса:

Непрерывная функция, определенная на непустом замкнутом ограниченном множестве, достигает максимума (минимума) по крайней мере в одной точке этого множества.

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

При численных расчетах часто необходимо использовать еще два важных понятия.

Вектор, указывающий направление наискорейшего возрастания функции, называется градиентом функции grad F(x) = (?F/?x₁, … ,?F/?x_n). Противоположный ему вектор называют антиградиентом, он указывает направление наискорейшего убывания функции.

Линией уровня (или линией равного значения) функции F(x) называют геометрическое место точек, координаты которых удовлетворяют уравнению F(x) = Const. Линия уровня и вектор градиент в каждой точке взаимно перпендикулярны.

Постановка ЗЛП, различные формы записи. Примеры экономических задач

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

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

Рассмотрим постановку ЗЛП на примере задачи и наилучшем использовании ресурсов. Имеется m видов ресурсов в ограниченном количестве b = (b₁, b₂, …, b_m). Ресурсы используются предприятием для выпуска n видов продукции. Известна экономическая выгода производства каждого вида продукции, исчисляемая, например, ценой реализации С = (С₁, С₂, …, С_n). Известны технологические коэффициенты а_ij, соответствующие количеству i-го вида ресурса, необходимого для производства единицы jго вида продукции — А = (а_ij). Необходимо составить план производства х = (х₁, х₂, …, х_n), приносящий предприятию максимальную прибыль.

В общем виде математическую модель задачи (ЗЛП) можно записать следующим образом:

F (x) = C₁x₁ + C₂x₂ + … + C_nx_n > max

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n? b₁, x_j? 0, j=

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n? b₂,

… … … …

a_m1x₁ + a_m2x₂ + … + a_mnx_n? b_m.

Рассмотрим задачу о диете. Необходимо составить диету (рацион), содержащую определенные питательные вещества. Имеем n видов продуктов, каждый из которых сожержит необходимые m видов питательных веществ. Единица j-го продукта содержит а_ij единиц i-го питательного вещества. Для нормальной жизнедеятельности необходимо не менее b_i единиц i-го вещества. Известна стоимость единицы каждого вида продукта С = (С₁, С₂, …, С_n). Необходимо составить диету минимальной стоимости.

Математическая модель задачи примет вид:

F (x) = C₁x₁ + C₂x₂ + … + C_nx_n > min

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n? b₁, x_j? 0, j=

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n? b₂,

… … … …

a_m1x₁ + a_m2x₂ + … + a_mnx_n? b_m.

Здесь х_j — количество j — го продукта в рационе.

В матричной форме общая ЗЛП выглядит так:

F (x) = C^Tx > max (min)

Ax? (=,?) B; x? 0.

Кроме того, для записи ЗЛП можно использовать знак суммы:

F (x) = > max (min)

.

Рассмотрим задачу о размещении заказа. Имеется m однородных групп оборудования, на котором нужно выполнить заказ на выпуск n видов продукции в объемах х*_j,. Мощность оборудования ограничена, например, временем Т_i. Производительность оборудования задана коэффициентами а_ij. Известны коэффициенты затрат С_ij — затраты i — го оборудования на производство j — го продукта. Построить план х_ij размещения заказа (загрузки оборудования). Составим математическую модель задачи.

F (x) = > min, x_ij? 0, j=, ,

— по мощности —, ,

— по видам продукции, план по которой может быть перевыполнен

j= ,

— по видам продукции, план по которой должен соответствовать заказу

j= ,

— по видам продукции, заказ на которую принимается для более полной загрузки

оборудования

j= .

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

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

Схема решения.

Строим область допустимых решений.

Строим линию уровня.

Определяем направление градиента.

Определяем точку максимума (минимума):

Точка максимума — точка допустимой области, наиболее удаленная от линии уровня в направлении градиента, точка минимума — точка допустимой области, наиболее удаленная от линии уровня в направлении антиградиента.

При решении ЗЛП возможны следующие случаи:

Основные свойства ЗЛП (см. рис.).

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

Оптимальное решение достигается по крайней мере в одной из вершин допустимой области: а) только в одной вершине; б) в двух вершинах и имеет бесконечное множество планов.

Если допустимая область не ограничена, то ЗЛП может быть разрешима или не разрешима, что зависит от целевой функции: в) задача на max не разрешима, а на min — разрешима; г) ЗЛП не разрешима.

Если допустимая область состоит из единственной точки, то в ней достигается и максимум и минимум — д).

Если допустимая область пуста, то ЗЛП не разрешима — е).

Если допустимая область ограничена и не пуста, то ЗЛП всегда имеет решение.

Лекция 3

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

Вопросы:

1. Стандартная форма ЗЛП, правила построения.

2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса.

3. Симплекс-метод.

1. Стандартная форма ЗЛП, правила построения

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

Стандартная форма ЗЛП представляет собой такой вид задачи, в котором:

1) все переменные неотрицательны;

2) все ограничения заданы в виде уравнений;

3) целевая функция сформулирована на минимум.

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

Правила построения стандартной формы ЗЛП:

1) Если F (x) = C₁x₁ + C₂x₂ + … + C_nx_n max, то можно искать

F (x) = - C₁x₁ — C₂x₂ — … — C_nx_n min.

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

Например: 2х₁ + 3х₂ 4 2х₁ + 3х₂ + х₃ = 4, х₃ — уравновешивающая переменная.

4x₁ + 2x₂ 5 4x₁ + 2x₂ — x₄ = 5, x₄ — уравновешивающая переменная.

3) Если некоторая переменная х может быть не ограничена знаком, то в стандартном виде такую переменную можно представить в виде разности двух неотрицательных переменных: x = x' - x'', x', x'' .

При этом дополнительные переменные не входят в целевую функцию. Стандартная форма ЗЛП в матричном виде выглядит так: Ax = b, x, F (x) = C^Tx min.

2. Канонический вид ЗЛП, начальное допустимое базисное решение (НДБР), метод искусственного базиса

Чтобы ЗЛП имела решение необходимо, чтобы система ограничений была совместна. Это возможно, если ранг m системы (число линейно независимых уравнений) был не больше числа неизвестных n. Случай m > n невозможен. При m = n система имеет единственное решение, которое определяется методами обычной алгебры. Если m < n, то система имеет m линейно независимых векторов — базис, через которые любой вектор системы может быть выражен как линейная комбинация. Таких базисов может быть несколько, но не больше, чем С_n^m. Переменные ЗЛП, соответствующие m векторам базиса, являются базисными, остальные переменные — свободные.

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

Переменные, входящие в базис, называют базисными (б.п.), остальные n - m переменных называют свободными.

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

Допустимым базисным решением (ДБР) является такое, при котором все переменные неотрицательны. В противном случае базисное решение недопустимо.

Частное допустимое базисное решение, с которого начинают решение, называют начальным допустимым базисным решением (НДБР).

Чтобы найти НДБР, удобно ЗЛП записать в каноническом виде.

Канонический вид ЗЛП — это такой стандартный вид, в котором в каждом i-ом уравнении найдется такая переменная х_I, что коэффициент перед ней в данном уравнении равен +1, а в других уравнениях и в выражении целевой функции эти коэффициенты равны нулю. Если при этом все b, то говорят о допустимом каноническом виде, в противном случае — о недопустимом.

Например.

1 Случай. Исходная задача ЗЛП содержит все ограничения со знаком .

, ,

F (x) = .

Стандартная форма ЗЛП является одновременно и каноническим допустимым видом.

, ,

 — дополнительные, уравновешивающие переменные

F (x) = - .

При этом х_j = 0, — свободные переменные, х_n+I = b_i, — - базисные переменные — НДБР.

2 Случай. Ограничения исходной ЗЛП содержат неравенства разных знаков и уравнения.

, ,

, ,

F (x) = .

Стандартная форма ЗЛП не совпадает с каноническим видом.

,

,

,

 — дополнительные, уравновешивающие переменные.

F (x) = - .

Чтобы построить канонический вид и получить НДБР используют метод искусственного базиса. В каждое уравнение, не содержащее переменную, создающую канонический вид, вводят искусственную неотрицательную переменную.

,

, ,

, ,

F (x) = - .

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

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

G (x) = или G (x) = .

Оптимальное решение вспомогательной задачи соответствует НДБР исходной задачи.

3. Симплекс-метод

При решении ЗЛП симплекс-методом удобно представить задачу в табличном виде.

ПРИЗНАК ОПТИМАЛЬНОСТИ. План х* = (х₁, х₂, …, х_n) считается оптимальным, если все коэффициенты целевой функции неотрицательны, С_j 0,. Тогда значение F_max равно значению, стоящему в правом нижнем углу таблицы.

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

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

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

Элемент, стоящий на пересечении разрешающих строки и столбца, называется разрешающим и отмечается .

Производится замена базисного допустимого решения на другое, при этом таблица будет иметь следующее содержание:

а) свободная переменная х_j*, стоящая в разрешающем столбце, становится базисной, а

базисная переменная х_ai*, стоящая в разрешающей строке, — свободной;

б) все элементы разрешающей строки в новой таблице имеют значения

(штрихом отмечены новые значения);

в) все остальные элементы таблицы определяются по формулам:

(ii*), (ii*),

(ii*), .

Каждая новая таблица проверяется на оптимальность. Операции 1)-4) осуществляются до тех пор, пока не будет получено оптимальное значение целевой функции.

Лекция 4, 5

Устойчивость решений ЗЛП при небольших изменениях условий. Двойственный симплекс-метод

Вопросы:

1. Обращенный базис, симплекс — множители.

2. Изменение значений правых частей ограничений.

3. Изменение значений коэффициентов целевой функции.

4. Включение дополнительных переменных.

5. Включение дополнительных ограничений.

6. Двойственный симплекс-метод.

7. Проблемы вырождения, зацикливания.

1. Обращенный базис, симплекс — множители

Рассмотрим решение ЗЛП симплекс-методом с точки зрения алгебры. В матричном виде стандартная форма ЗЛП имеет вид:, Ах = b, где А_mxn. Представим матрицу, А в виде «склеенных» двух матриц, А = В_mxm R_mx(n-m). Здесь В_mxm — матрица, состоящая из столбцов матрицы А, соответствующих переменным, которые в оптимальной таблице являются базисными. Матрица R_mx(n-m) состоит из всех оставшихся столбцов. Предположим известна матрица В^-1. Умножим слева ограничения ЗЛП на В^-1:

В^-1(ВR)x = B^-1b, здесь х = (х_б.п., х_св.п.) (Е_mB^-1R)x = B^-1b x_б.п. = B^-1b, х_св.п. = 0.

В НДБР базисным переменным соответствует единичная матрица, то есть, А = С_n-mE_m. Так как, А умножается на В^-1, то В^-1А = В^-1(С_n-mE_m) = В^-1 С В^-1, что соответствует матрице коэффициентов оптимальной таблицы. Следовательно, в оптимальной таблице в столбцах тех переменных, которые были базисными в НДБР, находится матрица В^-1.

Матрица В^-1 называется обращенный базис. В оптимальной таблице В^-1 находится среди коэффициентов ограничений, стоящих в столбцах тех переменных, которые были базисными в исходной таблице.

Запишем теперь канонический вид задачи.

x_n+I, I = - уравновешивающие переменные.

С₁х₁ +…+ С_nx_n = F (x)

Умножим каждое ограничение на некоторое число, соответственно и сложим с выражением целевой функции, получим х₁(С₁ +) + … + х_n(C_n +) + + … + = F (x) +

. (1)

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

.

Если предположить, что подобрали таким образом, что перед базисными переменными коэффициенты равны нулю, а перед свободными — неотрицательны, то вид (1) будет соответствовать оптимальному виду таблицы. Следовательно, в оптимальной таблице коэффициенты в выражении целевой функции перед переменными, которые были базисными в исходной таблице, есть. Это и есть симплекс — множители. При этом,

.

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

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

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

Пример.

2. Изменение значений правых частей ограничений

Правые части ограничений выражают ограниченные объемы ресурсов или минимальные нормы потребления и т. п. Предположим правые части ограничений изменились на. Другими словами, встает задача найти новый оптимальный план, при b' = b +. Можно ли использовать результаты уже решенной задачи? Если задача была решена для прежнего значения b, то известными являются обращенный базис В^-1 и симплекс — множители. При этом при определении В^-1 и значения b никак не учитывались, эти значения влияют лишь на оптимальное значение целевой функции. Следовательно, новые значения целевой функции и переменных можно получить по формулам

F'(x) = ;

Замечание. Указанный прием можно использовать лишь при небольших изменениях в b, то есть базисное решение должно остаться допустимым (неотрицательным). Таким образом, если для базисных переменных получено хотя бы одно отрицательное значение, то решение задачи можно продолжить двойственным симплекс-методом.

Пример.

3. Изменение значений коэффициентов целевой функции

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

C_j' = C_j +, а изменений в b не произошло, то и оптимальный план не изменится, а изменятся лишь оптимальные значения целевой функции и ее коэффициентов. В исходной таблице целевая функция имеет вид

F (x) = -C₁x₁ — C₂x₂ — … — C_nx_n

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

Умножим все уравнения системы соответственно на С₁, С₂, …, С_n и сложим с выражением целевой функции исходной таблицы в общем виде. Получим

0х₁ + … +0х_m + = F'(x) +

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

— если для С_j' коэффициента целевой функции окажутся неотрицательными, то найденное решение сохранится, то есть если,, то решение не изменится х_б' = х_б, F'(x) = - .

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

Пример.

4. Включение дополнительных переменных

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

Пусть объем нового вида продукции х_n+1, технологические коэффициенты известны

Р = (_1(n+1), _2(n+1), …, _m(n+1))^T, предполагаемая прибыль от реализации единицы продукции С_n+1. Все остальные условия остаются прежними. Чтобы учесть эти изменения, не решая задачу с самого начала, необходимо дополнительные данные записать в оптимальную таблицу. Новая «исходная» матрица коэффициентов A' = A P, чтобы привести ее к виду оптимальной таблицы, необходимо умножить ее на В^-1. Таким образом, в оптимальной таблице добавляется еще один столбец Р* = В^-1Р. При этом свободные члены не изменяются. Осталось записать коэффициент целевой функции, это можно сделать с помощью симплекс — множителей. Умножим коэффициенты Р на соответствующие симплекс — множители и прибавим к коэффициенту целевой функции в стандартном виде:

— C_n+1 + = C_n+1*.

Если C_n+1*, то х_n+1 останется свободной (то есть равной нулю), так как сохранится признак оптимальности. Следовательно, план менять не стоит.

Если C_n+1* < 0, то следует улучшить решение, а именно х_n+1 ввести в базисные переменные. Следовательно, план изменится. При этом решение продолжается обычным симплекс-методом.

Пример.

5. Включение дополнительных ограничений

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

Итак, пусть — новое дополнительное ограничение к уже решенной задаче. То есть х* уже найдено.

Если найденное х* = (х₁, х₂, …, х_n) удовлетворяет поставленному дополнительному ограничению, то план никак не изменится (ограничение не ограничивает данное производство).

Если х* = (х₁, х₂, …, х_n) не удовлетворяет новому ограничению, то необходимо изменить план, то есть продолжить решение.

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

Пример.

6. Двойственный симплекс-метод

Для решения задачи двойственным симплекс-методом она должна иметь недопустимый канонический вид. И признак оптимальности должен выполняться.

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

Правила.

1. Недопустимый канонический вид ограничений и оптимальный вид (С_j) целевой функции записывают в исходную таблицу.

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

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

Замечание: 1. Обычный симплекс-метод при сохранении допустимости решения переходит последовательно к оптимальному решению. А двойственный симплекс-метод при сохранении оптимальности переходит последовательно от недопустимого решения к допустимому.

2. Правила двойственного симплекс-метода отличаются от правил обычного выбором разрешающих столбца и строки.

3. Если в разрешающей строке (для двойственного метода) нет ни одного отрицательного элемента, то задача не разрешима.

7. Проблемы вырождения, зацикливания

Как правило, все базисные переменные отличны от нуля (то есть в симплекс-таблице все свободные члены). Однако, нет никаких ограничений к тому, чтобы одна или несколько базисных переменных обратились в ноль.

Базисное решение (базис) является невырожденным, если оно содержит ровно m отличных от нуля компонент. В противном случае — вырожденным.

Если начальный план задачи невырожден, то никаких сложностей при решении не возникает, при правильном выборе разрешающего элемента. Если хотя бы одна базисная переменная в НДБР приняла нулевое значение, то по правилам симплекс-метода именно она должна будет войти в базис на следующем шаге, так как min b_i/a_ij* = 0. При этом значение целевой функции не изменится.

Лекция 6.

Двойственность в линейном программировании

Вопросы:

1. Понятия двойственности, теневой цены, двойственной оценки.

2. Правила построения двойственной задачи.

3. Основные теоремы двойственности и их экономическое содержание.

1. Понятия двойственности, теневой цены, двойственной задачи

Двойственность является одним из фундаментальных понятий в линейном программировании, приводящим к важному результату теоретического и практического характера. Рассмотрим понятие двойственности на примере задачи оптимального использования ресурсов.

На производство n видов продукции предприятие затрачивает m видов ресурсов, имеющихся в ограниченных количествах b = (b₁, b₂, …, b_m). На производство единицы j-го вида продукции требуется a_ij единиц i-го вида ресурса. Прибыль от реализации единицы продукции С_j, j =. Необходимо определить такой план производства х = (х₁, х₂,…, х_n), при котором прибыль предприятия была бы максимальной. Математическая модель задачи выглядит следующим образом.

С₁х₁ + … + С_nx_n =F (x) m ax, x_j 0, j = .

В общем случае задача решается симплекс-методом. Что ограничивает производство? Зададимся вопросом, какова с точки зрения предприятия ценность имеющихся в его распоряжении ресурсов? При решении этого вопроса будем иметь в виду, что ресурсы, которые предприятие не может полностью использовать, имеют для него очень низкую ценность, в том смысле, что предприятие не согласно нести даже небольшие расходы на увеличение запасов этих ресурсов. Дорогое оборудование, не участвующее в технологическом процессе, составляет для предприятия нулевую ценность.

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

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

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

В экономической литературе «теневые» цены часто называют объективно-обусловленными или оптимальными оценками, двойственными или учетными, неявными оценками.

Чтобы определить оптимальные «теневые» цены ресурсов необходимо составить и решить задачу оптимизации. Имеем те же исходные данные, что и для задачи оптимального использования ресурсов. Только теперь необходимо найти такие «теневые» цены ресурсов y = (y₁, y₂,…, y_m), при которых стоимость всех ресурсов была бы минимальна, y_i — «теневая» цена единицы i-го ресурса, y_i 0.

«Теневые» цены y = (y₁, y₂,… ,y_m) должны быть такими, чтобы «теневая» цена всех ресурсов, затраченных на производство единицы продукции каждого вида, была бы не меньше получаемого от ее реализации дохода. Другими словами, стоимость затраченных ресурсов не может быть меньше стоимости окончательного продукта (так как существуют неизбежные издержки):

.

Оптимальными «теневыми» ценами естественно считать такие, которые минимизируют общую стоимость ресурсов.

.

Запишем обе задачи в матричном виде:

Прямая задача Двойственная задача

Ах А^Тy C

F = C^Tx Z =

x 0 y 0

Эти задачи называют парой двойственных задач. Пара двойственных задач может быть экономически интерпретирована следующим образом.

Прямая задача: Сколько и какой продукции x_j необходимо производить, чтобы при заданных стоимостях C_j и размерах ресурсов b_i максимизировать выпуск продукции в стоимостном выражении?

Двойственная задача: Какова должна быть цена каждого ресурса y_i, чтобы при заданных количествах b_i и стоимостях C_j минимизировать затраты?

2. Правила построения двойственной задачи

Исходя из общего вида прямой и двойственной задач можно установить связь между этими задачами, позволяющую для любой ЗЛП строить двойственную ей задачу.

Свойства двойственных задач (правила).

1. Число неизвестных двойственной задачи равно числу ограничений прямой задачи. Число ограничений двойственной задачи равно числу неизвестных прямой задачи.

2. Матрица коэффициентов двойственной задачи является транспонированной матрицей коэффициентов прямой задачи.

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

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

5. Если ограничения прямой задачи записаны со знаком меньше или равно (), то ограничения двойственной задачи записываются со знаком больше или равно ().

6. Если ограничение прямой задачи задано в виде уравнения, то соответствующее неизвестное двойственной задачи не ограничено знаком.

7. Если какое-либо неизвестное прямой задачи не ограничено знаком, то соответствующее ограничение двойственной задачи будет задано в виде равенства.

8. Если целевая функция прямой задачи сформулирована на максимум, то целевая функция двойственной задачи будет сформулирована на минимум.

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

1) все ограничения имеют знак ;

2) целевая функция сформулирована на максимум;

3) все неизвестные неотрицательны.

Чтобы записать прямую задачу в стандартном виде, необходимо:

1) неравенство со знаком умножить на (-1);

2) равенство заменить на два неравенства противоположных знаков, одно из которых следует умножить на (-1);

3) формулировку целевой функции меняют заменой знаков коэффициентов на противоположные;

4) если переменное x_j не ограничено знаком, его можно представить в виде разности двух неотрицательных переменных.

Пример. Составить двойственную задачу к исходной.

.

Решение. 1) Стандартный вид прямой задачи.

2) Двойственная задача:

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

.

3. Основные теоремы двойственности и их экономическое содержание

Теорема 1. Двойственная задача к двойственной есть прямая задача.

Доказательство: Пусть имеем пару двойственных задач в матричном виде.

Ах А^Тy C

F = C^Tx Z =

x 0 y 0

Построим к двойственной задаче двойственную:

1) запишем в стандартном видеА^ТyC

Z = ;

2) -Ах Ах

F = - C^Tx F = C^Tx

Что и требовалось доказать.

Теорема 2. Значение функции F, соответствующее любому допустимому решению прямой задачи, не больше значения функции Z, соответствующего любому допустимому решению двойственной задачи.

Доказательство: Пусть X и Y соответственно произвольные допустимые решения прямой и двойственной задач. Следовательно,

1) Ах и Y Y^Т, Y^TAX Y^Tb = b^TY = Z.

2) A^TY C и X 0 X^Т, X^TA^TY X^TC = C^TX = F.

3) выражение X^TA^TY — скалярная величина (число) она равна своей

транспозиции, т. е. X^TA^TY = Y^TAX. Итак, имеем,

F X^TA^TY = Y^TAX Z F Z. Что и требовалось доказать.

Следствия: 1) если в прямой задаче допустимая область не пуста, а целевая функция не ограничена сверху, то у двойственной задачи допустимая область пуста;

2) если в двойственной задаче допустимая область не пуста, а целевая функция не ограничена снизу, то у прямой задачи допустимая область пуста.

Теорема 3. Если прямая задача имеет конечное оптимальное решение F = F_max, то двойственная задача имеет конечное оптимальное решение Z = Z_min. При этом F_max = Z_min, а симплекс-множители оптимального решения прямой задачи являются значениями переменных в оптимальном решении двойственной задачи.

Доказательство: Запишем прямую задачу

Ах, x 0, b, F = C^Tx .

Запишем задачу в стандартном виде Ах + х^Р = b, где х^Р = (х₁,…, х_n+m) — дополнительные, уравновешивающие переменные, ^Т— симплекс-множители оптимального решения. Известно, что прямая задача разрешима, следовательно, можно определить значения симплекс-множителей оптимального решения. Получим оптимальное выражение целевой функции, то есть

(-С^T+)x+= F + b^T. (*)

Так как это оптимальный вид целевой функции, то все коэффициенты

неотрицательны.

или .

Т.о., если y =, то ограничения двойственной задачи выполняются.

Так как (*) — оптимальный вид целевой функции, то коэффициенты перед базисными переменными равны нулю, а свободные переменные сами равны нулю F_min = -b^T или F_max = b^T. Если y =, то это и есть целевая функция двойственной задачи, то есть Z = F_max = Z_min. Что и требовалось доказать.

Теорема 4. Если двойственная задача имеет конечное оптимальное решение Z = Z_min, то прямая задача имеет конечное оптимальное решение F = F_max. При этом Z_min = F_max , а значения симплекс-множителей оптимального решения двойственной задачи являются значениями переменных в оптимальном решении прямой задачи с противоположными знаками (если обе задачи решаются прямым симплекс-методом).

Доказательство: В матричной форме двойственная задача имеет вид.

А^Тy C, y 0, С 0, Z =

1) Запишем в стандартном виде A^Ty — y^S = C, где y^S= (y_m+1,…, y_m+n)^T 0 — дополнительные, уравновешивающие переменные, — симплекс-множители оптимального решения двойственной задачи. Для двойственной задачи имеют то же значение, то есть

(b^T + = Z +. (**)

Так как это оптимальный вид целевой функции Z, то все коэффициенты неотрицательны.

или .

Таким образом, если, то ограничения прямой задачи удовлетворяются, значит это решение.

2) Так как (**) — оптимальное решение для целевой функции, то коэффициенты перед базисными переменными равны нулю, а свободные переменные сами равны нулю. Следовательно,

Z_min = -, а это есть целевая функция прямой задачи, если. Что и требовалось доказать.

Экономическое содержание теорем состоит в следующем: если задача оптимизации плана, максимизирующего выпуск продукции, разрешима, то разрешима и задача определения оценок ресурсов. План производства и оценки ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Так как F Z, Z — F = - издержки производства, которые равны нулю когда F^* = Z^*.

Двойственные оценки обладают тем свойством, что они гарантируют рентабельность оптимального плана, то есть равенство общей оценки продукции и ресурсов, и обуславливают убыточность всякого другого плана, отличного от оптимального.

Кроме того, если y_i > 0, то при оптимальной производственной программе этот ресурс используется полностью; если y_i = 0, то ресурс используется не полностью.

Лекция 7, 8

Элементы теории игр и принятия решений

Вопросы:

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

2. Теоремы теории игр.

3. Способы решения задач теории игр.

4. Методы принятия решений: в условиях определенности; в условиях риска; в условиях неопределенности.

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

Теория игр принадлежит к наиболее молодым математическим дисциплинам, её возникновение относится к концу II-й Мировой войны.

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

Ситуация называется конфликтной, если в ней сталкиваются интересы нескольких лиц, преследующих противоположные цели.

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

Упрощенная, формализованная модель конфликтной ситуации, называется игрой, а конфликтующие 7стороны — игроками.

Игра представляет собой совокупность правил, описывающих поведение игроков.

Допустимые действия любого из игроков в игре называются правилами игры.

Каждый случай разыгрывания игры некоторым конкретным образом от начала и до конца представляет собой партию игры. Элементами игры являются ходы. Правила игры предусматривают, какова должна быть последовательность ходов, и указывают характер каждого хода. Ходы бывают личными и случайными.

Личный ход представляет собой выбор игроком одного из данного множества вариантов.

Например, в шахматах каждый ход — личный, причем 1-й — выбор из 20 вариантов. Решение, принятое игроком при личном ходе, называется выбором.

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

Например, сдача карт, бросание монеты и т. п. Выбор при случайном ходе называется исходом хода.

Исходом игры является выигрыш или проигрыш. Величина этого выигрыша или проигрыша называется ценой игры.

Для личного хода правила игры перечисляют все возможные варианты выбора и определяют какой игрок его делает. Для случайного хода — указывают варианты и вероятности их выбора.

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