Размещено на http://www.allbest.ru/

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

(Лекции)

Галкина М.Ю.

2011



Содержание

Введение

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

1.1 Различные формы записи задачи линейного программирования

1.2 Графический метод решения задачи линейного программирования

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

1.4 Использование надстройки Поиск решения MS Excel

1.5 Решение ЗЛП средствами MS Excel

1.6 Двойственные задачи

Вопросы для самопроверки

2. Специальные задачи линейного программирования

2.1 Задача о назначениях

2.2 Теория игр

2.2.1 Основные понятия

2.2.2 Нижняя и верхняя цены игры. Принцип минимакса

2.2.3 Решение игр в смешанных стратегиях

2.2.4 Решение матричных игр 2х2 в смешанных стратегиях

2.2.5 Сведение матричной игры к задаче линейного программирования

2.2.6 Игры с природой

Вопросы для самопроверки

3. Многоцелевые задачи

3.1 Множество Парето

3.2 Метод идеальной точки

Вопросы для самопроверки

4. Нелинейное программирование

4.1 Графическое решение задачи нелинейного программирования

4.2 Метод множителей Лагранжа

4.3 Решение задач выпуклого программирования

Вопросы для самопроверки

Литература

лагранж линейный программирование матричный



Введение

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

1. Постановка задачи.

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

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

4. Решение задач, сформулированных на базе построенной математической модели.

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

6. Реализация полученного решения на практике.

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

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

1) выбирают некоторое количество переменных , заданием числовых значений которых однозначно определяется одно из возможных состояний исследуемого экономического процесса;

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

3) поиск наилучшего решения формулируют в терминах поиска оптимального (максимального или минимального) значения функции . Построенная функция называется целевой.

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

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

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

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



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

1.1 Различные формы записи задачи линейного программирования

Рассмотрим задачу линейного программирования (ЗЛП) в общем виде:

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

Задача линейного программирования задана в симметричной форме, если требуется максимизировать целевую функцию, все ограничения системы - неравенства «» (или минимизировать целевую функцию, все ограничения системы - неравенства «») и на все переменные наложено условие неотрицательности.

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

Множество всех допустимых решений называется областью допустимых решений (ОДР).

Допустимое решение , для которого достигается максимальное (минимальное) значение функции, называется оптимальным планом ЗЛП.

Термины «план» и «оптимальный план» возникли из экономических приложений.

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

Рассмотрим алгоритмы перехода от одной формы к другой.

· Симметричная каноническая. Переход осуществляется путем добавления в левую часть каждого неравенства дополнительной неотрицательной переменной. Если неравенство было «?», то балансовая переменная добавляется в левую часть неравенства со знаком «+». Если неравенство было «», то балансовая переменная добавляется в левую часть неравенства со знаком «-». Вводимые новые переменные называются балансовыми. Задачу минимизации функции Z заменяют на задачу максимизации функции (-Z) и используют, что min Z = -max (-Z).

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

· Общая каноническая. Каждая переменная, на которую не было наложено условие неотрицательности, представляется в виде разности двух новых неотрицательных переменных. Неравенства преобразуются в уравнения путем введения в левую часть каждого неравенства балансовой переменной таким же образом, как это было описано при переходе от симметричной к канонической форме. Задачу минимизации функции Z заменяют на задачу максимизации функции (-Z) таким же образом, как это было описано при переходе от симметричной к канонической форме.

1.2 Графический метод решения задачи линейного программирования

Графический метод применяется для решения ЗЛП, заданной в симметричной форме. Этот метод наиболее эффективно применяется для решения задач с двумя переменными, т.к. требует графических построений. В случае трех переменных необходимы построения в R³, в случае четырех переменных необходимы построения в R⁴ и т.д.

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

Пример 1

Следующие множества точек на плоскости являются выпуклыми:

Следующие множества точек на плоскости не являются выпуклыми:

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

Теорема 2 Пусть имеются две произвольные точки и в пространстве Rⁿ. Тогда для любой точки отрезка [PQ] должно выполняться: .где .

Гиперплоскостью в пространстве Rⁿ называется множество точек, удовлетворяющее уравнению . Заметим, что в двумерном случае гиперплоскостью является прямая.

Полупространством называется множество точек, удовлетворяющее одному из неравенств или . Гиперплоскость делит точки пространства на два полупространства. В двумерном случае гиперплоскостью является полуплоскость.

Теорема 3 Полупространство является выпуклым множеством.

Следствие Пересечение любого количества полупространств является выпуклым множеством.

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

Пример 2

Следующие множества являются многоугольниками.

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

Пример 3

Угловыми точками треугольника являются его вершины (их три). Угловыми точками круга являются точки окружности, которая его ограничивает (их бесконечное число).

Угловая точка многогранника называется его вершиной.

Рассмотрим ЗЛП, заданную в симметричной форме.

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



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

Пусть задача линейного программирования с двумя переменными задана в симметричной форме.

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

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

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

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

Для графического решения задачи ЗЛП используют следующий алгоритм:

Записывают уравнения граничных прямых a_i1x₁+a_i2x₂=b_i (i = 1,…,m) и строят их на плоскости X₁OX₂ по двум точкам.

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

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

Строят вектор и одну из прямых семейства (чаще всего Z = 0). Если выбранный для построения многоугольника масштаб не позволяет построить , то вместо него строят вектор (в случае, если длина слишком мала для построения) или (в случае, если длина слишком велика для построения), где .

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

Определяют экстремальную точку, соответствующую вершине многоугольника, путем параллельного перемещения прямой Z = с в направлении вектора . Это будет наиболее удаленная вершина многоугольника, в которой линия уровня пересекается с многоугольником.

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

Замечание: Если у функции требуется найти минимальное значение, то линию уровня Z = c перемещают в направлении вектора (или перемещают в направлении , но находят первую вершину пересечения линии уровня с многоугольником).

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

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

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

На рисунке а) функция достигает минимума в точке А, а максимума - в любой точке отрезка ВС (альтернативный оптимум); на рисунке б) максимум достигается в точке А, минимума функция не имеет; на рисунке в) функция не имеет ни минимума, ни максимума.

Пример 1

Решить графически ЗЛП:

Решение

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

(1) 2х1 + 5х2 = 20		(2) 8х1 + 5х2 = 40		(3) 5х1 + 6х2 = 30
х1	0	10		х1	0	5		х1	0	6
x2	4	0		x2	8	0		x2	5	0

Построим прямые.

Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем:

2 0 + 5 0 20 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

8 0 + 5 0 40 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

5 0 + 6 0 30 верно. Следовательно, отмечаем полуплоскость, содержащую «пробную» точку (0;0).

Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х₁,х₂ 0. Заштрихуем полученный пятиугольник.

Построим линию уровня Z = 0: 50х₁ + 40х₂ = 0

х1	0	4
x2	0	-5

Вектор определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор . Этот вектор также показывает направление наибольшего возрастания функции.

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

Точка А получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему:

8х₁ + 5х₂ = 40 5

5х₁ + 6х₂ = 30 8

_________________

-23x₂ = -40

Ответ: .

Пример 2

Пусть имеются два пункта, расстояние между которыми равно 1000 км. Между ними необходимо осуществить связь, имеющую 12 телефонных, 31 телеграфных и 18 фототелеграфных каналов с помощью кабелей двух типов, обладающих следующими характеристиками:

Каналы	Количество каналов для кабеля типа
	I	II
Телефонные	1	3
Телеграфные	5	4
Фототелеграфные	2	3
Стоимость 1 км кабеля (в у.е.)	12	16

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

Решение

Введем переменные: x₁ - количество кабеля типа I, x₂ - количество кабеля типа II. По определению эти переменные должны быть неотрицательны. При связи, использующей x₁ кабелей I типа и x₂ кабелей II типа, могут использоваться x₁+3x₂ телефонных каналов, 5x₁+4x₂ телеграфных каналов и 2x₁+3x₂ фототелеграфных каналов. Для осуществления связи необходимо наличие не менее требуемого количества каналов. Получаем ограничения на количества имеющихся каналов:

Затраты на осуществление связи, имеющей x₁ кабелей I типа и x₂ кабелей II типа, составят: (12x₁+16x₂)1000=12000x₁+16000x₂ условных единиц. Получаем математическую модель задачи:

Решим задачу графически. Каждое неравенство исходной системы ограничений определяет полуплоскость. Запишем уравнения граничных прямых для этих полуплоскостей.

(1) х1 + 3х2 = 12		(2) 5х1 + 4х2 = 31		(3) 2х1 + 3х2 = 18
х1	0	12		х1	0	6,2		х1	0	9
x2	4	0		x2	7,8	0		x2	6	0

Построим прямые.

Каждая прямая разбивает плоскость на две полуплоскости. Для выбора полуплоскостей, определяемых каждым неравенством, подставим координаты «пробной» точки (0;0) в каждое неравенство. Получаем:

0 + 3 0 12 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

5 0 + 4 0 31 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

2 0 + 3 0 18 не верно. Следовательно, отмечаем полуплоскость, не содержащую «пробную» точку (0;0).

Выбранные полуплоскости отметим стрелочками. Найдем пересечение отмеченных полуплоскостей с учетом условия: х₁,х₂ 0. Заштрихуем полученный неограниченный четырехугольник ABCD.

Построим линию уровня Z = 0: 12000х₁ + 16000х₂ = 0

х1	0	4
x2	0	-3

Вектор определяет направление наибольшего возрастания функции Z. Построим из начала координат вектор . Этот вектор также показывает направление наибольшего возрастания функции.

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

Точка B получается в результате пересечения прямых (2) и (3). Для нахождения ее координат решим систему:

5х₁ + 4х₂ = 31 3

2х₁ + 3х₂ = 18 4

_________________

7x₁ = 21

Ответ: Для осуществления связи с наименьшими затратами необходимо 3 кабеля I типа и 4 кабеля II типа. При этом минимальные затраты составят 100 000 у.е.



1.4 Использование надстройки Поиск решения MS Excel

Для решения оптимизационных задач используется надстройка Поиск Решения. Все действия по настройке и использованию данной надстройки приводятся для Excel 2007 и выше. Сначала необходимо убедиться, что эта надстройка присутствует на вкладке Данные в группе Анализ. Если команда Поиск решения или группа Анализ отсутствует, необходимо загрузить эту надстройку (Надстройка. Вспомогательная программа, служащая для добавления в Microsoft Office специальных команд или возможностей.). Для этого щелкните пиктограмму Microsoft Office (в верхнем левом углу окна), далее щелкните кнопку Параметры Excel. В появившемся окне Параметры Excel выберите слева поле Надстройки. В правой части окна должно быть установлено значения поля Управление равным Надстройки Excel, нажмите кнопку Перейти, которая находится рядом с этим полем. В окне Надстройки установите флажок рядом с пунктом Поиск решения и нажмите кнопку ОК. Далее можно работать с установленной надстройкой Поиск Решения.

До вызова Поиск Решения необходимо подготовить данные для решения задачи (из математической модели):

Определить ячейки, в которые будет помещен результат решения (изменяемые ячейки).

Ввести данные системы ограничений (коэффициенты при неизвестных и правую часть).

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

Ввести зависимость от изменяемых ячеек для целевой функции.

Ниже перечислены основные поля и кнопки диалогового окна Поиск решения и их назначение.

· Поле Установить целевую ячейку служит для указания ячейки, содержащей целевую функцию, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. (Эта ячейка должна содержать формулу).

· Переключатель Равной служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного значения). Чтобы установить заданное значение, введите его в поле, расположенное справа от слова «Значение».

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

· Кнопка Предположить используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки.

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

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

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

· Кнопка Удалить служит для удаления выбранного ограничения.

· Кнопка Выполнить решает поставленную задачу.

· Кнопка Закрыть служит для выхода без поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить.

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

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

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

Ниже перечислены основные поля и органы управления названных диалоговых окон.

· Поле «Ссылка на ячейку» служит для указания ячейки или диапазона, на значения которых необходимо наложить ограничение.

· Раскрывающийся список предназначен для выбора условия (<=, >=, =) определяющего ограничение.

· Поле «Ограничение» служит для задания числа, формулы, ссылки на ячейку или диапазон, определяющие ограничение.

· Кнопка «Добавить» используется для того, чтобы, не возвращаясь в окно диалога «Параметры поиска решения», наложить новое условие на поиск решения задачи.

Управление алгоритмом поиска и определение его параметров (скорости сходимости, точности и т.п.) выполняется с помощью диалогового окна «Параметры поиска решения», представленного на рисунке:

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

Ниже описаны значения полей, переключателей и флагов этого диалогового окна:

· Поле «Максимальное время» служит для ограничения времени, отпускаемого на поиск решения задачи. В поле можно ввести время (в секундах), не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Предельное число итераций» служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32767; значение 100, используемое по умолчанию, подходит для решения большинства простых задач.

· Поле «Относительная погрешность» служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Относительная погрешность по умолчанию 0,000001.

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

· Поле «Сходимость». Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле «Сходимость», поиск прекращается. Сходимость применяется только к нелинейным задачам, условием служит дробь из интервала от 0 до 1.

· Флаг «Линейная модель» служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи.

· Флаг «Показывать результаты итераций» служит для приостановки поиска решения для просмотра результатов отдельных итераций.

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

· Флаг «Значения не отрицательны» позволяет установить нулевую нижнюю границу для тех влияющих ячеек, для которых она не была указана в поле "Ограничение" диалогового окна «Добавить ограничение».

· Переключатель «Оценки» служит для указания метода экстраполяции (линейная или квадратичная), используемого для получения исходных оценок значений переменных в каждом одномерном поиске.

· Значение переключателя «Линейная» служит для использования линейной экстраполяции вдоль касательного вектора.

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

· Переключатель «Производные» служит для указания метода численного дифференцирования и для линейных задач его значение не играет роли.

· Переключатель «Метод поиска» служит для выбора алгоритма оптимизации (метод Ньютона или метод сопряженных градиентов) для указания направления поиска. Для решения задач линейного программирования его значения несущественны.

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

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

1.5 Решение ЗЛП средствами MS Excel

Пример

Решим задачу из Примера 2 раздела 1.3 с использованием настройки Поиск решения MS Excel.

Для решения нашей задачи создадим в Excel книгу с именем «Решение задачи линейного программирования». Подготовим данные на листе.

Сначала определим ячейки, в которые будет помещен результат решения. Пусть это будут ячейки В2, С2, сделаем у них заголовки. В этих ячейках нет данных, их должен будет рассчитать Excel, они выделены цветом. Далее заполним коэффициенты при неизвестных и правые части системы ограничений (строки 5-7). Заведем строку 9 для целевой функции. Цветом выделена ячейка, в которой будет находиться значение целевой функции для найденного оптимального решения.

В ячейки D5, D6, D7 ведем формулы для зависимостей левых частей системы ограничений, а в ячейку E9 - формулу для зависимости целевой функции.

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

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

В окне Поиск решения после нажатия кнопки Выполнить появляется окно Результаты поиска решения, в котором выбираем сохранение найденных значений и нажимаем кнопку ОК.

Результаты поиска решений (для ячеек В2 и С2 установлены числовые форматы с 0 знаками после запятой):

Получили . Решение совпадает с найденным графическим способом.

1.6 Двойственные задачи

Рассмотрим задачу использования сырья. Для изготовления двух видов продукции P₁, P₂ предприятие использует 4 вида сырья S₁, S₂, S₃, S₄. Запасы сырья и расходы на изготовление каждого вида продукции приведены в таблице. Составить план производства, при котором стоимость выпущенной продукции будет максимальной.



Сырье	Запасы	Расход на единицу продукции
		P1	P2
S1	20	3	2
S2	16	4	1
S3	30	0	3
S4	40	4	0
Стоимость единицы продукции (у.е.)		10	6

Для составления математической модели задачи введем две переменные: x₁ - количество произведенной продукции P₁ и x₂ - количество произведенной продукции P₂. По определению эти переменные должны быть неотрицательны. При производстве продукции предприятие израсходует 2x₁+3x₂ единиц сырья S₁, 2x₁+x₂ единиц сырья S₂, 3x₂ единиц сырья S₃ и 4x₂ единиц сырья S₄. Предприятие не может израсходовать сырья больше, чем у него имеется, поэтому получаем следующие ограничения на использование имеющегося сырья:

От продажи выпущенной продукции предприятие получит 10x₁+6x₂ у.е. Получаем математическую модель задачи:

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

Введем три переменные:

y₁ стоимость единицы сырья S₁,

y₂ стоимость единицы сырья S₂,

y₃ стоимость единицы сырья S₃,

y₄ стоимость единицы сырья S₄.

По определению эти переменные должны быть неотрицательны. Предприятию имеет смысл не выпускать продукцию только в случае, если выручка от продажи сырья не меньше, чем стоимость произведенной из этого сырья продукции. На производство одной единицы продукции P₁ расходуется 3 единицы сырья S₁, 4 единицы сырья S₂ и 4 единицы сырья S₄. Если не выпускать продукцию P₁, а продать все сырье, из которого его можно изготовить, то выручка от реализации этого сырья составит . Аналогично, выручка от реализации сырья, из которого можно изготовить продукцию P₂, составит . Выручка от продажи сырья должна быть не меньше стоимости единицы соответствующей продукции. Получаем ограничения:

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

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

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

2. Цели задач противоположны: в исходной задаче функция максимизируется, а в двойственной минимизируется.

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

4. Знаки неравенств задач противоположны: все неравенства исходной задачи имеют знак «», а двойственной «».

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

6. Переменные обеих задач не отрицательны.

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

Рассмотрим правила построения двойственной задачи в общем случае. Пусть имеется задачи линейного программирования в общем виде:

Каждой задаче такой можно поставить в соответствие двойственную задачу:

Построение двойственной задачи происходит по следующим правилам:

Сначала производится согласование цели исходной задачи и неравенств ее системы ограничений. Если целевая функция максимизируется, то все знаки неравенств должны быть «», если целевая функция минимизируется, то все знаки неравенств должны быть «». Если какое-нибудь неравенство не соответствует цели задачи, то его следует домножить на -1 для смены знака на противоположный.

Каждому i-му ограничению системы исходной задачи соответствует переменная y_i двойственной задачи и, наоборот, каждому j-му ограничению системы двойственной задачи соответствует переменная x_i исходной задачи. Подпишем эти соответствия слева от систем.

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

Цель двойственной задачи противоположна цели исходной задачи.

Матрица системы ограничений двойственной задачи получается транспонированием из матрицы системы ограничений исходной задачи;

Коэффициенты правых частей двойственной задачи - это коэффициенты при неизвестных в целевой функции исходной задачи.

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

На переменную y_j двойственной задачи следует наложить условие неотрицательности лишь в том случае, если i-е ограничение исходной задачи - неравенство.

Пример 1

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

Согласуем знаки неравенств с целью задачи. Целевая функция максимизируется, поэтому все неравенства должны быть «». Второе неравенство не согласовано с целью функции, умножим его обе части на -1.

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

Матрица левой части системы ограничений исходной задачи:

Матрица левой части системы ограничений двойственной задачи:

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

Второе ограничение является уравнением, т.к. на переменную x₂ не наложено условие неотрицательности. На переменную y₃ не наложено условие неотрицательности, т.к. соответствующее y₃ ограничение исходной задачи - уравнение.

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

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

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

Теорема 1 (Основное неравенство теории двойственности) Пусть и - допустимые решения пары двойственных задач в симметричной форме. Тогда, .

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

Теорема 2 (Достаточный признак оптимальности решения) Пусть и - допустимые решения пары двойственных задач и . Тогда, X^*, Y^* - оптимальные решения этих задач.

Экономический смысл Теоремы 2 заключается в том, что планы производства и оценки ресурсов оптимальны, если стоимость произведенной продукции совпадает с суммарной оценкой ресурсов.

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

Экономический смысл Теоремы 3 заключается в том, что максимально возможная стоимость произведенной продукции совпадает с минимально возможной стоимостью сырья.

Теорема 4 (Равновесия) Пусть и - допустимые планы пары двойственных задач в симметричной форме. Эти планы являются оптимальными тогда и только тогда, когда выполняются следующие условия дополняющей нежесткости:

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

Дадим экономическую интерпретацию условиям дополняющей нежесткости. Если в оптимальном решении какое-нибудь сырье имеет отличную от 0 оценку, то оно будет израсходовано полностью (ресурс является дефицитным). Если сырье расходуется не полностью (находится в избытке), то его оценка равна 0. Таким образом, получаем, что двойственные оценки - это мера дефицитности сырья. Оценка показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего сырья на 1 ед. Если некоторый вид продукции входит в план производства, то затраты на его производство совпадают со стоимостью произведенной продукции. Если затраты на производство какого-нибудь вида продукции больше стоимости продукции, то продукция не производится.

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

Пример 2

Составить двойственную задачу и найти ее решение по теореме равновесия

,

если известно решение исходной задачи: .

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

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

Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.

Подставим в составленную систему оптимальное решение исходной задачи:

.

Произведение равно нулю, если один из множителей равен 0. Получаем

Тогда,

Оптимальное решение двойственной задачи По Теореме 3 . Окончательно,.

Пример 3

Составить двойственную задачу к задаче из примера раздела 1.5 и найти ее решение по теореме равновесия

В разделе 1.5 было найдено решение исходной задачи средствами MS Excel:

Составим двойственную задачу. Знаки неравенств уже согласованы с целью задачи.

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

Найдем оптимальное решение двойственной задачи по теореме равновесия. Запишем условия дополняющей нежесткости.

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

Произведение равно нулю, если один из множителей равен 0. Получаем

Тогда,

Вычтем из первого уравнения второе:

Оптимальное решение двойственной задачи По Теореме 3 .

Окончательно,

Вопросы для самопроверки

1. Может ли система ограничений общей ЗЛП включать строгие неравенства?

2. Может ли целевая функция ЗЛП содержать нелинейные выражения из переменных?

3. Может ли допустимое решение ЗЛП содержать отрицательную компоненту?

4. Чем отличается оптимальное решение ЗЛП от допустимого?

5. Чем отличается канонический вид ЗЛП от общего?

6. Каждая ли симметрическая задача может быть приведена к каноническому виду? Если да, то как это делается?

7. Может ли каноническая задача быть приведена к общему виду?

8. Какое максимальное число неравенств может содержать ЗЛП с двумя переменными?

9. Как строится ОДР ЗЛП с двумя переменными?

10. Может ли ОДР быть невыпуклым многоугольником?

11. Может ли ОДР быть открытым множеством? Пустым?

12. Что такое градиент? Как его строить?

13. Что такое линия уровня? Как ее строить?

14. Может ли линия уровня целевой функции быть параллельной вектору целевой функции?

15. Может ли ЗЛП с двумя переменными иметь два и только два оптимальных решения?

16. В каком случае задача ЛП с двумя переменными не имеет решения?

17. Какой вывод можно делать из того, что ОДР не ограничена по направлению, противоположному вектору целевой функции?

18. Сколько переменных может содержать ЗЛП, которую можно решить графически?

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

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

21. Чем отличаются матрицы систем ограничений в паре двойственных задач?

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

23. Что можно сказать о решении двойственной задачи, если решение основной задачи не существует по причине несовместимости ее системы ограничений?

24. В чем смысл теоремы равновесия?



2. Специальные задачи линейного программирования

2.1 Задача о назначениях

Пример 1

В каждом из пяти филиалов производственного объединения могут изготовляться изделия пяти видов. Учитывая необходимость углубления специализации, в каждом из филиалов решено выпускать только один вид продукции, при этом каждый из видов изделий должен выпускаться одним из филиалов. Себестоимость каждого изделия в каждом из филиалов различна и задается матрицей C (- себестоимость производства i-м филиалом j-го вида продукции). Найти распределение выпуска продукции между филиалами, чтобы общая себестоимость выпущенной продукции была минимальной.

Составим математическую модель задачи.

i = 1,2,3,4,5, j = 1,2,3,4,5

Каждое филиал должен выпускать только один вид продукции:

Каждая вид продукции должен выпускаться:

Условие неотрицательности переменных:

x_ij 0, i = 1,2,3,4,5, j = 1,2,3,4,5

Суммарная себестоимость выпущенной продукции:

Z = 5x₁₁ + 11x₁₂ + 6x₁₃ + 11x₁₄ + 4x₁₅ + 10x₂₁ + 11x₂₂ + 9x₂₃ + 11x₂₄+ 5x₂₅ + 7x₃₁ + + 8x₃₂ + 6x₃₃ + 8x₃₄ + 2x₃₅ + 6x₄₁ + 4x₄₂ + 3x₄₃ + 7x₄₄+ 8x₄₅+ 4x₅₁ + 2x₅₂ + 5x₅₄ + 8x₅₅ min

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

1 этап

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

2. В каждом столбце находим минимальный элемент и вычитаем его из всех элементов соответствующего столбца.

2 этап

1. Проводим минимальное количество вертикальных и горизонтальных линий, пересекающих все нули.

2. Если таких количество таких линий равно количеству строк матрицы С, то 2-ой этап завершен.

3. В противном случае выберем среди неперечеркнутых элементов минимальный и построим новую матрицу по правилам:

а) из неперечеркнутых элементов вычитаем минимальный элемент;

б) к элементам, через которые проведены две линии, прибавляем минимальный элемент;

в) все остальные элементы не меняем.

Далее переходим на п.3

3 этап

В построении решения участвует последняя матрица из этапа 2.

1. Находим строку или столбец матрицы, в которой имеется единственный 0. Если такой строки или столбца нет, то берем любую строку или столбец, содержащие нули. Пусть .

2. Тогда в матрице X и все остальные элементы i-ой строки и j-го столбца равны 0.

3. В матрице С вычеркиваем i-ю строку и j-ый столбец.

4. Если в матрице С остался один элемент, то соответствующий элемент матрицы X равен 1 и этап 3 закончен. Иначе переходим на п.1.

Решим сформулированную выше задачу.

Этап 1

Этап 2

Этап 3

Порядок составления матрицы X:

1. Т.к. в 1-ой строке преобразованной матрицы имеется единственный элемент равный 0 (c₁₁=0), то x₁₁=1, а все остальные элементы 1-ой строки и 1-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 1-ю строку и 1-ый столбец.

2. Среди оставшихся невычеркнутыми элементов матрицы С 3-ий столбец содержит единственный 0 (c₅₃=0). Поэтому считаем, что x₅₃=1, а все остальные элементы 5-ой строки и 3-го столбца матрицы X равны 0. В матрице С исключаем из дальнейшего рассмотрения 5-ю строку и 3-ий столбец.