Исследование операций, методы оптимизации

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

Тема 1: Общая методология оптимизационных задач. Основные понятия

1. Понятие оптимизационных задач, постановка задачи

2. Классификация задач оптимизации

1. Понятие оптимизационных задач, постановка задачи

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

Например:

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

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

3) в социологии: как распределить ограниченные ресурсы в государстве с целью уменьшения социальной напряженности в обществе.

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

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

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

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

При решении конкретной задачи управления предполагается:

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

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

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

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

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

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

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

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

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

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

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

В общем виде математическая модель состоит из:

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

- целевой функции. Целевая функция позволяет выбрать наилучший вариант из множества возможных;

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

Постановка задачи оптимизации.

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

Запишем задачу на минимум в виде:

(1)

где - целевая функция;

- допустимое множество;

- допустимая точка задачи

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

Точка называется

1) точкой глобального минимума функции на множестве или глобальным решением задачи (1), если (2)

2) точка х* называется точкой локального минимума, если существует некоторая окрестность этой точки, в любой точки которой значение функции больше, чем в x* - f(x)>f(x*) (3).

Ясно, что глобальное решение является и локальным; обратное неверно.

Проиллюстрируем на рисунке понятия локального и глобального оптимума для функции одной переменной.

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



2. Классификация задач оптимизации

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

1) детерминированные, стохастические, задачи оптимизации с неопределенностями;

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

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

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

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

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

5) однокритериальные и многокритериальные;

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

7) одномерные и многомерные, причем многомерные задачи могут быть малой и большой размерности. Если размерность вектора равна 1 (=1), то задача (1) называется однопараметрической задачей оптимизации (одномерной задачей оптимизации). Если размерность вектора больше 1 (>1), то задача (1) называется многопараметрической задачей оптимизации (многомерной задачей оптимизации).

8) одноэкстремальные и многоэкстремальные.



Тема 2: Задачи линейного программирования (ЗЛП)

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

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

3. Формы записи ЗЛП

4. Каноническая форма задач линейного программирования

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

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

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

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

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

Рисунок 1 - Экстремум целевой функции



Математическая модель ЗЛП записывается следующим образом:

max (или min) Z=z(X),(1)

X D.

ОДР может быть представлена системой линейных уравнений или неравенств.

Вектор Х=(х₁, х₂, .... x_п) является вектором управления или управляющим воздействия.

Допустимый план Х, при котором критерий оптимальности Z=z(X) достигает экстремального значения, называется оптимальным и обозначается через X*, экстремальное значение целевой функции -- через Z*=z(X*).

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

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

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

При выпуске продукции предприятие ограничено имеющимися ресурсами, количество которых обозначим m, а вектор ресурсов В = (b₁, b₂, ..., b_т). Известны также технологические коэффициенты a_ij, которые показывают норму расхода i-го ресурса на производство единицы j-ой продукции. Эффективность выпуска единицы j-и продукции характеризуется прибылью p_j.

Требуется определить план выпуска продукции Х=(х₁, х₂, ..., x_п), максимизирующий прибыль предприятия при заданных ресурсах.

Целевая функция выглядит следующим образом

,(1)

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

.(2)

Часто ассортимент продукции устанавливается вышестоящей организацией, т. е. его объемы должны быть заключены в некоторых границах D^н_j и D^в_j:тогда задается следующее ограничение:

(3)

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

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

1) максимум прибыли



2) минимум затрат на производство

3) максимум выпуска в стоимостном выражении (выручки от реализации продукции)

Пример. Предприятие может изготовлять четыре вида продукции 1, 2, 3 и 4. Сбыт любого ее объема обеспечен. Предприятие располагает в течение квартала трудовыми ресурсами в 100 человеко-смен, полуфабрикатами массой 260 кг, станочным оборудованием в 370 станко-смен. Нормы расхода ресурсов и прибыль от единицы каждого вида продукции представлены в табл.1.

Необходимо:

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

б) решить задачу с требованием комплектации, чтобы количество единиц третьей продукции было в 3 раза больше количества единиц первой;

в) выяснить оптимальный ассортимент при дополнительных условиях: первого продукта выпускать не менее 25 единиц, третьего -- не более 30, а второго и четвертого -- в отношении 1:3.



Таблица 1

Исходные данные

Ресурсы	Продукция	Объем ресурса
	1	2	3	4
Трудовые ресурсы, человеко-смен	2,5	2,5	2	1,5	100
Полуфабрикаты, кг	4	10	4	6	260
Станочное оборудование, станко-смен	8	7	4	0	370
Прибыль от единицы продукции, руб.	40	50	100	80	Max Z
План выпуска	Х1	Х2	Х3	Х4

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

целевая функция:

max: Z=40x₁+50x₂+100x₃+80x₄

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

а) на трудовые ресурсы:

2,5x₁+2,5x₂+2x₃+1,5x₄ ? 100;

на полуфабрикаты:

4x₁+10x₂+4x₃+6x₄ ? 260;

на станочное оборудование:

8x₁+7x₂+4x₃+10x₄ ? 370;

условие неотрицательности:



x_j ?0; j=1,4;

б) дополнительное требование комплектации выразится условием

3x₁=x₃, т.е 3x₁x₃=0;

в) граничные условия и условие комплектации представим так: х₁?25,

х₃?30, 3*х₂=х₄.

Задача о размещении заказов или загрузке взаимозаменяемых групп оборудования. Речь идет о распределения заказов между m (i=1,…, m) предприятиями (цехами, станками, исполнителями) с различными производственными и технологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказов. Требуется составить такой план размещения заказов, при котором задание было бы выполнено, а показатель эффективности достигал экстремального значения.

Сформулируем задачу математически. Пусть на т однородных группах оборудования нужно изготовить п видов продукции. План выпуска каждого вида продукции на определенный период задан набором х_j (j=1,2, …п). Мощность каждого вида оборудования ограничена и равна b_i. Известна технологическая матрица A=||a_ij||, где a_ij--число единиц j-ой продукции, выпускаемой в единицу времени на i-м оборудовании. Матрица С - матрица затрат, где c_ij--затраты, связанные с выпуском единицы j-й продукции на i-м оборудовании. Х -- вектор объема выпускаемой продукции.

Модель задачи примет следующий вид:

целевая функция -- минимизация расходов на реализацию всех заказов

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

а) по мощности оборудования

;

б) на выпуск продукции

;

в) условие неотрицательности

.

Данную задачу называют распределительной или задачей распределения.

Если по некоторым видам продукции допускается превышение плана, то ограничение (б) примет вид

.

В качестве целевой прибыли также можно принять:

а) максимум прибыли

;



б) минимум затрат станочного времени

.

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат a_ij. Очевидно, что это допущение далеко не всегда выполняется. Так объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно - в зависимости от изменения программы производства Х. К другим упрощающим предпосылкам относятся предположения о независимости цен _j от объемов x_j, что справедливо лишь для определенных пределов их изменения. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления усовершенствования модели.

3. Формы записи ЗЛП

Существует 3 формы записи ЗЛП:

1) в виде функций

max( или min)Z=,max( или min)Z=,

.

2) векторная форма

(скалярное произведение векторов)

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

A₁х₁+A₂х₂+..+A_nx_n = B

x>=0.

Где векторы

С = (С_1, С₂.. С_n), Х = (Х_1, Х₂.. Х_n), и.

3) матричная форма

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

AХ = B

X>=0,

где С = (с₁, с₂,…с_n),



4. Каноническая форма задач линейного программирования

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

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

.

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

Правила приведения ЗЛП к каноническому виду:

1) если в ограничениях правая часть отрицательная, то следует умножить это ограничение на -1;

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

3) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется в целевой функции и во всех ограничениях разностью между двумя новыми неотрицательными переменными: xk=x^*k - xl, где l - сводный индекс, x^*k>=, xl>=0.

Рассмотрим пример. Приведем к канонической форме:

.

Введем в каждое уравнение системы ограничений выравнивающие переменные х₄, х₅, х₆. Система запишется в виде равенств, причем в первое и третье уравнение системы ограничений переменные х₄, х₆ вводятся в левую часть со знаком «+», а во второе уравнение вводится х₅ со знаком «-».

Тогда

.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:

.

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

.

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

.

оптимизационный симплексный линейный программирование



Тема 3. Симплексный метод решения задач линейного программирования

1. Построение опорных планов

2. Признак оптимальности опорного плана. Симплекс таблица

3. Переход к нехудщему опорному плану. Симплексные преобразования

1. Построение опорных планов

Пусть поставлена задача: найти минимальное значение целевой функции

при канонических ограничениях:

.

Ограничение имеет предпочтительный вид, если при неотрицательной правой части (b_i ? 0) левая содержит переменную, входящую в данное уравнение с коэффициентом, равным единице, а в остальные ограничения-равенства с коэффициентом, равным нулю.

Например, в системе ограничений

первое и втрое уравнения имеют предпочтительный вид (х₁ и х₃).

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

;.

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

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

1) пусть задана система:

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

Но в расширенной задаче система ограничений имеет предпочтительный вид, следовательно, начальный опорный план:



.

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

2) задано систему ограничений:

Вычитая из левых частей дополнительные переменные , получим расширенную задачу. Однако система ограничений не имеет предпочтительного вида, так как дополнительные переменные входят в левую часть с коэффициентами, равными минус единице. Поэтому план недопустим. В этом случае вводят так называемый искусственный базис. К левым частям системы ограничений-равенств, не имеющих предпочтительного вида, добавляют искусственные переменные Wi. В целевую функцию Wi вводят с коэффициентом, равным (+М) в случае решения задачи на min, и с коэффициентом (-М) - на max, где М - большое положительное число. Полученная задача называется М-задачей.

М-задача формируется и в случае, когда ЗЛП задана в канонической форме, но не имеет предпочтительного вида.

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

Если ни одно из ограничений не имеет предпочтительного вида, то М-задача запишется:

Где знак (-) в относится к задаче на max. Начальный опорный план задачи:

.

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

2. Признак оптимальности опорного плана. Симплекс таблица

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

Пример



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

.

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

Б.п.	СБ	А0	х1	х2	х3	х4	х5
			2	-1	3	-2	1
х2	-1	3/2	0	1	1/2	0	1/2
х4	-2	2	0	0	1	1	0
х1	2	1/2	1	0	-1/2	0	1/2
Целевая функция	-9/2	0	0	-13/2	0	-1/2

Находим начальный опорный план

,

Обозначим через Б множество базисных переменных, через В- множество свободных переменных. Очевидно, при , . Значения называются оценками свободных переменных.

Признак оптимальности опорного плана:

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

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

Строка функции цели называется Z-строкой или индексной строкой. Начальный опорный план Х₀=(1/2;3/2;0;2;0) и Z(Х₀)=-9/2. Т.к. все оценки индексной строки неположительны, то план Х₀ - оптимален.

3. Переход к нехудщему опорному плану. Симплексные преобразования

Рассмотрим задачу

,

, , ,

, .

Начальный опорный план

,

Если все оценки свободных переменных , то план Х₀ - оптимальный. Если существуют положительные оценки свободных переменных, то столбец, которому соответствует наибольшее значение ?j называется разрешающим. Обозначим его номер j_o, а величину x_jo введем в базис.

Т.к. ?_jо > 0, то, не изменяя нулевых значений всех свободных переменных, можно уменьшить функцию Z за счет увеличения x_jo.

.

Чтобы перейти к новому опорному плану из базиса нужно вывести одну из переменных.

Значение xj_o нужно увеличить так, чтобы ни одно из значений базисных переменных x_i не было отрицательным. Т.е.

.

Возможны два случая.

1) Все элементы разрешающего столбца j_o неположительны, т.е. a_ijo ? 0. Если при решении задачи на min (max) в индексной строке имеются положительные (отрицательные) оценки свободных переменных, а в столбце переменной xj_o нет ни одного положительного элемента, то целевая функция не ограниченна снизу (сверху) на множестве допустимых планов задачи.

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

..

Отсюда получаем

.



Пусть данное выражение выполняется при i=i_o, тогда

.

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

Новое значение целевой функции:

.

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

Правила симплексного преобразования:

1) В индексной строке симплекс-таблицы найти наибольший положительный (или отрицательный) элемент. Столбец соответствующий этому элементу - разрешающий.

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

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

4) Неизвестные элементы, соответствующие разрешающим столбцу и строке, меняются местами.

5) Переход к следующей таблице. Элементы разрешающей строки новой таблицы будут равны

и .

6) Элементы разрешающего столбца равны нулю, за исключением , т.к. x_jo - базисная величина.

7) Все остальные элементы находятся по формулам

и

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

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

8) вычисляем элементы индексной строки



и

Для контроля вычислений можно вычислить

и

9) алгоритм продолжается до тех пор, пока не будет достигнуто условие оптимальности.

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

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

Пример: Решить симплекс-методом задачу линейного программирования

Б.п.	СБ	А0	х1	х2	х3	х4	х5
			14	-5	2	-1	8
х2	-5	5	1	1	0	0	-1	5/1=5
х3	2	41	5	0	1	0	3	41/5=8,2
х4	-1	15	-5	0	0	1	4
Целевая функция	42	-4	0	0	0	-1



Б.п.	СБ	А0	х1	х2	х3	х4	х5
			14	-5	2	-1	8
х1	14	5	1	1	0	0	-1	-
х3	2	16	0	-5	1	0	8	16/8=2
х4	-1	40	0	5	0	1	-1	-
Целевая функция	62	0	4	0	0	-5

Б.п.	СБ	А0	х1	х2	х3	х4	х5
			14	-5	2	-1	8
х2	14	7	1	3/8	1/8	0	0
х5	8	2	0	-5/8	1/8	0	1
х4	-1	42	0	35/8	1/8	1	0
Целевая функция	72	0	7/8	5/8	0	0

.

Оптимальный план X (7;0;0;42;2) и Z(x)=72.

Пример задачи с искусственным базисом.

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

Во 2-е и 3-е уравнение введем искусственные переменные:

Составим симплексную таблицу:

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	w1	w2
			3	2	3	0	0	0	M	M
х4	0	2	2	1	1	1	0	0	0	0	2/1=2
w1	M	8	3	8	2	0	-1	0	1	0	8/8=1
w2	M	1	0.	0	1	0	0	-1	0	1
Целевая функция	0	-3	-2	-3	0	0	0	0	0
	9M	3M	8M	3M	-M	-M	-M

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	w2
			3	2	3	0	0	0	M
х4	0	1	13/8	0	3/4	1	1/8	0	0	4/3
х2	2	1	3/8	1	1/4	0	-1/8	0	0	4
w2	M	1	0	0	1	0	0	-1	1	1
Целевая функция	2	-9/4	0	-5/2	0	-1/4	0	0
	M	0	-	M	-	-	-M	-

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6
			3	2	3	0	0	0
х4	0	1/4	13/8	0	0	1	1/8	3/4
х2	2	3/4	3/8	1	0	0	-1/8	1/4
x3	3	1	0	0	1	0	0	-1
Целевая функция	9/2	-9/4	0	0	0	-1/4	-5/2

Оптимальный план Х (0;3/4;1;1/4;0;0;0) и Z(х)=9/2.



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

1. Понятие двойственности

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

1. Понятие двойственности

Понятие двойственности рассмотрим на примере задачи оптимального использования сырья. Пусть на предприятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы ресурсов m видов в объемах b_i единиц соответственно (i=1;m). Из этих отходов, учитывая специализацию предприятия можно наладить выпуск n видов основной продукции.

Введем обозначения: a_ij - норма расхода i-го ресурса на производство j-ой продукции;

c_j - цена реализации j-ой продукции;

x_j - объем выпуска j-ой продукции, обеспечивающей предприятию максимум прибыли.

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

.

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

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

1) общую стоимость отходов производства покупающая организация стремиться минимизировать;

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

Эти требования формализуются в виде следующей ЗЛП:

- это требование покупающей организации.

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

.

Левая часть неравенства выражает стоимость ресурсов, идущих на производство единицы продукции первого вида; правая - цену продукции.

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

.

Переменные y_i называются двойственными оценками или объективно обусловленными оценками. В зарубежной литературе их называют теневыми ценами.

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

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

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

;

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

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

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

1) если прямая задача на максимум, то двойственная к ней - на минимум, и наоборот;

2) коэффициенты c_j целевой функции прямой задачи являются свободными членами двойственной;

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

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

5) если прямая задача на максимум, то ее система ограничений представляется в виде неравенств со знаком «?». Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств со знаком «?»;

6) число ограничений прямой задачи равно числу переменных двойственной, а число ограничений двойственной - числу переменных прямой;

7) все переменные в обеих задачах неотрицательны.

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

1) Прямая задача:

.

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

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

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

1) если на переменную x_j прямой задачи наложено условие неотрицательности, то j-e условие системы ограничений двойственной задачи является неравенством;

2) если на переменную x_j прямой задачи не наложено условие неотрицательности, то j-e условие системы ограничений двойственной задачи записывается в виде строгого равенства;

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

Прямая задача:

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

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

.

Прежде всего, ограничения типа ? умножением на -1 сведем к ограничениям типа ?. Получим:



Тема 5: Двойственные оценки

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

2. Анализ двойственных оценок

3. Оценка новой продукции

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

Основное неравенство двойственности: Для любых допустимых решений X и Y пары двойственных задач ЛП справедливо неравенство:

или .

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

Теорема существования (или малая теорема двойственности): Чтобы прямая и двойственная задачи имели оптимальное решение, необходимо и достаточно, чтобы существовали допустимые решения для каждой из них.

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

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

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

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

1) определить оптимальный план выпуска продукции, доставляющий предприятию максимум прибыли;

2) составить двойственную задачу.

Ресурсы	Продукция	Объем ресурса
	1	2	3	4
Трудовые ресурсы, человеко-смен	4	2	2	8	4800
Полуфабрикаты, кг	2	10	6	0	2400
Станочное оборудование, станко-смен	1	0	2	1	1500
Цена продукции, руб.	65	70	60	120	Max Z
План выпуска	Х1	Х2	Х3	Х4

1) Прямая задача:

.

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

Решение прямой задачи:

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	х7
			65	70	60	120	0	0	0
х4	120	500	5/12	-1/6	0	1	1/8	-1/24	0
х3	60	400	1/3	5/3	1	0	0	1/6	0
х7	0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
Целевая функция	84 000	5	10	0	0	15	5	0
						y1	y2	y3

Между переменными прямой и двойственной задачи можно установить следующее взаимно однозначное соответствие

и .

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

,

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

, .

В нашем примере,

x₁ x₂ x₃ x₄ x₅ x₆ x₇

y₄ y₅ y₆ y₇ y₁ y₂ y₃

Тогда оптимальный план прямой задачи Х(0;0;400;500;0;0;200) и Z(х)=84000; двойственной Y(15;5;0;5;10;0;0) и f(х)=84000.

Вторая теорема двойственности (о дополняющей нежесткости): чтобы допустимые решения X и Y пары двойственных задач были оптимальными, необходимо и достаточно выполнить условия:

,

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

если , то ;

если , то .

Аналогично,

если , то ;

если , то .

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

Ресурсы 1-й, 2-й и 4-й являются дефицитными, 3-й ресурс - недефицитный.

Критерий оптимальности Канторовича: Чтобы допустимые решения X и Y пары двойственных задач были оптимальными, необходимо и достаточно, чтобы значения целевых функций для них совпадали, т.е. z(x)=f(y).

Предположим, что величины ресурсов b_i могут изменяться. Возникает вопрос, при каких приращениях правых частей ограничений найденный оптимальный план Х^* не изменяется и как эти приращения сказываются на экстремальном значении целевой функции.

Третья теорема двойственности: Значения переменных y_i в оптимальном решении равны изменению целевой функции при малом изменении соответствующего ограничения ресурса:



.

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

В задаче приращение первого ограниченного ресурса на единицу ведет к увеличению целевой функции на 15, второго - на 5, четвертого - на 10. Третий ресурс избыточен, поэтому его увеличение не влияет на значение целевой функции.

Чем выше величина оценки y_i, тем острее дефицитность i-го ресурса.

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

2. Анализ двойственных оценок

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

В рассматриваемой задаче рентабельным будет выпуск 3-й и 4-oй продукции; убыточным - 1-oй и 2-ой.

Рассмотрим состав двойственной оценки 1-го ресурса.

Возьмем столбец в симплекс-таблице, соответствующий данному ресурсу. Элементы столбца отражают изменение значений базисных переменных при увеличении первого ресурса на единицу. Так значение х₄ изменится на 1/8, т.е. х₄=500+1/8; х₃=60+0; резерв по 2-му ресурсу сократиться на х₇=200-0,125=199,875.

Оценка выпускаемой продукции (целевая функция) увеличится на 0,125*120+0*60=15, что соответствует двойственной оценке первого ресурса. Аналогично при увеличении второго ресурса на единицу целевая функция увеличится на (-0,0417)*120+0,167*60=5.

Дополнительные переменные показывают, что 1-й,2-й ресурс используются полностью, т.к. х*₅=х*₆=0. х*₇=200, следовательно, 200 единиц третьего ресурса осталось неиспользованным.

Возникает вопрос - возможна ли замена одного ресурса другим.

Коэффициент взаимозаменяемости - показывает, сколько единиц ресурса i необходимо дополнительно приобрести, чтобы компенсировать уменьшение ресурса j на единицу:

.

Пример, и .

Знак ? означает, что невозможно i-й ресурс заменить j-ым.

На основе вычисленных значений строится матрица взаимозаменяемости ресурсов.



Тема 6: Транспортная задача

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

2. Структура системы ограничений и начального опорного плана задачи

3. Условия оптимальности опорного плана

4. Решение транспортной задачи методом потенциалов

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

Пусть имеется m (i=1;т) поставщиков, располагающих некоторым однородным продуктом в объемах по а_i единиц, и n получателей с объемами потребления по b_j единиц. Задана матрица C=|с_ij|, где с_ij -- стоимость перевозки единицы продукции от i-го поставщика j-му потребителю. Возникает задача определения плана перевозок X=| x_ij |, где x_ij -- количество единиц продукции, поставляемой по коммуникации ij. Целевой функцией можно считать суммарную стоимость всех перевозок.

Условия задачи в табличном виде выглядят следующим образом:

	b1	b2	...	bj	...	bn
a1	x11 c11	x12 c12	...	x1j c1j	...	x1n c1n
a2	x21 c21	x22 c22	...	x2j c2j	...	x2n c2n
...	...	...	...	...	...	...
ai	xi1 ci1	xi2 ci2	...	xij cij	...	xin cin
...	...	...	...	...	...	...
am	xm1 cm1	xm2 cm2	...	xmj cmj	...	xmn cmn

Если

(1)



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

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

Функция цели -- минимизация суммарных затрат на перевозку продукции

.(2)

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

1) на запасы продукции у поставщиков

(3)

2) на запросы потребителей, которые должны быть полностью удовлетворены,

(4)

3) условия неотрицательности, исключающие обратные перевозки:

.(5)

Матрицу X=| x_ij|, удовлетворяющую ограничениям, называют допустимым планом перевозок, а переменные x_ij -- допустимыми перевозками.



Графический способ задания условий задачи

Допустимый план Х, доставляющий целевой функции минимальное значение именуется оптимальным; С=|| с_ij || называется матрицей тарифов или матрицей транспортных издержек. Отрезок или линия, соединяющая i-го поставщика с j-м потребителем, называется коммуникацией и обозначается (ij) или (A_iB_j). Если на всех коммуникациях (ij) проставлены величины перевозок х_ij, то получается транспортная сеть.

Если условие не выполняется, то модель транспортной задачи называется открытой. В случае, если запасы поставщиков больше потребностей получателей, вводят n+1-гo фиктивного потребителя, запросы которого равны излишкам запаса, т. е.

.

Тарифы C_i;n+1 считают равными нулю. Получим расширенную закрытую задачу. Ее оптимальный план даст оптимальный план исходной задачи. Поставки х_i;n+1 в оптимальном плане расширенной задачи покажут остатки продукции на складах поставщиков.

Если потребности превышают запасы, то вводят m+1-ro фиктивного поставщика. Его запасы считают равными недостающей продукции:



.

Тарифы с_m+1;j равны некоторому большому положительному числу М. В расширенной задаче получим баланс потребностей и запасов. Поставки x_m+1;j в оптимальном плане расширенной задачи покажут объемы недостачи продукции.

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

.

2. Структура системы ограничений и начального опорного плана задачи

Модель транспортной задачи -- задача линейного программирования. Ее оптимальный план всегда можно найти симплексным методом. Однако матрица системы ограничений специфична.

Специфика заключается в следующем:

1) Коэффициенты при неизвестных во всех ограничениях равны единице.

2) Каждая неизвестная величина встречается в двух и только в двух уравнениях: один раз -- в системе (3) и один раз -- в системе (4).

3) Система уравнений симметрична относительно всех переменных х_ij.

Благодаря этой специфике общую процедуру симплексного метода применительно к транспортной задаче можно значительно упростить. При любом методе ее решение начинают с нахождения начального опорного плана. В невырожденном опорном плане ЗЛП должно содержаться f отличных от нуля координат, где f -- ранг системы ограничений. В системе ограничений уравнений закрытой транспортной задачи имеется m+n--1 линейно независимых уравнений, т. е. ранг системы ограничений (3--4) равен m + n--1.

Рассмотрим несколько простых способов построения начального опорного плана.

1) Способ северо-западного угла предполагает начать работу с клетки (1, 1) (на географической карте это соответствует северо-западному углу, отсюда -- название способа). Предположим, что x₁₁=min{a₁, b₁}.

а) Если a₁ > b₁, то х₁₁ = b₁, т.е запросы первого потребителя будут полностью удовлетворены. В дальнейшем первый столбец в расчет не принимается, в нем переменные х_i1=0; i=2,m. Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку (1;2) меньшее из чисел (a₁ - b₁) и a₁ > b₂, т.е x₁₁=min{a₁- b₁; b₂}. когда запасы первого поставщика исчерпаны, то дальнейшие расчеты производятся по второй строке и т.д.

б) Если a₁ < b₁, то x₁₁=a₁, при этом запас первого поставщика будет полностью исчерпан, поэтому x_1j=0, j=2;n. Первая строка из дальнейшего рассмотрения исключается.

Аналогично производятся вычисления во всех остальных строках. План перевозок, построенный по такому способу, содержит m+n--1 заполненных клеток, т. е. является опорным.

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

Пример. Составить план перевозок зерна из четырех районов, запасы которых соответственно 800, 700, 1000 и 500 тыс. ц., на три склада в количестве 1 000, 1100 и 900 тыс. ц. Затраты на перевозку 1 тыс .ц. зерна представлены в таблице: