Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции - Общая методология оптимизационных задач - файл 1.doc


Лекции - Общая методология оптимизационных задач
скачать (841 kb.)

Доступные файлы (1):

1.doc841kb.20.12.2011 14:15скачать

содержание
Загрузка...

1.doc

  1   2   3
Реклама MarketGid:
Загрузка...
Тема 1: Общая методология оптимизационных задач. Основные понятия.
1 Понятие оптимизационных задач, постановка задачи

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

Например:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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



(0)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

8) одноэкстремальные и многоэкстремальные.
Тема 2: Задачи линейного программирования (ЗЛП)


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

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

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

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


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

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

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



Рисунок 1 – Экстремум целевой функции
Математическая модель ЗЛП записывается следующим образом:
max (или min) Z=z(X), (1)

X D.

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

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

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

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

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

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

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

, (1)

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

. (2)

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

(3)

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

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

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



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



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



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


Необходимо:

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

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

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

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

целевая функция: max: Z=40x1+50x2+100x3+80x4

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

а) на трудовые ресурсы: 2,5x1+2,5x2+2x3+1,5x4 ≤ 100;

на полуфабрикаты: 4x1+10x2+4x3+6x4 ≤ 260;

на станочное оборудование: 8x1+7x2+4x3+10x4 ≤ 370;

условие неотрицательности: xj ≥0; j=1,4;

б) дополнительное требование комплектации выразится условием 3x1=x3, т.е 3x1­x3=0;

в) граничные условия и условие комплектации представим так: х1≥25, х3≤30, 3*х24.

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

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

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

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



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

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

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

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

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

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

.

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

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

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

Т.к. любая модель содержит упрощающие предпосылки, для корректного применения полученных результатов необходимо четкое понимание сути этих упрощений, что, в конечном счете, и позволяет сделать вывод об их допустимости или недопустимости. Наиболее существенным упрощением в рассмотренных моделях является предположение о прямопропорциональной (линейной) зависимости между объемами расхода ресурсов и объемами производства, которая задается с помощью норм затрат aij. Очевидно, что это допущение далеко не всегда выполняется. Так объемы расхода многих ресурсов (например, основных фондов) изменяются скачкообразно – в зависимости от изменения программы производства Х. К другим упрощающим предпосылкам относятся предположения о независимости цен j от объемов xj, что справедливо лишь для определенных пределов их изменения. Данные «уязвимые» места важно знать еще и потому, что они указывают принципиальные направления усовершенствования модели.
3 Формы записи ЗЛП
Существует 3 формы записи ЗЛП:

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

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

.

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

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

при ограничениях A1х1+A2х2+..+Anxn = B

x>=0.

Где векторы С = (С1, С2.. Сn), Х = (Х1, Х2.. Хn), и.

  1. матричная форма



при ограничениях AХ = B

X>=0,

где С = (с1, с2,…сn),
4 Каноническая форма задач линейного программирования
Если все ограничения в задаче линейного программирования являются уравнениями и на все переменные xj налагаются условия неотрицательности, то она называется задачей линейного программирования в канонической форме или канонической задачей линейного программирования (КЗЛП).



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

.

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

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

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

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

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

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

.

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

Тогда .

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

.

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

.

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

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

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

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


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



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

.

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

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



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

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

; .

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

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

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-строкой или индексной строкой. Начальный опорный план Х0=(1/2;3/2;0;2;0) и Z(Х0)=-9/2. Т.к. все оценки индексной строки неположительны, то план Х0 - оптимален.
3 Переход к нехудщему опорному плану. Симплексные преобразования.
Рассмотрим задачу

,

, , ,

, .

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

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

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

.

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

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

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

..

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

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



.


Б.п.

СБ

А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



























  1   2   3



Скачать файл (841 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru