Место и роль методов оптимизации при моделировании и решении прикладных задач.

МЕТОДЫ ОПТИМИЗАЦИИ

Курс лекций

Перевод в электронный вид осуществляли

студенты факультета ИСТАС

Горин А.С.

Овсянникова М.В.

Москва 2009 г.

МЕТОДЫ ОПТИМИЗАЦИИ

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

Место и роль методов оптимизации при моделировании и решении прикладных задач.

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

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

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

- изучение взаимосвязей и установление критериев эффективности, позволяющих оценивать преимущество того или иного варианта;

- постановку задачи принятия решения в сложных ситуациях или в условиях неопределенности.

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

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

Основными понятиями являются:

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

Решение – определенный выбор параметров.

Оптимальное решение – те решения, которые предпочтительнее других.

Модель операции – описание операции с помощью математического аппарата.

Эффективность операции количественно выражается в виде критерия эффективности - целевой функции.

Например:

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

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

Общая постановка прикладной задачи.

Все факторы, входящие в описание модели можно разделить на две группы: внешние факторы (условия проведения операции), на которые мы не можем влиять а₁,а₂,а₃,…;

Зависимые факторы (элементы решений), которые мы можем выбирать х₁,х₂,х₃,…

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

z = f (x₁ x₂ … a₁ a₂ …)

Оптимизационная задача формулируется в общем виде.

Найти переменные х₁,х₂,…х_n, удовлетворяющие системе неравенств (уравнений) φ_j (x₁ x₂…x_n) ≤ b_j, где j =1, 2, …m, и обращают в max или min целевую функцию:

z = f (x_1, x_2,…a_1, a_2,…) → max (min).

 

Основные этапы построения оптимизационных моделей.

Основные этапы построения оптимизационных моделей можно представить в виде схемы:

 

 

 

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

 

 

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

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

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

Пример.

Для изготовления 2-х видов продукции Р1 и Р2 используют 4 вида ресурсов S1, S₂, S3,S4. Запасы ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице:

 

X₁, X₂– число единиц продукции.

Прибыль, получаемая от единицы продукции Р1 и Р₂ соответственно равны С₁=2 и С₂=3.

Так как потребление ресурсов S1, S₂, S3,S4 не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

х₁ + 3х₂ ≤ 18

2х₁ + х₂ ≤ 16 (2.1) – система ограничений.

х₂ ≤ 5

3х₁ ≤ 21

 

По смыслу задачи переменные

x1≥0, x2≥0 (2.2)

Суммарная прибыль составит

F = 2x1 + 3x2→max (2.3)

Итак, экономико-математическая модель задачи найти план выпуска продукции, Х (х₁,х₂) удовлетворяющий системе ограничений (2.1) и условию (2.2), при которых функция (2.3) принимает максимальное значение.

Задачу легко обобщить на случай n видов продукции с использованием m видов ресурса.

 

Примеры прикладных ЗЛП.

Пример 2.1

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

 

Вид сырья	Нормы расхода сырья на ед. изделия.	Общее кол-во сырья
А	В
Прибыль с
одного изде-
лия

Решение.

X₁, X₂– число единиц видов изделий соответственно А и В.

№ п/п	Алгоритм	Конкретное соответствие данной задаче
	Написать общую ЗЛП
	Записать число видов изделий	n = 2
	Записать число видов сырья	m = 3
	Записать аij	а11=12; а12=4; а21=4; а22=4; а31=3; а32=12
	Записать величины bi	b1=300; b2=120; b3=252
	Записать величины сj	с1=30; с2=40
	Записать поставленную экономико-математическую задачу.	12x1 + 4x2 ≤ 300 4x1 + 4x2 ≤ 120 3x1 + 12x2 ≤ 252   F = 30x1 + 40x2 → max

Выполнить самостоятельно:

Пример2.2

Рацион для питания животных на ферме состоит из двух видов кормов: I и II. 1 кг I корма стоит 80 руб. и содержит 1 ед.жиров, 3 ед.белков и 1 ед.углеводов. 1 кг II корма стоит 10 руб. и содержит 3 ед.жиров, 1 ед.белков и 8 ед.углеводов. Составить наиболее дешевый рацион питания, обеспечивающий жирами не менее 6 ед., белками не менее 9 ед., углеводами не менее 8 ед.

Пример 2.3

Решить графическим методом следующую задачу:

 

х₁ + 3х₂ ≤ 21

3х₁ + 2х₂ ≤ 21

3х₁ + х₂ ≤ 18

х₁; х₂ ≥ 0

 

Определить при каких х₁ и х₂ функция F = 30х₁ +60х₂ → max

Решение.

 

 

1. Область допустимых решений построим следующим образом. Постоим прямые с уравнениями

Х1
Х2

1) х₁ + 3х₂ = 21

 

 

Х1
Х2	10,5

2) 3х₁ + 2х₂ = 21

 

Х1
Х2

3) 3х₁ + х₂ = 18

 

 

4) х₁ = 0

5) х₂ = 0

Прямые пронумерованы, а рядом с соответствующим уравнением приведены координаты двух точек, через которые проходят прямые.

В результате получим выпуклый пятиугольник ОАВСD.

 

2. Строим нормальный вектор q = (30;60)/ 3, уменьшив значение координат в 3 раза. Прямая с уравнением 30 х₁ + 60 х₂ = 0 представляет собой «нулевую» линию уровня целевой функции. Эта прямая проходит через начало координат и перпендикулярна нормальному вектору q. Передвигаем эту прямую параллельно себе по вектору q и фиксируем ее крайнее положение (т.В).

 

3. Определим координаты точки В, которая принадлежит прямым 1) и 2).

Составляется система уравнений:

х₁ + 3х₂ = 21 х₁ = 3; х₂ = 6

3х₁ + 2х₂ = 21

 

Тогда F _max =30∙3 + 60∙6 = 450

При минимизации F = 30 х₁ + 60 х₂ линию уровня необходимо смещать параллельно самой себе в направлении противоположном вектору q. Минимум функции достигается в точке О(0;0).

Тогда F _min = 0.

 

К достоинствам геометрического метода решения ЗЛП относятся:

- наглядность;

- быстрота и легкость нахождения ответа.

 

К недостаткам геометрического метода относятся:

- возможны «технические» погрешности при приближенном построении графиков;

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

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

Выполнить самостоятельно.

ЗАДАНИЕ №1.

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

 

ТАБЛИЦА №1

	0,1,2	3,4,5,6	7,8,9
	f(x)=3x1-2x2; 2x1+x2≤2; x1+2x2≤2; x1,x2≥0;	f(x)=4x1+8x2; x1+x2≤3; x1+2x2≤2; x1,x2≥0;	f(x)=-4x1+8x2; 3x1+5x2≤15; x1-x3≤1; x1,x2≥0;
	f(x)=3x1-2x2; -x1+2x2≤2; 2x1-x2≤2; x1,x2≥0;	f(x)=-x1+6x2; 4x1+3x2≤12; -x1+x2≤1; x1,x2≥0;	f(x)=-x1+6x2; x1+x2≤3; -2x1+x2≤2; x1,x2≥0;
	f(x)=x1+6x2; 3x1+4x2≤12; -x1+x2≤2; x1,x2≥0;	f(x)=2x1+6x2; 3x1+4x2≤12; x1+2x2≤2; x1,x2≥0;	f(x)=8x1+12x2; 2x1+x2≤4; 2x1+5x2≤10; x1,x2≥0;
	f(x)=8x1+12x2; -3x1+2x2≤0; 4x1+3x2≤12; x1,x2≥0;	f(x)=3x1-2x2; 2x1+x2≤2; 2x1+3x2≤6; x1,x2≥0;	f(x)=6x1+4x2; x1+2x2≤2; -2x1+x2≤0; x1,x2≥0;
	f(x)=6x1+4x2; 3x1+2x2≤6; 3x1+x2≤3; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤1; 3x1+2x2≤6; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤2; 3x1+4x2≤12; x1,x2≥0;

 

2.5 Элементы линейной алгебры.

Любые m переменных системы уравнений с n переменными, где m < n называются основными (или базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n – m переменных называются неосновными (или свободными). Основными могут быть разные группы из n переменных. Максимальное число групп основных переменных равно числу сочетаний (где m-число уравнений, а n-число переменных). Решение системы Х(х₁, х₂…х_n) называется допустимым, если оно содержит лишь неотрицательные компоненты, в противном случае решение называется недопустимым. Базисным решением системы m уравнений с n неизвестными называется решение в котором все (n – m) переменных равны 0. Допустимое базисное решение иначе называется опорным планом.

Пример 2.4.

Решить систему уравнений

х₁ – х₂ – 2х₃ + х₄ = 0

2 х₁ + х₂ + 2х₃ – х₄ = 2

 

Общее число групп основных переменных: - X₁X₂, X₁X₃, X₁X₄, X₂X₃, X₂X₄, X₃X₄.

Выясним, могут ли быть основными переменные X₁X₂ , т.к. определитель матрицы из коэффициентов

׀ 1 -1 ׀ = 1•1 – 2•(-1) ≠ 0,

׀ 2 1 ׀

то X₁X₂ – основные переменные

Аналогично основным можно отнести X₁X₃; X₁X₄ (у них определители ≠ 0)

Группы X₂X₃, X₂X₄, X₃X₄ не могут быть основными, т.к. их определители = 0

 

Таким образом система уравнений имеет 3 базисных решения:

1) Для основных переменных X₁X₂ и не основных X₃X₄

(X₃= X₄ = 0)

Х₁-Х₂=0 X₁ = ⅔

2Х₁+Х₂=2 X₂ = ⅔

 

Таким образом, базисное решение: X = (⅔, ⅔, 0, 0) – допустимое решение;

2) Для основных переменных X₁X₃ и неосновных X₂ = X₄ = 0

X₁ = ⅔ X₃ = ⅓

Базисное решение: X₂ = (⅔, 0, ⅓, 0). Оно тоже допустимое.

3) Для основных переменных X₁ X₄ и неосновных X₂ = X₃ = 0

Базисное решение X₃ (⅔, 0, 0, -⅔) – недопустимое.

 

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

 

 

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

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

Для реализации СМ необходимо знать 3 основных элемента:

1. способ определения первоначального допустимого базисного решения;

2. правило перехода к лучшему решению;

3. проверка признака оптимальности решении, который состоит в следующем:

 

- если в выражении целевой функции отсутствуют положительные коэффициенты при неосновных переменных, то решение максимально;

- если отсутствуют отрицательные коэффициенты, то решение минимально.

 

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

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

Знак «+», если неравенство вида ≤;

Знак «-», если неравенство вида ≥.

 

Алгоритм вычислительной реализации этих трех элементов рассмотрим на следующем примере.

Пример 2.5.

Решить задачу симплексным методом:

z=18 y₁+16y₂+5y₃+21y₄ →min

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

y₁+2y₂+3y₄≥2

3y₁+y₂+y₃≥3

y₁, y₂, y₃, y₄≥0

Шаг 1:

Введем дополнительные переменные y₅, y₆ со знаком «-», т. к. «≥» получим систему уравнений в канонической форме:

 

y₁+2y₂+3y₄-y₅=2

3y₁+y₂+y₃-y₆=3

 

Если на первом шаге в качестве основных переменных взять дополнительные переменные y₅, y₆, тогда:

y₁=y₂=y₃=y₄=0, => y₅=-2; y₆=-3.

У₁=(0,0,0,0,-2,-3) – недопустимое базисное решение.

 

Шаг 2:

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

0 3 ≠0

1 0

 

y₃, y₄ - основные переменные.

y₁=y₂=y₆=y₅=0 неосновные переменные;

Выразим основные переменные через неосновные:

y₃=3-3y₁-y₂+y₆

y₄=2/3-y₁/3-2/3y₂+y₅/3

y₃=3, y₄=2/3;

 

Базисное решение У₂=(0,0,3,2/3,0,0) – допустимое решение.

Выражаем линейную функцию через неосновные переменные:

z=18y₁+16y₂+5(3-3y₁+y₆-y₂)+21(2/3-y₁/3-2/3y₂+y₅/3)= 29-4y₁-3y₂+7y₅+5y₆

Критерии оптимальности не выполняются, т.к. имеются отрицательные коэффициенты при y₁ и y₂, поэтому Z₁ =29 – не является минимальным.

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

Шаг 3:

y₁, y₄ - основные переменные.

y₂, y₃, y₅, y₆=0 – неосновные переменные;

После преобразований:

y₁=1- 1 y₂ - 1 у₃+ 1 у₆;

3 3 3

y₄= 1 - 5 у₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 9 3 9

z=25- 5 y₂+ 1 у₃+ 1 у₅- 1 у₆;

3 9 3 9

y₃=(1;0;0;1/3;0;0) – допустимое базисное решение.

Z(y₃)=25 – не является min, так как имеется отрицательный коэффициент при y₂, поэтому переменную y₂ переводим в основную.

 

Шаг 4:

y₁,y₃ – основные переменные.

y₃, y₄, y₅, y₆=0 – неосновные переменные.

у₁= 4 - 2 у₃+ 5 у₄- 1 у₅+ 2 у₆

5 3 3 5 5

y₂= 3 + 1 у₃- 9 у₄+ 3 у₅- 1 у₆

5 5 5 5 5

y₃= (4/5;3/5;0;0;0;0) – допустимое базисное решение

z=24+y₃+3y₄+6y₅+4y₆→min

Решение оптимальное, так как в выражении нет отрицательных коэффициентов при неосновных переменных.

Z(y₄)=24=min

 

Пример 2.6

Линейная функция:

F=2x₁+3x₂→max

Система ограничений

x₁+3x₂≤18

2x₁+x₂≤16

x₂≤5

3x₁≤21

x₁, x₂≥0

 

1. Приведем эту систему к каноническому виду, введя дополнительные переменные х₃, х₄, х₅, х₆:

 

х₁+3х₂+х₃=18

2х₁+х₂+х ₄=16

х₂+х₅=5

3х₁+х₆=21

 

Целевую функцию представим в виде:

F-2x₁-3x₂=0;

 

2. Заполняем первую симплексную таблицу: в ней х₃, х₄, х₅, х₆ – основные переменные (базис). Последняя строка называется оценочной.

Таблица №1.

 

←разрешающая строка

 

 

↑

разрешающий столбец

 

3. Проверяем выполнение критерия функции на max – первый опорный план не оптимальный, так как в F коэффициенты при x₁ и x₂ < 0

 

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.(второй столбец)

 

5. Делим свободные члены на коэффициенты разрешающего столбца, определяем оценочные отношения. И выбираем строку в качестве разрешающей, где это отношение минимальное min {6,16,5,∞}=5. На пересечении разрешающего столбца и разрешающей строки находиться разрешающий элемент a₂₃ = 1.

Для построения таблицы №2 в качестве основной переменной мы выбираем х₂, так как она образует разрешающей столбец таблице 1.

Переход к новому плану осуществляется пересчетом симплексной таблице (СТ) методом Жордана Гаусса.

 

Таблица №2.

 

 

← разрешающая строка

 

↑

разрешающий столбец

 

Построение 2^ой таблицы:

1)Заменим переменные в базисе с х₅ на х_2.

2)Делим элементы разрешающей строки х₅ (табл.1) на разрешающий элемент, результаты занесем в строку х_2, но в таблицу №2.

3)В остальных клетках разрешающегося столбца (табл.1) записываем 0.

4)Остальные клетки заполняем по правилу прямоугольника:

	НЭ=СТЭ-(А´В)/РЭ

 

НЭ- новый элемент.

СТЭ- старый элемент.

РЭ- разрешающий элемент.

А,В- эл-ты старого плана, образующие прямоугольник со старым эл-том и разрешающим элементом.

СТЭ А

 

 

В РЭ

 

b₁=18-(3х5)/1=3

а₁₁=1-(3х0)/1=1

b₂=16-(1х5)/1=11 и т.д.

Критерии оптимальности опять не выполнен, так как F имеет коэффициент -2<0

- наибольший отрицательный по модулю коэффициент |-2| определяет разрешающий столбец x₁

- min (3;11/2;∞;7)=3. Следовательно, 1^ая строка разрешающая а₁₁ - разрешающий элемент.

 

Таблица №3

 

← разрешающая строка

 

 

↑

разрешающий столбец

В таблице 3 критерий оптимальности вновь не выполнен. Разрешающий столбец x₅, разрешающая строка x₄, разрешающий элемент 5.

1)х₁ вместо х_3.

2)В строке х₁ делим все на 1.

 

Таблица №4

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4	х5	х6
х1				-1/5	3/5
Х5				-2/5	1/5
х2				2/5	-1/5
х6				3/5	-9/5
F				4/5	3/5

 

Новая СТ№4 – критерий оптимальности выполнен – оптимальное базисное решение X(6,4,0,0,1,3)

F=24 =max

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

Прибыль принимает максимальное значение F_max=24 при реализации 6 единиц продукции P₁ (x₁=6) и 4 единиц продукции P₂(x₄=4). Дополнительные переменные x₃, x₄, x₅, x₆ показывают остатки ресурсов каждого вида. При оптимальном плане производства x₃=x₄=0, то есть остатки ресурсов S₃ и S₄ равны 0, а остатки ресурсов S₅ и S₆ равны соответственно 1 и 3 единицам.

Выполнить самостоятельно.

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

-предпоследняя цифра - № столбца

-последняя цифра – № строки

Пример: Симплексным методом решить задачу максимизации.

F(x)=5x₁-x₂→max

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

1. Переведем систему ограничений в канонический вид, введя выравнивающие (базисные) неизвестные – x₃ и x₄.

Задача принимает следующий вид:

2x₁-x₂+x₃=3

3x₁+2x₂=6

x₁=x₂=x₃=x₄=0

F-5x₁+x₂=0

2. Заполняем первую симплексную таблицу. В ней x₃, x₄ – основные переменные (базис).

Таблица 1.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
x3		2	-1			3/2
x5
F		-5

 

 

← разрешающая строка

 

 

↑

разрешающий столбец

 

3. Проверяем выполнение критерия на max – первый опорный план не оптимальный, т.к. в F коэффициент при х₁<0

4. Выбираем наибольший по модулю отрицательный коэффициент F, который определяет разрешающий столбец.

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

 

Min (3, 2)= 3

2 2

Разрешающий элемент будет а₁₁=2

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

 

Таблицы 2.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	3/2		-1/2	1/2		-3
х4	3/2		7/2	-3/2		3/7
F	15/2		-3/2	5/2

 

 

← разрешающая строка

 

↑

разрешающий столбец

Построение таблицы №2.

1. Заменим переменные в базисе с х₃ на х₁.

2. Делим элементы разрешающей строки (табл.1) на разрешающий элемент, результаты занесем в строку х₁ в табл. №2.

3. В остальных клетках разрешающего столбца (табл. 1) записываем 0.

4. Остальные клетки заполняем по правилу прямоугольника

НЭ=СТЭ-(АхВ)/РЭ

 

СТЭ А

 

 

В РЭ

 

5. Критерий эффективности опять не выполнен, т.к. F имеет два коэффициента - 3 < 0

Построение таблицы №3

Таблицы 3.

Базис	Свободный член	Переменные	Оценочные отношения
х1	х2	х3	х4
х1	12/7			2/7	1/7
х2	3/7			-1/7	2/7
F	57/7			13/7	3/7

 

Из таблицы 3 видно – критерий оптимальности выполнен.

Оптимальные базисные решения Х^*=(12, 3,0,0)

7 7

F=5x₁-x₂=5x 12 - 3 = 57

7 7 7

 

 

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ №1

	0,1,2	3,4,5,6	7,8,9
	f(x)=3x1-2x2; 2x1+x2≤2; x1+2x2≤2; x1,x2≥0;	f(x)=4x1+8x2; x1+x2≤3; x1+2x2≤2; x1,x2≥0;	f(x)=-4x1+8x2; 3x1+5x2≤15; x1-x3≤1; x1,x2≥0;
	f(x)=3x1-2x2; -x1+2x2≤2; 2x1-x2≤2; x1,x2≥0;	f(x)=-x1+6x2; 4x1+3x2≤12; -x1+x2≤1; x1,x2≥0;	f(x)=-x1+6x2; x1+x2≤3; -2x1+x2≤2; x1,x2≥0;
	f(x)=x1+6x2; 3x1+4x2≤12; -x1+x2≤2; x1,x2≥0;	f(x)=2x1+6x2; 3x1+4x2≤12; x1+2x2≤2; x1,x2≥0;	f(x)=8x1+12x2; 2x1+x2≤4; 2x1+5x2≤10; x1,x2≥0;
	f(x)=8x1+12x2; -3x1+2x2≤0; 4x1+3x2≤12; x1,x2≥0;	f(x)=3x1-2x2; 2x1+x2≤2; 2x1+3x2≤6; x1,x2≥0;	f(x)=6x1+4x2; x1+2x2≤2; -2x1+x2≤0; x1,x2≥0;
	f(x)=6x1+4x2; 3x1+2x2≤6; 3x1+x2≤3; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤1; 3x1+2x2≤6; x1,x2≥0;	f(x)=8x1+6x2; -x1+x2≤2; 3x1+4x2≤12; x1,x2≥0;

 

Пример. Решить следующую задачу максимизации

F(x)=5x₁-x₂→max

2x₁-x₂+x₃≤3

3x₁+2x₂≤6

x₁≥0; x₂≥0

 

Запишем систему в каноническом виде

1) 2x₁-x₂+x₃=3

2) 3x₁+2x₂=6

3) x₁=0; x₂=0

 

Решение. В системе координат Х₁ОХ₂ построим ОДР.

Из первого уравнения:

При Х₁=0 X₂=-3 → (X₁,X₂)=(0,-3) прямая (1)

При Х₂=0 Х₁= 3 → (X₁,X₂)=(3, 0)

2 2

 

Из второго уравнения:

При Х₁=0 X₂=3 → (X₁,X₂)=(0,3) прямая (2)

При Х₂=0 Х₁=2 → (X₁,X₂)=(2, 0)

 

Из условия (3) (Х₁, Х₂)=(0,0) Х₁=0 – прямая (3)

Х₂=0 – прямая (4)

 

Для определения с какой стороны прямых ОДР все точки удовлетворяют неравенствам возьмем точку (1,1). Таким образом, ОДР лежит внутри АВСD.

Для определения точки выхода, строим прямую:

F(x)=5x₁-x₂=0

5x₁=x₂→ x₁=x₂=0 при x₁=1, x₂=5

Строим нулевую линию уровня целевой функции.

Строим нормальный вектор q (5.-1)

Передвигая линию уровня целевой функции параллельно себе, по вектору q, фиксируем ее крайнее положение (т.В), которая принадлежит прямым (1) и (2).

2x₁-x₂+x₃=3

3x₁+2x₂=6

 

x₁= 12 x₂= 3, т.е. Х^*=(12, 3)

7 7 7 7

F(Х^*)=5х 12 - 3 = 57

7 7 7

 

 

2.8Двойственные задачи линейного программирования (ДЗЛП).

Рассмотрим пример 2.6 и пример 2.5 и представим их в виде таблице

 

Задача 1 (исходная)	Задача 2 (двойственная)
F=2x1+3x2→max при ограничениях: x1+3x2≤18 2x1+x2≤16 x2≤5 3x1≤21 x1, x2≥0 Составить такой план выпуска продукции X=(x1, х2) при котором прибыль при реализации будет max. В общем виде задача запишется: n F=∑Cjxj→max, j=1 при ограничениях: n j=1,2…m ∑aijхi≤ bi i=1,2…n j=1	Z=18 y1+16y2+5y3+21y4→min при ограничениях: y1+2y2+3y4≥2 3y1+y2+y3≥3 y1, y2, y3, y4≥0 Найти такой набор цен ресурсов Y=(y1,y2,y3,y4), при котором общие затраты на ресурсы будут минимальны. В общем виде задачу запишем: m Z=∑ biyi →min, i=1 при ограничениях: m j=1,2…m ∑ aijyi≤ cj i=1,2…n i=1

 

Из таблице видно, что задачи 1 и 2 обладают следующими свойствами:

1) В задаче 1 ищут max, во 2 ищут min.

2) Коэффициенты целевой ф-ции 1-ой задачи являются свободными членами системы ограничения 2-ой задачи.

3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤, а в задаче минимизации вида ≥.

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

Для 1 3 18

задачи 1 A₁= 2 1 16

0 1 5

3 0 21

2 3 F

 

 

Для

задачи 2 A’₁= 1 2 0 3 2

3 1 1 0 21

18 16 5 21 Z

 

 

 

 

5) Число неравенств в системе ограничений 1-ой задачи совпадает с числом переменных 2-ой задачи.

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

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

2.9Алгоритм составления двойственных ЗЛП:

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

1) Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут max целевой функции, то все неравенства системы ограничений привести к виду ≤, а если ищут min – к виду ≥. Для этого неравенства, в которых это требование не выполняется, умножить на (-1).

2) Составить расширенную матрицу системы A₁.

₃₎ Найти матрицу A₁, транспонированную к матрице A_1.

4) Сформулировать двойственную ЗЛП

Этот алгоритм можно проиллюстрировать следующим примером:

Составить задачу двойственную следующей задаче:

F=14x₁+10x₂+14x₃+11x₄→max

Система ограничений:

4х₁+2х₂+2х₃+3х₄≤35

х₁+х₂+2х₃+3х₄≤30

3х₁+х₂+2х₃+х₄≥40*

х₁≥0

х₂≥0

х₃≥0

х₄≥0

 

Решение:

Алгоритм	Конкретные ситуации данного алгoритма
1.Все неравенства системы ограничений привести к виду ≤;   2.Составить расширенную матрицу системы А1, в которую включить: - матрицу коэффициентов переменных системы ограничений. - столбец свободных членов. - строку коэффициентов при переменных линейной функции.   3.Найти матрицу A'1 транспонированную к матрице А1.   4.Сформулировать двойственную задачу на основании полученной матрицы A'1	Приведем третье неравенство к виду: -3х1-х2-2х3-х4≤-40     4 2 2 3 35 А1= 1 1 2 3 30 -3 -1 -2 -1 -40 14 10 14 11 F   4 1 -3 14 2 1 -1 10 A'1 = 2 2 -2 14 3 3 -1 11 35 30 -40 Z   Z=35y1+30y2-40y3→min 4y1+y2-3y3≥14 2y1+y2-y3≥10 2y1+2y2-2y3≥14 3y1+3y2-y3≥11 y1≥0; y2≥0; y3≥0

Выполнить самостоятельно:

1. Составить ДЗЛП следующей задачи

F=-x₁+2x₂→max

При ограничении: 2x₁-x₂≥1

-x₁+4x₂≤24

x₁ -x₂≤3

x₁ +x₂≥5