ВАРИАНТ 5. Методы оптимальных решений
ВАРИАНТ 5
_
ПОЛНОЕ ЗАДАНИЕ В ДЕМО ФАЙЛЕ,
ЧАСТЬ ДЛЯ ПОИСКА ДУБЛИРУЮ НИЖЕ
Министерство образования Российской Федерации
Хабаровская государственная академия экономики и права
Кафедра математики и математических методов в экономике
Т.Н. Беспрозванная
Методы оптимальных решений
Хабаровск 2003
2
ББК У052
Беспрозванная Т.Н. Математическая оптимизация. Хабаровск: РИЦ ХГАЭП,
2003. с.
Рецензенты:
Лапаева Л.Н. к.э.н., профессор, завкафедрой
бухгалтерского учета и аудта ДВГУПС
Бочкарева Т.А. главный бухгалтер фирмы
«ДальАудитСервис», к.э.н.
В учебном пособии кратко изложены принципы учета затрат и калькулирования
себестоимости продукции и особенности учета и калькулирования в отраслях
производственной сферы. Учебное пособие предназначено для студентов
дистанционной формы обучения.
© Хабаровская государственная академия экономики и права. 2003
© Беспрозванная Т.Н., 2003
3
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ 5
ГЛАВА 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ 7
1.1. Экономико-математические модели 7
1.2. Примеры математических моделей задач линейного программирования 7
1.2.1. Задача планирования производства 7
1.2.2. Задача выпуска продукции с реализацией излишков ресурсов 10
1.2.3. Задача распределения прибыли предприятия 11
1.2.4. Задача выбора вариантов вложенных средств 13
1.2.5. Задача о кредитной политике банка (конкретный пример) 14
1.2.6. Транспортная задача 15
1.2.7. Использования мощностей оборудования 17
1.3. Математическая постановка задач линейного программирования 18
1.3.1.Общая задача линейного программирования 18
1.3.2.Стандартная задача линейного программирования 18
1.3.3.Основная задача линейного программирования 19
1.3.4.Системы линейных уравнений 20
1.3.5. Метод Жордана Гаусса 21
1.3.6. Канонические системы. Преобразование однократного замещения 24
1.3.7. Алгоритм преобразования однократного замещения 24
1.4.Общая теория линейного программирования 26
1.4.1. Выпуклые множества 26
1.5. Основные методы решения задач линейного программирования 33
1.5.1. Графический метод 33
1.5.2. Каноническая задача линейного программирования 37
1.5.3. Симплексные таблицы 38
1.5.4. Основные теоремы симплекс метода 39
1.5.5. Альтернативный оптимум 42
1.5.6. Метод искусственного базиса 45
1.6.Двойственность и анализ чувствительности 49
1.6.1. Определение двойственной задачи 49
1.6.2. Теоремы двойственности 50
4
1.6.3. Экономико-математический анализ полученных оптимальных решений
1.7. Математические модели транспортных задач 65
1.7.1. Теоремы о разрешимости транспортной задачи 67
1.7.2. Алгоритм решения транспортной задачи методом потенциалов 69
1.7.3. Открытая транспортная задача 73
1.8. Модели сетевого планирования и управления 75
1.8.1. Назначение и области применения сетевого планирования и управления 75
1.8.2. Порядок и правило составления сетевого графика 75
1.8.3. Временные характеристики сетевого графика 78
2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ 83
2.1. Постановка задачи динамического программирования 83
2.2. Принципы динамического программирования 84
2.3. Принцип оптимальности 86
2.4. Оптимальное распределение ресурсов как задача динамического
программирования 87
ГЛАВА 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 90
3.1. Постановка задачи нелинейного программирования 90
3.2. Геометрическая интерпретация задачи нелинейного программирования 91
3.3. Математические основы выпуклого программирования 92
3.4. Метод множителей Лагранжа. Экономический смысл множителей
Лагранжа 95
3.5. Теорема Куна-Таккера 98
3.6. Задача квадратичного программирования и ее решение 100
ВАРИАНТЫ ЗАЧЕТНЫХ ЗАДАНИЙ 103
СПИСОК ЛИТЕРАТУРЫ 110
5
ВВЕДЕНИЕ
Экономико-математическое моделирование как средство принятия оптимальных
решений
Многие практические задачи любой деятельности человека связаны с
определением наилучшего, оптимального варианта решения. К таким задачам
относятся задачи экономического планирования, управления, распределения
ограниченных ресурсов, разрешения конфликтных ситуаций и множество других задач,
в которых определяется наилучший вариант решения с точки зрения поставленной
цели. Для осуществления этой цели необходимо формализовать условие задачи и затем
составить математическую модель.
Математическая модель – это система математических уравнений, неравенств,
формул и различных математических выражений, описывающих реальный объект,
составляющие его характеристики и взаимосвязи между ними.
Процесс построения математической модели называют математическим
моделированием.
Моделирование экономического объекта позволяют свести экономический анализ
производственных процессов к математическому анализу и принятию самых
эффективных решений.
Для задачи экономического плана строятся экономико-математические модели.
Для построения таких моделей необходимо осуществлять следующее:
1) выбор некоторого числа переменных величин для формализации модели
объекта;
2) выражение взаимосвязей, характеризующих объект, в виде уравнений и
неравенств;
3) выбор критерия эффективности и выражение его в виде математического
соотношения – целевой функции.
Экономико-математические модели включают в себя систему ограничений,
целевую функцию.
Как правило, в качестве цели выбирается экономический показатель – прибыль,
рентабельность, себестоимость и т.д. Система ограничений состоит из отдельных
математических уравнений или неравенств.
Решением экономико-математической модели, или доступным планом называется
набор значений неизвестных, который удовлетворяет ее системе ограничений. Модель
имеет множество допустимых планов и среди них нужно найти такое, которое
удовлетворяет системе ограничений и при котором целевая функция принимает
оптимальное значение. Если модель задачи имеет множество оптимальных планов, то
для каждого из них значение целевой функции одинаково.
Итак, экономико-математическая модель представляет собой:
1) систему ограничений – равенства или неравенства вида больше или равно ( ),
меньше или равно ( ).
2) Условие неотрицательности переменных ( 0, j x j 1,n ).
3) Целевую функцию.
Математическая общая модель задачи может быть представлена в виде:
Найти значения n переменных X1, X2 ,, Xn , которые удовлетворяют системе
ограничений
fi x1; x2;; xn ; ; bi (i 1,m)
6
и максимизируют или минимизируют
Z fi x1; x2 ;; xn .
Если на переменные налагается условие неотрицательности, тогда в модель
задачи вводится условие
0, j x ( j 1,n ).
Если ограничения и целевая функция линейны относительно переменных. То
модель называют линейной. В случае, если хотя бы одна из функций fi и Z нелинейна,
то модель называют нелинейной.
Задачи оптимизации, представлены этими моделями, дали толчок к разработке
различных методов решения, которые должны участвовать соответствующие
математические свойства этих моделей. Наиболее известными и эффективными из них
являются методы линейного программирования, когда целевая функция и все
ограничения будут линейными. Для решения математических моделей других типов
предназначены методы нелинейного программирования, динамического,
целочисленного программирования, многокритериальной оптимизации, методы
сетевых моделей.
Реализация перечисленных методов должна включать следующие этапы:
1) Формализация исходной проблемы.
2) Построение математической модели.
3) Решение модели
4) Проверка эффективности модели.
5) Реализация решения.
1. О формализации исходной проблемы было сказано ранее. В результате
исследования данной проблемы должны быть получены три принципиальных элемента
решаемой задачи: а) описание возможных альтернативных решений; б) определение
целевой функции; в) построение системы ограничений, накладываемых на возможные
решения.
2. Построение математической модели означает перевод формализованной задачи
на четкий язык математических соотношений. На данном этапе не обязательно строить
новую модель, обычно, полученная модель является одной из стандартных моделей
либо линейного, либо нелинейного программирования. Если же результирующая
модель не приводится к какому-либо типу известных моделей, то ее необходимо
упростить, либо использовать имитационное моделирование.
3. Решение модели обычно достигается путем использования соответствующих
существующих алгоритмов оптимизации. Очень важным аспектом этого этапа является
анализ чувствительности полученного решения. Это подразумевает получение
дополнительной информации о поведении «оптимального» решения при изменении
некоторых параметров модели. Данный анализ чувствительности особенно необходим
тогда, когда невозможно точно оценить параметры модели.
4. Проверка адекватности модели предполагает проверку правильности
составленной модели. Необходимо убедится, что решение, полученное в рамках
построенной модели, имеет смысл и приемлемо. Обычным методом проверки
адекватности модели является сравнение полученного решения с известными ранее
решениями или поведением реальной системы. Модель считается адекватной, если при
определенных начальных условиях ее поведение совпадает с поведением исходной
системы при тех же начальных условиях.
5. Реализация решения подразумевает перевод результатов решения модели в
рекомендации, представленные в форме отчета.
7
Вопросы для самопроверки
1. Что такое математическая модель?
2. Понятие математического моделирования.
3. Что необходимо осуществить для построения математической модели?
4. Что подразумевается под решением математической модели?
5. Как может быть представлена математическая модель в общем виде?
6. Этапы реализации методов решения задач по модели.
ГЛАВА 1. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ЗАДАЧ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ
1.1. Экономико-математические модели
Линейное программирование (ЛП) – это метод математического моделирования,
разработанный для оптимизации использования ограниченных ресурсов. ЛП успешно
применяется в области сельского хозяйства, индустрии, военной области, транспортной
отрасли, экономике, системе здравоохранения, в социальных науках и т.д. На
алгоритмах линейного программирования базируются алгоритмы более сложных типов
моделей, включая целочисленное, нелинейное и стахостическое программирование.
1.2. Примеры математических моделей задач линейного программирования
1.2.1. Задача планирования производства
Для изготовления n – видов продукции используют m – видов ресурсов. Запасы
ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции,
а также прибыль, получаемая от реализации единицы продукции, приведены в табл.
1.2.1.
Таблица 1.2.1
… …
a12
2
… …
…
…
…
…
…
a11
Прибыли от
реализации ед.
продукции
Запас
ресурсов
1
Вид продукции
Вид ресурса
2
1 j n
j
m am2
a2j a2n
a1 j
ai1
a1n
am1
a21
amj
a22
c1 c2 c j cn
b1
amn
b2
…
…
…
…
…
…
…
…
…
…
…
…
…
… …
…
… …
Затраты ресурсов на единицу продукции
bi
bm
ai2 ain
…
aij
Необходимо составить такой план выпуска продукции, при котором прибыль от
ее реализации будет максимальной.
8
Составим экономико-математическую модель данной задачи.
Пусть x1; x2 ;; xn – это соответствующие объемы выпускаемой продукции. Цель
задачи – получение наибольшей прибыли от реализации продукции. Суммарную
прибыль можно выразить следующей функцией
Z c1x1 c2 x2 cn xn.
Прибыль должна стремиться к максимуму (max).
Так как запас ресурсов ограничен, то переменные x1, x2 ,, xn должны
удовлетворять системе ограничений
1 1 2 2 .
1 1 2 2
21 1 22 2 2 2 2
11 1 12 2 1 1 1
m m ij j mn n m
i i ij j in n i
j j n n
j j n n
a x a x a x a x b
a x a x a x a x b
a x a x a x a x b
a x a x a x a x b
По смыслу задачи переменные должны быть неотрицательные
0, j x ( j 1,n ).
Или более кратко математическая модель задачи выпуска продукции имеет вид:
0 ( 1, ) (1.2.3)
1 ( 1, ) (1.2.2)
max (1.2.1)
1
x j n
n
j i i m
aij x j b
Z c x
j
n
j
j j
Решить задачу это значит найти такие значения x1, x2 ,, xn , удовлетворяющих
условиям (1.2.1) и (1.2.3), при которых целевая функция (1.2.1) принимает
максимальное значение. Если в данной задаче прикладываются еще какие-либо условия
– допустим дается определенный план выпуска какого-то вида продукции, то в систему
ограничений необходимо включить это условие в виде:
x П j ( ) ( j 1,n), j
где П j – это и есть дополнительный план выпуска j-го вида продукции (x j ).
Кроме того можно учесть и другие условия – например, спрос на какую-то
продукцию k . k
x M
Приведем модель математической модели задачи производства ассортимента
продукции.
Фирма производит 4 различных вида галстуков. Один вид дорогой, полностью
шелковый, второй из полиэстера, третий и четвертый виды из смеси полиэстера и
хлопка. Стоимость и возможные запасы трех видов материала в мастерских показаны в
табл. 1.2.2.
9
Таблица 1.2.2
Вид материала Стоимость за ярд ($) Запасы в месяц (ярд)
шелк
полиэстер
хлопок
21
6
9
800
3000
16000
1 ярд=1,514(см).
Фирма установила контракты с различными магазинами на продажу галстуков.
Контрактом установлены минимальные количества изделий каждого вида в месяц. В
табл. 1.3. отражены контрактный спрос в месяц для каждого из четырех типов
галстуков, продажная цена за один галстук и количество ткани, требуемой для пошива
галстуков каждой разновидности.
Таблица 1.2.3
Виды ткани
для галстуков
Цена за
штуку,
($)
Минимальный
контракт в
месяц
Спрос в
месяц
Мастер требует
на пошив 1
галстука, (ярд)
Требование
мастера
1. Полностью
шелковые
6,7 6000 7000 0,125 100%
шелка
2. Полностью
из полиэстера
3,55 10000 14000 0,08 100%
полиэстера
3. Из смеси
полиэстера и
хлопка 1 вида
4,31 13000 16000 0,1 50% 50%
полиэстера
и хлопка
4. Из смеси
полиэстера и
хлопка 2 вида
4,81 6000 8000 0,1 30% 70%
полиэстера
и хлопка
Цель компании – максимальная ежемесячная прибыль. Необходимо решить какой
ассортимент галстуков выпускать.
Пусть x1 число галстуков полностью шелковых,
x2 число галстуков из полиэстера,
x3 число галстуков из смеси 1 вида,
x4 число галстуков из смеси 2 вида.
Для решения задачи составим математическую модель. Определим вид функции
соответствующей прибыли от продажи всего ассортимента галстуков. Для этого
определим чистую прибыль для каждого вида.
1. Для галстука чисто шелкового ( x1) мастер требует 0,125 ярдов шелка по цене
21 доллар за ярд. Поэтому стоимость материала на галстук – 0,125 21 = 2,62 $.
Продажная цена такого галстука 6,7 $. Тогда чистая прибыль будет: 6,7–2,62 = 4,08
доллара за один шелковый галстук.
2. Для галстука полностью из полиэстера мастер требует 0,08 ярдов этого
материала стоимостью 6 долларов за ярд. Тогда стоимость материала для одного
галстука будет: 0,08 6 = 0,48 долларов. Чистая прибыль компании за один галстук
составит: 3,55–0,48 = 3,07 долларов.
3. Для галстука из смеси вида 1 (50% – полиэстера и 50% – хлопка) мастер
требует 0,05 ярда полиэстера по 6 долларов за ярд и 0,05 ярда хлопка по 9 долларов за
ярд, тогда стоимость материала на галстук будет: 0,05 6 + 0,05 9 = 0,3+0,45 = 0,75
долларов. Чистая прибыль получится: 4,31–0,75 = 3,56 долларов.
4. Для галстука из смеси вида 2 (30% – полиэстера и 70% – хлопка) мастер
требует 0,03 ярда полиэстера по 6 долларов за ярд и 0,07 ярда хлопка по 9 долларов за
10
ярд, тогда стоимость материала на галстук будет: 0,03 6 + 0,07 9 = 0,81, и чистая
прибыль за галстук составит: 4,81–0,81 = 4 доллара.
Теперь можем записать математическую модель функции (чистой прибыли) и
системы ограничений
Z 4,08x1 3,07x2 3,56x3 4x4 max
0 1,4.
8500(ммаксималный контракт для галстуков из смеси 2 вида)
6000(мминимальый контракт для галстуков из смеси 2 вида)
16000(ммаксималный контракт для галстуков из смеси из 1 вида)
13000(мминимальый контракт для галстуков из смеси 1 вида)
14000(ммаксималный контракт для галстуков из полиэстера)
10000(мминимальый контракт для галстуков из полиэстера)
7000(ммаксималный контракт для галстуков из шелка (сспрос)
6000(мминимальый контракт для галстуков из шелка)
0,05 0,07 1600(кколичесто яярдо шелка)
0,08 0,05 0,03 3000(кколичесто яярдо полиэстера)
0,125 8000(кколичесто яярдо шелка)
4
4
3
3
2
2
1
1
3 4
2 3 4
1
x j
x
x
x
x
x
x
x
x
x x
x x x
x
j
1.2.2. Задача выпуска продукции с реализацией излишков ресурсов
Допустим имеются два вида ресурсов, при этом b1 запас дефицитного ресурса, а
b2 запас недефицитного ресурса, кроме того a1 j затраты дефицитного ресурса на
выпуск единицы j-го вида продукции, a2 j затраты недефицитного ресурса на выпуск
единицы j-го вида продукции. Тогда математическая модель примет вид
0, ( 1, ).
,
,
max
1
2 2
1
1 1
1
x i n
a x b
a x b
Z c x
j
n
j
j j
n
j
j j
n
j
j j
Так как недефицитный ресурс в оптимальном плане расходуется не полностью, то
имеется остаток этого ресурса в объеме S2.
Если цену одной единицы обозначить P2, тогда выручка от реализации данного
остатка составит P2 S2. .
11
На полученную выручку можно приобрести дополнительно по цене P1 за единицу
дефицитного ресурса в объеме ,
1
2 2
P
P S
тогда, увеличив объем дефицитного ресурса на
величину 2 ,
1
2
1 S
P
P
V математическая модель примет вид:
0, ( 1, ).
,
,
max
1
2 2 2
1
2
1
2
1 1
1
x j n
a x s b
s
p
p
a x b
Z c x
j
n
j
j j
n
j
j j
n
j
j j
или, окончательно, модель можно представить таким образом:
0, ( 1, ).
,
,
max
1
2 2 2
1
2 1
1
2
1
1
x j n
a x s b
s b
p
p
a x
Z c x
j
n
j
j j
n
j
j j
n
j
j j
1.2.3. Задача распределения прибыли предприятия
При решении обычной задачи выпуска продукции получаем объем прибыли.
Необходимо узнать, как распорядиться этой прибылью, чтобы в будущем году
получить еще большую прибыль.
Введем следующие обозначения
b1 стоимость основных производственных фондов (ОПФ),
b2 стоимость фонда оплаты труда (ФОТ),
b3 стоимость материальных ресурсов,
a1 j затраты ОПФ на выпуск 1 единицы j-го вида продукции,
a2 j затраты ФОТ на выпуск 1 единицы j-го вида продукции,
a3 j затраты материальных ресурсов на выпуск 1 единицы j-го вида продукции.
Математическая модель такой задачи примет вид
n
j
j j
Z c x
1
max
12
0, ( 1, ).
1
3 3
1
2 2
1
1 1
x j n
a x b
a x b
a x b
j
n
j
j j
n
j
j j
n
j
j j
Полученная прибыль предприятия ( Zmax ) распределяется следующим образом:
q-я часть прибыли идет на уплату всевозможных налогов.
Остальная часть: (1–q) идет в собственное использование.
Допустим:
1 часть, прибыли которая идет на воспроизводство основных
производственных фондов,
2 часть прибыли, идущая на увеличение фонда оплаты труда,
3 часть прибыли, которая идет на приобретение дополнительных
материальных ресурсов.
Примем 1 2 3 1, тогда
1(1 q)Z показатель увеличения основных производственных фондов (в
стоимостном выражении),
2 (1 q)Z показатель увеличения фонда оплаты труда,
3 (1 q)Z показатель увеличения запасов ресурсов (в стоимостном выражении).
Тогда исходная модель примет вид:
0, ( 1, ).
1
(1 )
(1 )
(1 )
max
1 2 3
1
3 3 3
1
2 2 2
1
1 1 1
1
*
x j n
a x b q Z
a x b q Z
a x b q Z
Z c x
j
n
j
j j
n
j
j j
n
j
j j
n
j
j j
Задача решается несколько раз, изменяя части 1, 2 и 3.Выбирается лучший
вариант распределения средств.
Решение задачи представляет интерес не толь с точки зрения получения прибыли,
но и с точки зрения формирования бюджетов различных уровней.
13
Общий объем отчислений в бюджет зависит не только от ставки налога, но и от
объема полученной прибыли.
Исходя из этого, можно предположить, что величина отчислений не только не
уменьшается, но и даже возрастет, при уменьшении ставки налогообложения.
1.2.4. Задача выбора вариантов вложенных средств
Корпорации предлагается сформировать инвестиционную программу. Эффект от
реализации проекта пропорционален доле реализации этого проекта. Требуется
определить каким проектам отдать предпочтение при инвестировании, чтобы эффект от
осуществления этих проектов (или их доли) был бы максимальным.
Введем следующие обозначения:
It объем капитала на осуществление проектов в году t.
Atj инвестиционные затраты в году t на осуществление проекта в целом j-го
вида.
C j эффективность при осуществлении j-го проекта в целом.
Тогда математическая модель данной задачи примет следующий вид:
Z c1x1 c2 x2 cn xn.
Из n проектов на m лет при условии, что инвестиционные затраты не должны
превышать установленный лимит средств. Объем инвестиций по годам ( It ),
инвестиционные затраты по проектам в каждом году ( Atj ), а также норма
эффективности осуществления каждого проекта в целом (C j ), даны в табл. 1.2.4.
Таблица 1.2.4
… …
a12
2
… …
…
…
…
…
…
a11
Норма
эффективности
проекта
Лимит
капитала
по годам
1
Годы
2
1 j n
t
m am2
a2j a2n
a1 j
at1
a1n
am1
a21
amj
a22
c1 c2 c j cn
I1
amn
I2
…
…
…
…
…
…
…
…
…
…
…
…
…
… …
…
… …
Инвестиционные затраты по проектам
Im
at2 atn
…
atj It
Рассматриваемые проекты независимы, могут быть реализованными только один
раз. Допускается частичная реализация, при этом
14
1 1 2 2 .
1 1 2 2
21 1 22 2 2 2 2
11 1 12 2 1 1 1
m m ij j mn n m
t t tj j tn n t
j j n n
j j n n
a x a x a x a x I
a x a x a x a x I
a x a x a x a x I
a x a x a x a x I
0 x j 1, ( j 1,n )
или
0 1 ( 1, ).
( 1, )
max
1
1
x j n
a x I t m
Z c x
j
n
j
tj j t
n
j
j j
1.2.5. Задача о кредитной политике банка (конкретный пример)
Банк, представляющий полный набор банковских услуг, находится в процессе
формирования портфеля кредитов объемом 15 млн. долларов. В табл. 1.2.5
представлены возможные типы банковских кредитов.
Таблица 1.2.5
Типы кредита Ставка процента Вероятность безнадежных
долгов
Кредиты физическим
лицам
0,15 0,1
Кредиты на покупку
автомобилей
0,12 0,08
Кредиты на покупку жилья 0,11 0,04
Сельскохозяйственные
кредиты
0,12 0,05
Коммерческие кредиты 0,1 0,01
Безнадежные долги считаются невозвратными, потому они должны вычитываться
из возможного дохода.
Конкурентная борьба с другими финансовыми институтами вынуждает банк не
менее 45% капитала помещать в сельскохозяйственные и коммерческие кредиты. Для
содействия строительной индустрии своего региона банк планирует вложить в кредиты
на покупку жилья не менее 50% от общей суммы кредитов физических лиц, на покупку
автомобилей и жилья. Банк также поддерживает государственную политику,
указывающую, что отношение безнадежных долгов ко всей сумме кредитов не должно
превышать 0,045.
Все кредиты выделяются примерно в одно время, что позволит игнорировать
временной фактор в процессе размещения капитала в различные кредиты. Банк желает
максимизировать чистую прибыль, т.е. разность между доходом от инвестируемых
сумм и суммой невозвращенных кредитов. Поскольку безнадежные долги считаются
невозвратимыми, они вычитаются как из инвестируемых сумм, так и общей прибыли.
15
Определим переменные создаваемой модели.
X1 кредиты физическим лицам.
X2 кредиты на покупку автомобилей.
X3 кредиты на покупку жилья.
X4 сельскохозяйственные кредиты.
X5 коммерческие кредиты.
Тогда математическая модель задачи примет следующий вид:
Z 0,15 (0,9x1) 0,12 (0,92x2) 0,11 (0,96x3 ) 0,12 (0,95x4 ) 0,1 (0,99x5 )
0,1x1) 0,08x2 0,04x3 0,05x4 0,01x5.
После приведения подобных членов
Z 0,35x1 0,0304x2 0,0256x3 0,074x4 0,089x5 max .
Задача имеет пять ограничений:
1. Ограничение общей суммы кредитов
x1 x2 x3 x4 x5 15.
2. Ограничение на сельскохозяйственные и коммерческие кредиты
x4 x5 0,45 15 или x4 x5 6,75.
3. Ограничения кредитов на покупку жилья
x3 0,5(x1 x2 x3 ) или 0,5x1 0,5x2 0,5x3 0.
4.Ограничения на невозвращенные кредиты
0,045
1 2
0,1 1 0,08 2 0,04 0,05 0,01
3 4 5
3 4 5
x x x x x
x x x x x
или
0,055x1 0,035x2 0,005x3 0,005x4 0,035x5 0.
5. Условие неотрицательности переменных
x j 0 ( j 5).
1.2.6. Транспортная задача
Имеются m поставщиков A1, A2 ,, Amоднородного или взаимозаменяемого груза
в объемах соответственно a1,a2 ,,am и n потребителей B1, B2 ,, Bn , спрос на этот
груз у которых соответственно b1,b2 ,,bn.
Известны также затраты на перевозку единицы груза для каждой пары
«поставщик-потребитель».
Найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы
1) мощности всех поставщиков были реализованы;
2) спросы всех потребителей были удовлетворены;
3) суммарные затраты на перевозку были бы минимальными.
Все эти условия могут быть выполнены только, если мощности поставщиков
совпадают со спросом потребителей.
Составим математическую модель данной задачи.
Для этого все исходные данные задачи поместим в табл. 1.2.6.
16
Таблица 1.2.6
… …
… … … … …
…
… …
…
…
… … … …
… …
… …
… …
… …
xmn
xin
x 2n
x1n
xmj
xij
x2 j
x1j
xm2
xi2
x22
x12
xm1
xi1
x21
x11
mj cmn c
ij cin c
c2n
c1n
c2 j
c1 j
ci2
c22
cm2
c12
cm1
ci1
c21
c11
b1 b2 b j bn
am
ai
a2
a1
B1 B2 B j Bn
Поставщики
Потребители
A1
A2
Ai
Am
где cij затраты на перевозку единицы однородного груза от i-го поставщика j-му
потребителю.
xij объем поставки такого груза от i-го поставщика j-му потребителю.
Для того, чтобы были реализованы мощности всех поставщиков и при этом
удовлетворен спрос всех потребителей, должно выполняться следующее условие:
n
j
j
m
i
ai b
1 1
.
Если это условие выполняется, то задачу называют «закрытого» типа.
Целевая функция представляет собой затраты на перевозку, т.е. имеет вид
min.
11 11 12 12 ij ij mn mn
Z c x c x c x c x
0 ( 1, ; 1, )
min
1
1
1 1
x i m j n
x b
x a
Z C X
ij
m
j
ij j
n
j
ij i
n
j
ij ij
m
i
или
17
все 0 ( 1, ; 1, ).
Ограничени я по спросу
Ограничени я по запасам ресурсов (сстрокам
1 2
1 2
12 22 2 2 2
11 21 1 1 1
1 2
1 2
21 22 2 2 2
11 12 1 1 1
x i m j n
x x x x b
x x x x b
x x x x b
x x x x b
x x x x a
x x x x a
x x x x a
x x x x a
ij
n n in mn n
j j ij mj j
i m
i m
m m mj mn m
i i ij in i
j n
j n
1.2.7. Использования мощностей оборудования
Предприятие имеет m моделей оборудования различных мощностей. Задан план
по времени и номенклатуре: Ti время работы i-го оборудования; должно быть
выпущено не менее П j единиц продукции j-го вида.
Необходимо составить такой план работы оборудования, чтобы обеспечить
минимальные затраты на производство, если известны производительность каждого i-
го оборудования по выпуску j-го вида продукции ( aij ) и стоимость единицы времени,
затрачиваемого i-м оборудованием на выпуск j-го вида продукции (Cij ).
Задача решается на минимум затрат на производство (функция Z).
,
1
min
1
m
i
Z C X
n
j
ij ij
при следующих ограничениях
, ( 1, ) ограничение по заданному количеству продукции - го вида
1
aij xij П j j n j
m
i
, ( 1, ) ограничение по времени работы - го вида оборудования
1
xij Ti i m i
n
j
Кроме того xij 0, (i 1,m; j 1, n) .
Моделей задач линейного программирования можно привести еще достаточное
количество: задача об оптимальном раскрое, задача о диете, задача о составлении
жидких смесей и т.д.
Вывод:
Мы рассмотрели ряд задач линейного программирования. Обобщая их можно
сделать такой вывод:
18
1. Линейная функция может стремиться как к максимуму, так и к минимуму.
2. Ограничения могут быть выражены равенствами и неравенствами любого
смысла ( , ).
3. Переменные в задачах всегда неотрицательны.
1.3. Математическая постановка задач линейного программирования
1.3.1. Общая задача линейного программирования
Найти совокупность значений переменных х1, х2, …, хn, удовлетворяющих системе
ограничений:
1 1 2 2 0,
1,1 1 1,2 2 1, 1,0,
1 1 2 2 0,
11 1 12 2 1 1 10,
m m mn n m
l l l n n l
l l ln n l
n n
a x a x a x a
a x a x a x a
a x a x a x a
a x a x a x a
(1.3.1.1)
x1 0, x2 0, , xn 0, (1.3.1.2)
для которой линейная функция
Z c1x1 c2 x2 cn xn (1.3.1.3)
достигает экстремума.
Приведем необходимые для дальнейшего определения.
1. Функция Z называется целевой функцией.
2. Всякое неотрицательное решение системы (2.1) будем называть допустимым
решением или допустимым планом. Допустимый план обычно записывается в
3. виде n мерного вектора X ( х1, х2, …, хn).
4. Совокупность всех допустимых решений называется множеством (или
областью) допустимых решений.
5. Допустимое решение, для которого целевая функция достигает экстремума,
называется оптимальным решением или оптимальным планом.
Из определения следует, что X0 оптимальный план при Z max, если для
любого X из множества допустимых планов выполняется неравенство Z X0 Z X .
1.3.2. Стандартная задача линейного программирования
Найти совокупность значений переменных х1, х2, …, хn, удовлетворяющих системе
неравенств:
1 1 2 2 0
21 1 22 2 2 20,
11 1 12 2 1 1 10,
m m mn n m
n n
n n
a x a x a x a
a x a x a x a
a x a x a x a
19
и условиям неотрицательности:
x1 0, x2 0, , xn 0,
для которых функция
Z c1x1 c2 x2 cn xn
достигает экстремума или более кратко математическую модель задачи можно
представить в виде
max
1
n
j
Z c j x j (1.3.2.1)
n
j
aij x j ai
1
0, (i 1, m), (1.3.2.2)
x j 0, ( j 1, n), (1.3.2.3)
где выражение (1.3.2.1) – целевая функция,
(1.3.2.2) – система ограничений,
(1.3.2.3) – неотрицательность переменных.
1.3.3. Основная задача линейного программирования
Найти совокупность переменных х1, х2, …, хn, удовлетворяющих системе уравнений:
n
j
aij x j ai
1
0, (i 1, m),
и условия неотрицательности x j 0, ( j 1, n)
для которых целевая функция
n
j
Z c j x j
1
достигает экстремума.
Вопросы для самопроверки
1. Какова постановка стандартной, общей, основной задач линейного
программирования?
2. Какое решение называется допустимым?
3. Какое решение называется оптимальным?.
1.3.4. Системы линейных уравнений
Систему уравнений первой степени вида:
1 1 2 2 0
21 1 22 2 2 20,
11 1 12 2 1 1 10,
(1.3.4.1)
m m mn n m
n n
n n
a x a x a x a
a x a x a x a
a x a x a x a
называется системой m линейных уравнений c n неизвестными. Решить систему
(1.3.4.1) это значит найти такие значения переменных x1, x2 ,..., xn , при которых каждое
уравнение системы обращается в тождество. Решение можно записать в виде вектора с
соответствующими координатами
X (α1, α2, …, αn).
20
Систему (1.3.4.1) можно записать более кратко:
( 1, ).
1
0 , i m
n
j
aij x j ai (1.3.4.2)
Решение системы (1.3.4.2) называют допустимым, если в нем все неизвестные
неотрицательны.
Система (1.3.4.1) в матричном виде:
A X A0 ,
где матрица
;
1 2
21 22 2
11 12 1
m m mn
n
n
a a a
a a a
a a a
A ;
0
20
10
0
am
a
a
A
.
2
1
xn
x
x
X
Будем считать, что число уравнений меньше числа неизвестных (m n). Выберем из n
неизвестных какую либо группу переменных x1, x2 ,..., xn . Допустим, что
определитель, составленный из коэффициентов при этих неизвестных системы
линейных уравнений (3.1), отличен от нуля
0.
1 2
21 22 2
11 12 1
m m mn
n
n
a a a
a a a
a a a
Определение 1. Любые m неизвестных системы уравнений (1.3.4.1) называются
базисными, если определитель, составленный из коэффициентов при этих
неизвестных, отличен от нуля.
В этом случае неизвестные x1, x2 ,..., xm называют базисными, а остальные
неизвестные хm+1, хm+2, …, хn свободными.
Предположим, что свободные переменные равны нулю, т.е. xm 1 0,
xm 2 0,…, xn 0, тогда система уравнений (1.3.4.1) примет вид
1 1 2 2 0.
21 1 22 2 2 20,
11 1 12 2 1 1 10,
(1.3.4.3)
m m mm m m
m m
m m
a x a x a x a
a x a x a x a
a x a x a x a
Так как определитель этой системы отличен от нуля, то она имеет единственное
решение вида
X (α1, α2, …, αm)
Тогда система уравнений (1.3.4.1) будет иметь решение:
X (α1, α2, …, αm, 0, …, 0).
Это решение является базисным решением системы уравнений (1.3.4.1).
21
Определение 2. Базисным решением системы m уравнений с n неизвестными
называется такое решение, в котором свободные неизвестные равны нулю.
Определение 3. Система линейных уравнений называется системой с базисом,
если в каждом уравнении содержится неизвестное с коэффициентом, равным единице,
отсутствующее во всех остальных уравнениях.
Система вида
, 1 1 0
2 2, 1 1 2 20,
1 1, 1 1 1 10,
(1.3.4.4)
m m m m mn n m
m m n n
m m n n
x a x a x a
x a x a x a
x a x a x a
является примером системы с базисом, в которой переменные х1, х2, …, хm, являю, так как
определитель
1 0.
0 0 1
0 1 0
1 0 0
Система с базисом всегда имеет решение (т.е. совместна) и базисным решением
системы будет
X (a10, a20, …, am0, 0, …, 0).
1.3.5. Метод Жордана Гаусса
Решения системы линейных уравнений
Рассмотрим систему линейных уравнений вида
1 1 2 2 0.
1 1 2 2 0,
1 1 2 2 0,
21 1 22 2 2 2 20,
11 1 12 2 1 1 10,
m m mp p mn n m
q q qp p qn n q
i i ip p in n i
p p n n
p p n n
a x a x a x a x a
a x a x a x a x a
a x a x a x a x a
a x a x a x a x a
a x a x a x a x a
(1.3.5.1)
Приведем данную систему к системе с базисом путем элементарных
преобразований по методу Жордана-Гауса.
Преобразования удобнее производить в таблице Гаусса, в которую заносятся
коэффициенты при неизвестных и свободные члены системы.
Следовательно системе линейных уравнений (1.3.5.1) соответствует табл. 1.3.5.1.
22
Таблица 1.3.5.1
х1 х2 xk xp xn ai0
a11
a21
ai1
aq1
am1
a12
a22
ai2
aq2
am2
a1k
a2k
aik
aqk
amk
a1p
a2p
aip
amp
a1n
a2n
ain
aqn
amn
a10
a20
ai0
aq0
am0
Алгоритм метода Жордана Гаусса
1. Составим таблицу Гаусса.
2. Выбираем разрешающий элемент aqp 0 из коэффициентов при неизвестной
xp. Строка и столбец, в которых находится этот разрешающий элемент, называют
разрешающими.
3. Элементы разрешающей строки делим на разрешающий элемент.
4. Элементы разрешающего столбца, не принадлежащие разрешающей строке,
обратим в нули.
5. Элементы остальных строк и столбцов пересчитываем по правилу
прямоугольника.
Из табл. (1.3.5.1) видим i ю и q ю строки и k й и p й столбцы, получим
прямоугольник (рис.1).
A B
разрешающая строка
разрешающий столбец
aij
aqk
j
aqp
j
aip
D C
Рис.1
Для вычисления
'
aik последующей таблицы Гаусса, нужно перемножить
элементы, стоящие на главной диагонали прямоугольника АВСD (диагональ проходит
через разрешающий элемент aqp ), вычесть из полученного результата произведение
элементов, стоящих по другой диагонали (СВ) и разность разделить на разрешающий
элемент aqp , т.е
.
qp
ik qp qk ip
ik
a
' a a a a a
Приведенное правило и есть “правило прямоугольника”. Переход от одной
таблицы к другой по алгоритму будем называть итерацией. После первой итерации
получаем табл. 1.3.5.2.
aqp
23
Таблица 1.3.5.2
х1 х2 xk xp xn ai0
'
a11
'
a21
'
ai1
'
aq1
'
am1
'
a12
'
a22
'
ai2
'
aq2
'
am2
'1
a k
'2
a k
'
aik
'
aqk
'
amk
0
0
0
1
0
'1
a n
'2
a n
'
ain
'
aqn
'
amn
'
a10
'
a20
'
ai0
'
aq0
'
am0
Алгоритм применяет до тех пор, пока в каждой строке не получим базисные
переменные.
Замечание 1. Если после выполнения итераций, в какой-либо строке все
элементы обратятся в ноль, то соответствующее уравнение данной строки можно
отбросить, так как оно является линейной комбинаций всех остальных уравнений.
Замечание 2. Если в какой-либо строке коэффициенты при всех неизвестных
обратятся в ноль, а свободный член ai0 отличен от нуля, то система уравнений
несовместна.
Пример 1. Привести систему уравнений к системе с базисом и найти базисное
решение системы:
3 4 5 7.
2 2 5,
1 2 3 4
1 2 3 4
x x x x
x x x x
Решение. Воспользуемся алгоритмом Жордана-Гауса и получим несколько
таблиц, соответствующих каждой итерации
Таблица 1.3.5.3
х1 х2 х3 х4 ai0
1
3
2
4
1
–5
1
1
5
7
1
0
2
2
1
–8
2
7
5
8
2 8 7 8.
2 2 5,
2 3 4
1 2 3 4
x x x
x x x x
1
0
0
10
7
4
5
3,5
3
4
4 3,5 4.
7 5 3,
2 3 4
1 3 4
x x x
x x x
В первой таблице был выбран разрешающий элемент 1,
11
a следовательно
разрешающими будут первая строка и первый столбец. Делим элементы первой строки
(разрешающей) на разрешающий элемент равный 1 и результат записываем в первую
строку последующей таблицы. В первом столбце (разрешающем) последующей
таблицы запишем нуль. Остальные элементы этой таблицы рассчитаем по правилу
прямоугольника
24
2;
1
1 4 3 2
22
a' 8;
1
1 (5) 3 1
23
a' 7;
1
1 ( 1) 3 2
24
a'
8.
1
1 7 3 5
10
a'
Выполнив еще одну итерацию, получим систему уравнений с базисом
4 3,5 4,
7 5 3,
2 3 4
1 3 4
x x x
x x x
где х1, х2, базисные неизвестные, х3, х4 свободные неизвестные, тогда базисное
решение системы будет х3 = 0; х4 = 0; х1 = –3; х2 = 4 или Xб ( 3; 4; 0; 0).
1.3.6. Канонические системы. Преобразование однократного замещения
Определение 1. Линейная система уравнений называется канонической, если она
является системой с базисом и свободные члены этой системы неотрицательны.
Система вида
, 1 1 0.
2 2, 1 1 2 20,
1 1, 1 1 1 10,
m m m m mn n m
m m n n
m m n n
x a x a x a
x a x a x a
x a x a x a
(1.3.6.1)
есть каноническая система, если ai0 0, при i = 1, 2, …, m.
Определение 2. Базисное допустимое решение системы называется опорным
решением.
Первоначальным опорным решением системы уравнений (5.1) будет решение
вида
X0 (a10, a20, , am0 , 0)
(свободные неизвестные этой системы обращаются в нуль, т.е. xm 1 0, xm 2 0,…,
xn 0 ).
Чтобы найти все другие опорные решения системы (5.1), необходимо перейти к другой
канонической системе, эквивалентной системе (5.1).
Определение 3. Переход от одной канонической системы к эквивалентной ей
канонической системе, в результате которого одно из базисных неизвестных
заменяется свободным неизвестным, называется преобразованием однократного
замещения.
Теорема. Если в канонической системе уравнений среди коэффициентов при
каком либо свободном неизвестном есть хотя бы один положительный, то возможен
переход к новой канонической системе, равносильной данной, в которой указанное
свободное неизвестное становится базисным. При этом одно из базисных переменных
станет свободным.
1.3.7. Алгоритм преобразования однократного замещения
1. Каноническую систему записываем в виде таблицы Гаусса, добавив столбец,
указывающий базисную переменную в соответствующем уравнении, и столбец θ (где θ
– это отношение свободных членов системы уравнений к положительным элементам
выбранного разрешающего столбца).
2. Выбираем разрешающий столбец среди столбцов коэффициентов при
свободных неизвестных, в котором есть хотя бы один положительный элемент.
25
3. Разрешающую строку выбираем по минимальному отношению θ.
4. На пересечении разрешающего столбца и разрешающей строки находится
разрешающий элемент.
5. Перейдем к последующей таблице по методу Жордана Гаусса.
Пример 1. Дана каноническая система
2 2.
3 5,
2 2 4,
2 5
3 4 5
1 4 5
x x
x x x
x x x
В системе х1, х2, х3 – базисные переменные, а х4, х5 свободные переменные.
Исходное опорное решение: х4 = 0; х5 = 0; х1 = 4; х3 = 5; х2 = 2 или
X1 (4, 2, 5, 0, 0).
Найти следующее опорное решение.
Для того, чтобы найти следующее опорное решение необходимо выполнить
одно преобразование однократного замещения.
Составим таблицу Гаусса.
Таблица 1.3.7.1
Базис ai0 x1 x2 x3 x4 x5 θ
х1
x3
x2
4
5
2
1
0
0
0
0
1
0
1
0
2
3
0
-2
1
2
5/1 =5
2/2 = 1 → min
x1
x3
x5
6
4
1
1
0
0
1
1/2
1/2
0
1
0
2
3
0
0
0
1
После преобразования первоначальной системы получим второе опорное решение
X2 (6, 0, 4, 0,1).
Выбор разрешающего столбца определяет то свободное неизвестное, которое
становится базисным, а выбор разрешающей строки определяет неизвестное, которое
становится свободным.
Вопросы и задачи для самопроверки
1. Какие неизвестные называются базисными, какие свободными?
2. Какое решение называют базисным?
3. Какое решение называют опорным?
4. Какую систему можно считать системой с базисом?
5. Как составляется таблица Гаусса.
6. Каков алгоритм метода Жордана-Гаусса.
7. Какая система уравнений является канонической?
8. Какие преобразования называют преобразованиями однократного замещения?
9. Каков алгоритм преобразования однократного замещения?
10. Привести систему к системе с базисом
7 3 2 8.
3 2 4 8 6,
1 2 3 4 5
1 2 3 4 5
x x x x x
x x x x x
11. Найти два опорных решения системы
26
2 2 4.
2 2 5,
2 3,
3 1,
1 3 6
1 2 3
1 3 5
1 4
x x x
x x x
x x x
x x
1.4. Общая теория линейного программирования
В задачах линейного программирования требуется найти оптимальный план,
который является определенной системой чисел. Исходные данные в таких задачах
также представляют собой некоторые числовые совокупности. Поэтому и
рассматриваем n мерные векторы и действия над ними.
Определение 1. Упорядоченный набор n чисел называется n мерным вектором
или n мерной точкой. Числа х1, х2, …, хn называются координатами вектора или точки.
N мерный вектор будем записывать следующим образом:
X (х1, х2, …, хn).
Определение 2. Суммой двух n мерных векторов называется третий вектор,
каждая координата которого есть сумма соответствующих координат слагаемых
векторов.
Если X (х1, х2, …, хn) и Y (y1, y2, …, yn),то
X Y (х1+y1, х2+y2, …, хn+yn).
Определение 3.Произведением вектора X на число называется новый вектор
X, координаты которого получаются умножением каждой координаты исходного
вектора на число .
Если X (х1, х2, …, хn), то X (λх1, λх2, …, λхn).
Перечисленные линейные операции обладают следующими свойствами:
1. Переместительным: X Y Y X,
X X .
2. Сочетательным: X (Y Z) (X Y) Z,
( X) ( X) ( )X.
3. Распределительным: (X Y) X Y,
X( ) X X .
Определение 4. Множество n мерных векторов, для которых определены
операции сложения и умножения вектора на число, называется n мерным векторным
пространством.
Введем еще операцию над n мерными векторами скалярное произведение.
Определение 5. Скалярным произведением двух векторов называется число,
равное сумме произведений соответствующих координат этих векторов:
X Y x1y1 x2 y2 xn yn.
1.4.1. Выпуклые множества
Определение 1. Множество точек n мерного пространства называется выпуклым,
если любые две точки данного множества можно соединить отрезком, который
целиком принадлежит данному множеству.
Например, множество на рис. 2 выпуклое, а на рис. 3 невыпуклое.
27
Рис. 2 Рис. 3
А B
A B
Из определения ясно, что понятие выпуклого множества связано с понятием отрезка в
n мерном пространстве. Введем его понятие. Рассмотрим в пространстве две точки М1
и М2 (рис. 4). Радиусы векторы этих точек обозначим X1 и X 2.
O
Рис. 4
X 2
М
X
М1
М2
X 0 X1
Определение 2. Отрезком n мерного пространства, соединяющим концы
векторов X1 и X2 , называется множество X точек этого пространства,
удовлетворяющих соотношению:
X tX1 (1 t)X2,
где 0 t 1.
Приведем следующую теорему.
Теорема. Пересечение выпуклых множеств есть также выпуклое множество.
Среди точек выпуклого множества можно выделить внутренние, граничные и
крайние (угловые) точки.
Рис. 4
Определение 3. Точка X0 называется граничной точкой множества, если в
любом шаре сколь угодно малого радиуса с центром в точке X0 содержатся как точки
множества, так и точки, не принадлежащие множеству.
28
Определение 4. Множество называется замкнутым, если ему принадлежат все его
граничные точки.
Определение 5. Крайними или угловыми точками называются те точки X
выпуклого множества, для которых не существует точек X1 и X2 этого множества
таких, что X tX1 (1 t)X2, где 0 t 1.
Графически это означает, что крайняя точка не является внутренней ни для какого
отрезка, целиком принадлежащего множеству.
Например, для круга любая точка ограничивающей его окружности является
крайней. Крайними точками являются все вершины выпуклого многогранника.
Определение 6. Множество называется ограниченным, если существует шар
конечного радиуса с центром в начале координат, который целиком содержит данное
множество.
Выпуклое, замкнутое, ограниченное множество, имеющее конечное число крайних
точек, называется многогранником. В случае, когда размерность пространства больше
трех, многогранники нельзя изобразить графически, поэтому представляет интерес их
аналитическое представление.
Определение 7. Линейная комбинация
t1X1 t2 X2 tk Xk
векторов X1 , X2 , …, X k называется выпуклой, если числа ti удовлетворяют
условию:
1,
1
1
k
i
t ti 0, (i = 1, 2, …, к).
Теорема 1 (о представлении выпуклого множества).
Любая точка выпуклого, замкнутого, ограниченного множества есть выпуклая
линейная комбинация его крайних точек.
X1
X1
X1
X1
X5
X 4
X3
Xk
X 2
X1
X
Рис.5
Если X1 , X 2. , …, X k крайние точки множества, то любая точка X этого
множества
X t1 X1 t2 X2 tk Xk ,
где 1,
1
1
k
i
t ti 0, (i = 1, 2, …, к).
29
Теорема 2. Множество решений системы линейных алгебраических уравнений,
есть выпуклое множество
Доказательство:
Рассмотрим систему линейных алгебраических уравнений
.
(1.4.1.1)
1 1 2 2 0
21 1 22 2 2 20,
11 1 12 2 1 1 10,
m m mn n m
n n
n n
a x a x a x a
a x a x a x a
a x a x a x a
Введем обозначения
a1 (a11, a12, , a1n ),
a2 (a21, a22, , a2n ),
(1.4.1.2)
am (am1, am2, , amn ),
X (x1, x2, , xn ).
Тогда система (1.4.1.1) примет вид
0.
2 20,
1 10,
am X am
a X a
a X a
(1.4.1.3)
Рассмотрим i-е уравнение системы (1.4.1.2)
ai X ai0.
Пусть X1 и X2 две произвольные точки множества решения данного
уравнения. Следовательно,
ai1 X1 ai0 , (1.4.1.4)
ai X2 ai0 .
Рассмотрим произвольную точку X, лежащую на отрезке, соединяющем две
точки множества решения X1 и X2 , но
X tX1 (1 t)X2.
Подставим значение вектора X в данное уравнение
ai X ai tX1 (1 t)X2 tai X1 (1 t)ai X2 tai0 (1 t)ai0 tai0 ai0 tai0 ai0.
Итак, ai X ai0 .
Следовательно, X является также решением данного уравнения. А это значит,
что вместе с любыми двумя точками X1 и X2 множеству решений данного уравнения
принадлежат все точки отрезка, соединяющего эти точки, это значит, множество
решений системы алгебраических уравнений есть выпуклое множество.
Аналогично доказывается, что множество решений других уравнений также есть
множество выпуклое.
30
А множество решений системы этих уравнений есть пересечение выпуклых
множеств, которое (по предыдущей теореме) является множеством выпуклым.
Аналогично можно доказать, что множество решений системы линейных
неравенств есть множество выпуклое.
Следовательно, множество решений системы ограничений задачи линейного
программирования:
1 1 2 2 0
21 1 22 2 2 20,
11 1 12 2 1 1 10,
(1.4.1.5)
m m mn n m
n n
n n
a x a x a x a
a x a x a x a
a x a x a x a
x j 0, (j = 1, 2, …, n) (1.4.1.6)
есть пересечение множеств решений системы линейных уравнений (1.4.1.5), (1.4.1.6). А
это множество будет выпуклым.
Теорема 3. Каждому опорному решению системы ограничений задачи линейного
программирования соответствует крайняя точка множества допустимых решений
системы ограничений.
Доказательство.
Пусть X опорное решение системы (1.4.1.5)-(1.4.1.6)
X ( 1, 2 ,..., n ,0,...,0) .
Докажем, что X совпадает с одной из крайних точек множества доступных
решений системы.
Допустим противное, что опорное решение не совпадает ни с одной из крайних
точек указанного множества.
Тогда найдутся такие точки данного множества
X1( 1, 2 ,..., n ) и X2 ( 1, 2 ,..., n ) , которые являются концами отрезка, внутри
которого лежит точка X , тогда
X X1t (1 t)X2, 0 t 1.
Из последнего уравнения следует
0 (1 ) .
.......... .......... .......... ........
0 (1 ) ,
(1 ) ,
.......... .......... .......... ........
(1 ) ,
1 1
1
1 1 1
n n
m m
m m m
t t
t t
t t
t t
По определения t > 0; t < 0 или (1–t) > 0.
Кроме того i 0, i 0, так как X1 и X2 – принадлежат множеству
допустимых решений.
Тогда из соотношений
n n
m m
t t
t t
0 (1 )
.......... .......... .......... ........
0 1 (1 ) 1,
следует, что m 1 0; m 1 0; n 0; n 0, т.е. i 0; i 0; (i m 1,..., n).
31
Таким образом, X1( 1, 2 ,..., m,0,...,0); X2 ( 1, 2 ,..., m,0,...,0) также являются
опорными решениями системы. X ( 1, 2 ,..., n ,0,...,0) – также опорное решение
системы (по условию теоремы). Мы получим три опорных решения системы с m
неизвестными X1,…,Xm вида
1 1 2 2 0.
21 1 22 2 2 20,
11 1 12 2 1 1 10,
m m mm m m
m m
m m
a x a x a x a
a x a x a x a
a x a x a x a
Но согласно теореме Крамера данная система может иметь только единственное
решение. И потому X1 X2 X и значит X крайняя точка.
Теорема 4. Каждой крайней точке множества допустимых решений системы
ограничений соответствует опорное решение этой системы.
Теорема 5. Множество допустимых решений системы ограничений основной
задачи линейного программирования есть выпуклый многогранник.
Теорема 6. (об экстремуме целевой функции)
Целевая функция достигает своего опорного значения в одной из крайних точек
множества допустимых решений системы ограничений.
Доказательство.
Рассмотрим основную задачу линейного программирования.
0.
1
0 ,
j
ij j i
x
n
j
a x a
(1.4.1.7)
n
j
Z c j x j
1
max . (1.4.1.8)
Допустим, что задача решается на максимум. Известно, что множество
допустимых решений системы (1.4.1.7) есть многогранник.
Пусть X1, X2 ,..., Xk , крайние точки этого многогранника. Каждая из них является
решением, тогда
Z(X1) Z(X).
Допустим, что X0 не совпадает ни с одной из крайних точек многогранника. Так
как множество решений выпуклое, то x0 можно представить в виде выпуклой
линейной комбинации крайних точек, X1, X2 ,..., Xk .
1, 0.
1
0 1 1 2 2 k k , где k ti
k
i
X X t X t X t t
Обозначим Z(X0 ) M, так как Z – линейная функция, рассчитаем
( ) ( ) ( ) .
( ) ( ) ( ) ( )
1 1 2 2
1 1 2 2 0 1 1 2 2
t Z X t Z X t Z X M
Z X t X t X t Z X Z X t Z X t Z X t
k k
k k k k
Пусть среди Z(X1),Z(X2 ),..., Z(Xk ) наибольшим будет Z(Xl ).
Заменим все Z(Xi ), i 1, k на Z(Xl ), l 1, k, тогда уравнение (2.10) примет вид:
32
Z(X0 ) t1Z(Xl ) t2Z(Xl ) tk Z(Xl ) (t1 t2 tk )Z(Xl )
или
Z(X0 ) Z(Xl ), так как 1, 0.
1
k ti
k
i
t
Из последнего неравенства следует, что X0 не является оптимальным решением
системы, что противоречит нашему предположению x0 оптимальный план задачи.
Следовательно, если задача имеет решение, то оно совпадает с одной из крайних
точек.
Теорема 7. (об альтернативном оптимуме)
Если целевая функция достигает своего оптимального решения в нескольких из
крайних точках, то она достигает его в любой точке множества, являющейся выпуклой
линейной комбинацией этих крайних.
Доказательство.
Допустим, целевая функция достигает максимума в точках X1, X2 ,..., Xm, тогда
Z(X1) Z(X2 ) Z(Xm) M.
Пусть X выпуклая линейная комбинация крайних точек
1, 0.
1
1 1 2 2 m m, где i ti
m
i
X t X t X t X t
Тогда
1.
1
( ) , так как
( ) ( ) ( ) ( )
1 2
1 1 2 2 1 1 2 2
m
i
t t t M M t
Z X Z t X t X t X t Z X t Z X t Z X
m i
k k m m
Таким образом, X является тоже оптимальным решением.
Теорема 8. (основная теорема линейного программирования)
Если задача (1.4.1.7)-(1.4.1.8) имеет оптимальное решение, то оно совпадает с
одним из опорных решений системы (1.4.1.7).
Доказательство.
Из предпоследней теоремы оптимальное решение совпадает с одной из крайних
точек, а каждая крайняя точка есть опорное решение системы. Что и требовалось
доказать.
Вопросы для самопроверки:
1. Что называется n мерным вектором?
2. Что называется n мерным векторным пространством?
3. Какое множество называется выпуклым?
4. Что такое отрезок n мерного векторного пространства?
5. Какая точка называется крайней?
6. Что называется выпуклой линейной комбинацией точек?
7. Дать формулировку теоремы о представлении выпуклого множества.
8. Сформулировать теорему о множестве решений системы алгебраических
уравнений.
9. Сформулировать теорему о связи крайних точек с опорными решениями.
33
10. Дать формулировку теоремы об экстремуме задачи линейного
программирования.
11. Сформулировать основную теорему линейного программирования.
12. Как сформулировать теорему об альтернативном оптимуме.
1.5. Основные методы решения задач линейного программирования
1.5.1. Графический метод
Задачу линейного программирования можно решить графически, если стандартная
задача содержит не более двух неизвестных или основная задача содержит не более
двух свободных неизвестных.
При решении задачи графически следует 1) построить область допустимых
решений и 2) найти в области оптимальное решение.
Обоснование этой схемы дано в предыдущей главе и заключается в следующем:
1. Известно, что множество допустимых решений системы ограничений задачи
линейного программирования есть выпуклый многогранник (для плоскости
выпуклый многоугольник ограниченный или неограниченный).
2. Оптимальное решение находится в одной из крайних точек, если многогранник
ограниченный. В этом случае крайняя точка является вершиной многогранника. В
случае неограниченного многогранника оптимальное решение будет либо в одной из
крайних точек, либо целевая функция Z принимает значение , все это зависит от
конкретной ситуации.
х2 х2
С
В
А Д Zmax
O Е х1 O х1
n
Рис.6 Рис.7
Пример 1. Решить графически задачу линейного программирования.
При ограничениях
3 3,
5 2 10,
2,
1 2
1 2
1 2
x x
x x
x x
x1 0, x2 0,
найти максимум функции
Z x1 2x2.
34
Найдем вначале область допустимых решений каждого неравенства. Для этого
построим прямые:
3 3.
5 2 10,
2,
1 2
1 2
1 2
x x
x x
x x
Соответствующие каждому ограничению системы
Для построения прямой достаточно двух точек пересечения ее с осями координат
Для прямой: x1 x2 2,
х1 0 –2
х2 2 0
Для прямой: 5x1 2x2 10,
х1 0 2
х2 5 0
Для прямой: 3x1 x2 3,
х1 0 1
х2 –2 0
III
II
I
5
2
-2 2
0
линия уровня для вектора n 5, 2
C
B
A
x2
x2
линия уровня для вектора n 1, 2
5, 2 1 1, 2 n 1 n
рис 8
Граничная прямая делит плоскость Х10Х2 на две полуплоскости. Для того,
чтобы определить, точки какой полуплоскости удовлетворяют соответствующему
неравенству, выберем на плоскости любую точку, например, начало координат, т.е.
О(0; 0).
Подставим значения координат этой точки, т.е. х1 =0 и х2 =0 в каждое неравенство
системы ограничений, получим
35
0 3.
0 10,
0 2,
3 3,
5 2 10,
2,
1 2
1 2
1 2
x x
x x
x x
Первое и третье неравенства справедливы, поэтому для них выбираем областью
решения точки тех полуплоскостей, к которым принадлежит точка О(0; 0). Отметим
области решений каждого неравенства стрелками. Второе неравенство несправедливо ,
следовательно выбирает область решения точки той полуплоскости, к которой не
принадлежит точка О(0; 0).
Замечание. Если граничная прямая проходит через начало координат, то нужно
для «испытания» взять другую точку.
Найдем общую область допустимых решений, учитывая (из условия x1 0,
x2 0 ), что она должна быть расположена в I четверти.
Итак, общая область допустимых решений – треугольник АВС.
Целевая функция Z c1x1 c2x2 , при любом постоянном Z, задает прямую. Такие
прямые называются линиями уровня. Коэффициенты целевой функции с1, с2 являются
координатами вектора, перпендикулярного линии уровня. Такой вектор называют
целевым вектором n(c1,c2 ) . Его направление указывает на направление возрастания
целевой функции.
Для данного примера целевой вектор имеет вид: n( 1; 2) .
Начало вектора совпадает с началом координат, а конец, с точкой, координаты
которой х1= –1, х2 = 2.
Через общую область допустимых решений ( ABC ), перпендикулярно целевому
вектору проводим линию уровня.
Перемещая ее параллельно самой себе в направлении вектора n , определим
крайнюю точку, в которой функция Z x1 2x2 достигает максимума.
Максимальное значение функции будет достигнуто в вершине В множества
допустимых решений системы ограничений. Координаты точки В можно найти, решив
систему уравнений:
2 5
3 3,
2,
1
1 2
1 2
x
x x
x x
4,5.
2 2 2,5 4,5,
2,5,
2
2 2
1
x
x x
x
Подставив координаты точки В х1 = 2,5, х2 = 4,5 в целевую функцию, получим
Zmax 2,5 2 4,5 2,5 9 6,5.
Ответ: Zmax 6,5, при (2,5; 4,5).
*
X
Пример 2. Пусть система ограничений останется из предыдущей задачи.
Необходимо найти минимум целевой функции:
Z x1 2x2.
Так как система ограничений:
3 3,
5 2 10,
2,
1 2
1 2
1 2
x x
x x
x x
осталась прежней, то область допустимых решений остается ABC .
Целевой вектор для данной функции имеет координаты (5; 2).
36
Линия уровня перпендикулярная вектору n(5; 2) должна перемещаться
параллельно самой себе в направлении противоположном направлению вектора, т.к.
целевая функция Z x1 2x2 стремится к минимуму.
При этом функция будет достигать минимума во всех точках отрезка АС.
Найдем координаты точки А, решая систему уравнений:
5 2 10,
2,
1 2
1 2
x x
x x
.
7
20
;
7
6
x1 x2
Для определения координаты точки С решим систему уравнений:
3 3,
5 2 10,
1 2
1 2
x x
x x
.
11
15
;
11
16
x1 x2
Два оптимальных решения:
7
20
;
7
* 6
x и ,
11
15
;
11
* 16
x
соответствующих крайним точкам А и С.
Следовательно, функция достигает минимального значения в любой точке отрезка
АС с координатами где 0 1.
*
(1 )
* *
X t X1 t X2 t
10,
7
30 40
7
20
2
6
5
) 5
*
Zmin (X1
10.
11
80 30
11
15
2
11
16
) 5
*
Zmin (X2
Следовательно,
, где 0 1.
11
15
(1 )
7
20
;
11
16
(1 )
7
* 6
Zmin 10, при Х t t t t t
В этом случае имеет место альтернативный оптимум.
Пример 3. Найти максимум функции
Z x1 2x2 ,
при следующих ограничениях
3,
2 6,
3 8,
1 2
1 2
1 2
x x
x x
x x
x1 0, x2 0.
Построим граничные прямые и найдем область допустимых решений системы.
37
n
III
II
I
B
A
C
x1
x2
Рис. 9
Целевой вектор n 1; 1 .
Область допустимых решений – неограниченная многоугольная область. Задача
не имеет оптимального решения, так как Z .
1.5.2. Каноническая задача линейного программирования
Определение 1. Основную задачу линейного программирования будем называть
канонической, если система уравнений этой задачи является канонической, а целевая
функция выражена только через свободные неизвестные.
Рассмотрим основную задачу линейного программирования, в которой система
уравнений – каноническая, но целевая функция выражена через все переменные:
, 1 1 0.
2 2, 1 1 2 20,
1 1, 1 1 1 10,
(1.5.2.1)
m m m m mn n m
m m n n
m m n n
x a x a x a
x a x a x a
x a x a x a
x j 0 ( j 1,n),
Z c1x1 cmxm cm 1xm 1 cn xn c0 , (m n). (1.5.2.2)
Приведем задачу к каноническому виду для этого целевую функцию выразим
через свободные переменные: хm+1,…, xn. С этой целью перепишем выражение для
целевой функции в виде
Z c1x1 c2 x2 cmxm cm 1xm 1 cn xn c0. (1.5.2.3)
Умножим первое уравнение системы на c1, второе на c2 ,…, m уравнение на cm ,
тогда система примет вид:
, 1 1 0.
2 2 2 2, 1 1 2 2 2 20,
1 1 1 1, 1 1 1 1 1 10,
m m m m m m m mn n m m
m m n n
m m n n
c x c a x c a x c a
c x c a x c a x c a
c x c a x c a x c a
и сложим полученную систему с уравнением (1.5.2.3).
38
Z c1x1 c2 x2 cmxm c1x1 c2 x2 cmxm
(c1a1,m 1 c2a2,m 1 cmam,m 1 cm)xm 1
(c1a1n c2a2n cmamn cn )xn c1a10 c2a20 cmam0 cn
или
Z a0,m 1xm 1 a0,nxn a00, (1.5.2.4)
Z a00 a0,m 1xm 1 a0,nxn,
где
m
i
a ciai c
1
00 0 0 ,
m
i
a k ciaik ck
1
0 . (1.5.2.5)
Коэффициенты a0k – оценка соответствующей свободной переменной хk.
1.5.3. Симплексные таблицы
Решение канонической задачи симплексным методом существенно облегчается
применением так называемых симплексных таблиц. Всякую каноническую задачу
можно записать в виде табл. 1.5.3.1.
Табл. 1.5.3.1 заполняется следующим образом: в столбце i0 a записываются
свободные члены уравнений, в столбцах “x1”, “x2” , …, “xn”, коэффициенты при
соответствующих неизвестных этой системы.
Слева от столбца i0 a в столбце выписываются базисные неизвестные,
содержащиеся в соответствующих уравнениях системы (1.5.2.2).
Верхняя строчка и крайний левый столбец содержит коэффициенты при
соответствующих неизвестных в неприведенном выражении для функции Z. Если
функция выражена только через свободные неизвестные, то c j, соответствующие
базисным неизвестным, равны нулю.
Последняя строка таблицы называется индексной или оценочной и содержит в
условной форме приведенное выражение целевой функции.
Чтобы заполнить эту строку, надо выражение (1.5.2.1) привести к виду (1.5.2.4).
Если целевая функция выражена как через свободные так и через базисные
переменные, то для заполнения оценочной строки воспользуемся формулой (1.5.2.5).
Таблица 1.5.3.1
сj базис с0 с1 с2 сq cm cm+1 cp cn θ
ai0 x1 x2 xq xm xm+1 xp xn
с1
с2
сq
cm
x1
x2
xq
xm
a10
a20
aq0
am0
1
1
1
1
a1,m+1
a2,m+1
aq,m+1
am,m+1
a1p
a2p
aqp
amp
a1n
a2n
aqn
amn
Z а00 a0,m+1 a0p a0n
Эту формулу проще запомнить в виде правила нахождения оценок.
39
Оценка для x p равна сумме произведений элементов данного столбца на
соответствующие элементы первого столбца ( c j базисные) минус c p данного
столбца (коэффициент над x j ).
Таким образом,
m
i
a p ciaip c p
1
0 .
Табл. 1.5.3.1 дает полную информацию о решении задачи на каждом этапе
вычисления. Так, в столбце свободных членов содержатся значения базисных
неизвестных опорного плана X0 (а10, а20, …, аm0, 0, …, 0).
Первый элемент оценочной строки представляет собой значение целевой функции для
этого плана, т.е. Z0 a00.
1.5.4. Основные теоремы симплекс метода
Математическая модель канонической задачи имеет следующий вид:
Z a00 a0,m 1xm 1 a0nxn (1.5.4.1)
при ограничениях
, 1 1 0,
2 2, 1 1 2 20,
1 1, 1 1 1 10,
m m m m mn n m
m m n n
m m n n
x a x a x a
x a x a x a
x a x a x a
(1.5.4.2)
x j 0
j = 1, 2, …, n. (1.5.4.3)
или более кратко математическую модель можно записать следующим образом:
max
1
00 0, 1 1
n
j m
Z a a m xm
( 1, ),
1
x a x a 0, i m
n
j m
i ij j i
x j 0, (i 1,m) .
Теорема 1. (Достаточное условие оптимальности опорного плана). Если
решается каноническая задача линейного программирования и при этом все элементы
оценочной строки симплексной таблицы неотрицательны, то соответствующий
опорный план этой задачи является оптимальным, а элемент a00 представляет собой
наибольшее значение целевой функции на множестве планов задачи.
Доказательство:
Пусть исходный опорный план X0 задачи (1.5.4.1) (1.5.4.2) равен
X0 = (а10, а20, …, аm0, 0, …, 0).
Тогда значение целевой функции Z на X0 будет иметь вид
Z(X0 ) Z0 a00.
Допустим, что все элементы оценочной строки неотрицательны, т.е.
a0,m 1 0, ( j m 1,n).
Доказажем, что исходный план оптимален.
40
Пусть X (α1, α2, αm, αm+1, …, αn) произвольный допустимый план этой задачи,
тогда значение Z на данном плане X примет вид
( ) ,
1
00 0,
n
j m
Z X a a j j
Так как a0 j 0, ( j m 1, n) и j 0, ( j 1,n) ,
То Z(X) a00, но Z(X0 ) a00 , следовательно,
Z(X ) Z(X0 ), а это значит, что X0 оптимальный план, а Z(X0 ) a00
наибольшее значение целевой функции (1.5.4.2).
Теорема 2. (Случай неограниченности целевой функции). Если оценочная
строка задачи (1.5.4.1) (1.5.4.2) содержит отрицательный элемент a0k, а в столбце,
соответствующем неизвестному xk , нет ни одного положительного элемента, то на
множестве планов задачи целевая функция не ограничена сверху
Доказательство:
Предположим, что в оценочной строке есть элемент a0n 0, и над ним в столбцет все
элементы неположительные, т.е. a1n 0, a2n 0,…, amn 0 (столбец,
соответствующий свободной переменному xn ). Первоначальный опорный план задачи
линейного программирования X0 (а10, а20, . . ., аm0, 0, …, 0).
Построим новый план следующим образом: пусть xn 0, а
xm 1 xm 2 xn 1 0.
Тогда базисные переменные будут иметь вид (из 1.5.4.2)
.
,
,
0
2 20 2
1 10 1
m m mn
n
n
x a a
x a a
x a a
Так как все ai0 0, (i = 1, 2, …, m) и 0, то xi ai0 ain 0, (i = 1, 2, …, m).
И следовательно, очередным планом исходной задачи будет X1 , где
X1 (a10 a1n , ,am0 amn ,0,...,0, ) .
Тогда значение целевой функции Z на X1 равно
Z(X1) a00 a0,m 1xm 1 a0,nxn
при данном плане будет иметь вид
Z(X1) a00 a0,n
по условию a0n 0, а произвольное положительное число, следовательно, при
, Z(X1) .
Таким образом, на множестве планов задачи целевая функция Z может принимать
сколь угодно большие значения, т.е. не ограничена сверху.
Теорема 3. (Об улучшении опорного плана). Если решается задача (1.5.4.1)
(1.5.4.2) и в оценочной строке симплексной таблицы есть хотя бы один отрицательный
элемент a0n , а соответствующей этой строке столбец содержит хотя бы один
положительный элемент, то можно улучшить план, выполнив преобразование
однократного замещения.
41
Доказательство:
Исходный опорный план задачи (1.5.4.1) (1.5.4.2)
X0 (а10, а20, . . ., аm0, 0, …, 0),
Z0 a00.
Допустим, что a0n 0, а в столбце неизвестного xn есть положительные
элементы, пусть
a1n 0, a2n 0, …, aqn 0, а
aq 1,n 0, aq 2,n 0,…, amn 0.
Обозначим θ min , , , .
0
2
20
1
10
qn
q
n n a
a
a
a
a
a
И пусть min θ ,
1
10
a n
a
θ 0 по условию.
Следовательно, возможен переход к новому опорному решению и при этом xn
станет базисной переменной, а переменная xq станет свободной и тегда элемент aqn
станет разрешающим. Тогда следующее опорное решение будет иметь вид
(0, ' , ' , , ' ,0, , ).
0
1 20 30 m0
qn
q
a
a
X a a a
Подсчитаем значение целевой функции на опорном плане.
Рассчитаем значение Z при этом плане
( ) .
0
1 00 0
qn
q
n
a
a
Z X a a
Так как
a00 0; a0n 0, 0,
0
qn
q
a
a
то
Z(X1) a00 , так как a00 Z(X0 ), то Z(X1) Z(X0 ).
Следовательно, новое опорное решение “лучше” исходного.
Алгоритм симплекс метода
1.Записываем данную задачу в исходную симплекс-таблицу.
2.Если все элементы оценочной строки симплексной таблицы неотрицательны, то
исходный план оптимален.
3.Если в оценочной строке есть отрицательный элемент, над которым в таблице
нет положительного элемента, то целевая функция не ограничена сверху и задача не
имеет решение.
4.Если над каждой отрицательной оценкой в соответствующем столбце есть хотя
бы один положительный элемент, то можно перейти к лучшему плану.
Для этого:
а) выбираем разрешающий столбец, соответствующий наименьшей
отрицательной оценке;
б) выбираем разрешающую строку по minθ;
в) на пересечении разрешающего столбца и разрешающей строки находим
разрешающий элемент;
г) элементы разрешающей строки делим на разрешающий элемент;
42
д) элементы других строк находим по правилу “прямоугольника”, вплоть до
элементов оценочной строки.
1.5.5. Альтернативный оптимум
Иногда задача линейного программирования имеет несколько опорных решений,
в которых целевая функция достигает оптимального значения.
Оптимальным будет любое решение X, являющееся выпуклой линейной
комбинацией оптимальных опорных решений
X X1t1 X2t2 Xk tk
или
,
1
i
s
i
X ti X
если
1, 0.
1
i
s
i
ti t
В чем же практическое значение отыскания общего решения задачи в случае
альтернативного оптимума?
Так как модель задачи включает только один критерий оптимальности целевой
функции (например, максимум прибыли, максимум продукции, или минимум затрат) а
этого оказывается недостаточно для выбора наилучшего варианта и вынуждены решать
несколько задач по каждому критерию в отдельности. Из полученных таким образом
нескольких оптимальных решений можно выбрать наиболее целесообразное, но оно не
будет оптимальным по всем критериям. Когда же задача имеет альтернативный
оптимум, то, построив общее решение, можно, изменяя параметры t1, t2, …, tk, выбрать
план, который по другим показателям (не учтенным в функции Z ) окажется наиболее
целесообразным.
При решении задачи с альтернативным оптимумом надо выяснить следующие
вопросы:
1) установить признаки существования альтернативного оптимума;
2) найти все оптимальные опорные решения.
Пусть в результате некоторой итерации мы пришли к таблице, в которой все
оценки a0k 0, следовательно, получили оптимальный план:
X0 (a10,a20, ,am0,0, ,0), Z0 a00.
Если все оценки свободных переменных положительные, то введение любой из
них в базис уменьшит значение Z.
Тогда существует только одно оптимальное решение. Если какая либо оценка
свободной переменной равна нулю (например, a0 p 0 ), то введение этой переменной
в базис не изменит Z.
Дейтвительно. Если Z0 a00 по формуле прямоугольника:
43
1 0 max
1 0
0 0
00 00
1 00 00 0 0
0
Z Z Z
Z Z Z
Z a a
Z a a
Z a a a a
q p
q p
Итак, признаком существования альтернативного оптимума при расчете по
симплексным таблицам является наличие хотя бы одной нулевой оценки свободной
переменной при не отрицательности всех остальных оценок.
Если нулевых оценок при свободных переменных несколько, то введение в базис
всех соответствующих свободных переменных можно найти несколько оптимальных
решений.
Пример 1. Найти максимум целевой функции
Z 3x1 2x2 ,
при следующей системе ограничений:
2 4,
2 4,
10,
1 2
1 2
1 2
x x
x x
x x
x1 0, x2 0.
Решить задачу симплексным методом.
Решение.
Преобразуем стандартную задачу линейного программирования в основную,
добавляя к левым частям ограничений балансовые переменные. Целевая функция не
изменится.
Математическая модель примет вид:
2 4,
2 4,
10,
1 2 5
1 2 4
1 2 3
x x x
x x x
x x x
x j 0, ( j 1,5),
Z 3x1 2x2 max.
Получим каноническую задачу, в которой х3, х4, х5, – базисные переменные, а х1,
х2, – свободные переменные.
Исходное опорное решение:
x1 0; x2 0; x3 10; x4 4; x5 4, или X1(0; 0; 10; 4; 4).
Составим симплекс-таблицу.
44
Таблица 1.5.5.1
Ci
базиса
Базис 0 θ
ai0 x1 x2 x3 x4 x5
0
0
0
x3
x4
x5
10
4
4
1
1
–2
1
–2
1
1
0
0
0
1
0
0
0
1
10/1=10
4/1=4 min
–
Z1 0 –3 –2 0 0 0
0
3
0
x3
x1
x5
6
4
12
0
1
0
3
–2
–3
1
0
0
1
0
0
0
0
1
6/2=3
–
–
Z2 12 0 –8 0 0 0
2
3
0
x2
x1
x5
2
8
18
0
1
0
1
0
0
1/3
2/3
1
–1/3
1/3
1
0
0
1
Z3 28 0 0 8/3 1/3 0
Сi – коэффициенты целевой функции. При х1, коэффициент с1 = 3, при х2,
коэффициент с2 = 2, неизвестные х3, х4, х5 отсутствуют в целевой функции,
следовательно их коэффициенты равны нулю. В первом столбце таблицы
записываются коэффициенты целевой функции, соответствующие базисным
неизвестным.
Правило нахождения оценок:
Оценка для переменной хк равна сумме произведений элементов к-го столбца на
соответствующие элементы первого столбца (сi) минус коэффициент при данной
переменной (ск) в целевой функции, или оценки находятся по следующей формуле:
n
i
a k ciaik ck
1
0 .
В первой таблице расчет оценок:
1 0 0 0 0 0 0 0,
1 0 ( 2) 0 1 0 2 2,
1 0 1 0 ( 2) 0 3 3,
03
02
01
a
a
a
0 0 0 0 1 0 0 0.
0 0 1 0 0 0 0 0,
05
04
a
a
Первый опорный план X1(0; 0; 10; 4; 4) не оптимален, т.к. в перовой таблице в
оценочной строке есть отрицательные оценки.
По наименьшей отрицательной оценке (–3) выбирается разрешающий столбец
(х1).Так как в этом столбце есть положительный элемент, то можно перейти к лучшему
опорному плану методом однократного замещения.
Разрешающую строку определяем по наименьшему θ, равному отношению
свободных членов (ai0) к соответствующим положительным элементам разрешающего
столбца. В разрешающем столбце (х1) два положительных элемента. Найдем
минимальное из отношений, т.е. 4,
1
4
;
1
10
min следовательно, вторая строка
является разрешающей и элемент а21 = 1 есть разрешающий.
Неизвестное х1 войдет в базис вместо переменной х4. Затем переходим к лучшему
опорному плану X2 (4; 0; 6; 0; 12), Z2 12.
45
Но и этот план не является оптимальным, так как при переменной х2 оценка
отрицательна.
Вновь повторяем такой же алгоритм и получаем третий опорный план:
X3(8; 2; 0; 0; 18), Z3 28.
Последний опорный план будет оптимальным, так как в третьей таблице все
оценки неотрицательны.
Тогда ответом решения задачи будет:
Z3 28, при (8; 2).
*
X
1.5.6. Метод искусственного базиса
Решать задачу линейного программирования симплексным методом можно только
тогда, когда система ограничений записана в каноническом виде.
Если же в системе ограничений имеются знаки неравенства и 0 и 0, и есть
знак =, то введение балансовы переменных не приведет ее к каноническому виду.
Для того, чтобы система ограничений стала канонической можно добавить к
уравнениям, в которых нет базисных переменных, искусственные базисные
переменные.
Пусть задана основная задача линейного программирования.
,
1.5.6.1
1 1 2 2 0
21 1 22 2 2 20,
11 1 12 2 1 1 10,
m m mn n m
n n
n n
a x a x a x a
a x a x a x a
a x a x a x a
x j 0,
( j 1, 2, …, n),
Z c1x1 c2 x2 cn xn max.
Предположим, что все ai0 0, (i 1,m) (в противном случае этого добиться,
умножив соответствующие уравнения на ( 1).
Введем m неотрицательных переменных (y1, y2, …, ym) и назовем их
искусственными.
Получим систему
.
1.5.6.2
1 1 2 2 0
21 1 22 2 2 2 20,
11 1 12 2 1 1 10,
m m mn n m
n n
n n
a x a x a x ym a
a x a x a x y a
a x a x a x y a
x j 0,
yi 0,
(i 1,m) .
Составим новую целевую функцию
T Z M( y1 y2 ym) max, (1.5.6.3)
где М-произвольно большое положительное число. Получена новая задача. Назовем ее
М-задачей. Система ограничений М-задачи каноническая.
Пусть Y( 1, 2 ,..., n , n 1,..., n m) любое допустимое решение этой системы.
Если в этом решении все искусственные переменные равны нулю, т.е.
n 1 0,..., n m 0, то первые n чисел определяют допустимое решение системы
(1.4.6.1) X ( 1, 2 ,..., n ) .
46
Наоборот, если X ( 1, 2 ,..., n ) – есть допустимое решение системы (1.5.6.1), то
Y( 1, 2 ,..., n ,0,...,0) есть допустимое решение системы (1.5.6.2).
Решения X ( 1, 2 ,..., n ) и Y( 1, 2 ,..., n ,0,...,0) являются соответствующими.
Легко доказать, что Z – исходной и T – М-задачи при соответствующих решениях
одинаковы, т.е.
Z(X) T(Y).
М-задачу можно решить симплексным методом. Установим связь между
оптимальным решением М-задачи и исходной задачи.
Теорема 1. Если в оптимальном плане М-задачи все искусственные переменные
равны 0, то соответствующее решение исходной задачи является оптимальным.
Доказательство:
Пусть Y0 ( 1, 2 ,..., n ,0,...,0) – оптимальное решение М-задачи. Докажем, что
соответствующее решение исходной задачи X0 ( 1, 2 ,..., n ) является оптимальным.
Рассмотрим произвольное допустимое решение исходной задачи X ( 1, 2 ,..., n ) .
Тогда соответствующее допустимое решение М-задачи будет Y0 ( 1, 2 ,..., n ,0,...,0) .
Но так как Y0 – оптимальное решение М-задачи, то T(Y0 ) T(Y). Известно, что
T(Y0 ) Z(X0 ) и Z(X) T(Y) , тогда Z(X) Z(X) , т.е. X0 – есть оптимальное
решение исходной задачи.
Теорема 2. Если в оптимальном плане М-задачи хотя бы одна из искусственных
переменных отличается от нуля, то система ограничений исходной задачи несовместна
в области допустимых решений.
Доказательство:
Пусть Y0 ( 1, 2 ,..., n , n 1,..., n m) оптимальное решение М-задачи и при
этом хотя бы одно из n 1,..., n m отлично от нуля. Докажем, что система
ограничений исходной задачи несовместна.
Допустим противное, т.е. пусть X ( 1, 2 ,..., n ) – допустимое решение исходной
задачи.
Тогда соответствующее допустимое решение М-задачи Y( 1, 2 ,..., n ,0,...,0) .
Т.к. Y0 – оптимальное решение М-задачи, то
T(Y0 ) T(Y) т.е.
T(Y0 ) T(Y) 0.
Вычисли эту разность
0.
1 1
( )
1 1 1
( 0 ) ( )
m
i
M
n
j
c
n
j
c
m
i
M
n
j
T Y T Y c j j n i j j j j j n i
Так как среди n i есть хотя бы одно положительное, а М сколь угодно большое
число, то получим
.
( )
1
1
m
i
n
j
n i
c j j j
M
47
Получим T(Y0) T(Y) 0 , что противоречит условию.
Теорема 3. Если М-задача неразрешима, то и исходная неразрешима.
Алгоритм метода искусственного базиса
1. Составим М-задачу. При этом искусственные переменные вводим только в те
ограничения, которые не содержат “естественных” базисных переменных.
2. Составляем симплексную таблицу. Эта таблица содержит двет оценочные
строки. Оценки как обычно, вычисляются по формуле:
.
1
0 ip p
m
i
a p cia c
Оценка М-задачи при любой переменной будет иметь вид S Mt. S записывается в Z-
строку, а t в М-строку:
Так как M – сколь угодно большое положительное число, то знак оценки зависит
от знака t . Поэтому в методе искусственного базиса разрешающий столбец выбирается
по оценкам M-строки.
3. Задача решается симплексным методом. Если искусственные переменные
выходят из базиса (при этом элементы M строки обращаются в ноль), то решение
продолжаем по оценкам Z строки до получения оптимального решения. Если оценки
M строки неотрицательные, то получено оптимальное решение M задачи. При этом
исходная задача не имеет решения.
Пример 1. Найти максимальное значение целевой функции
Z x1 2x2 ,
при ограничениях
1,
5,
1,
1
1 2
1 2
x
x x
x x
x1 0, x2 0.
Решение.
Преобразуем систему ограничений к системе уравнений:
1,
5,
1,
1 5
1 2 4
1 2 3
x x
x x x
x x x
x j 0, ( j 1,5),
Z x1 2x2 max.
Первое и третье ограничения не содержат базисных неизвестных, поэтому мы
добавляем искусственны переменные именно в эти уравнения.
1,
5,
1,
1 5 2
1 2 4
1 2 3 1
x x y
x x x
x x x y
x j 0, ( j 1,5), yi 0, (i 1,2).
Целевая функция М-задачиT x1 2x2 M(y1 y2 ) max.
48
Составим симплексную таблицу.
Таблица 1.5.6.1
Ci
базиса
Базис 0 1 2 0 0 0 θ
ai0 x1 x2 x3 x4 x5
–M
0
–M
y1
x4
y2
1
5
1
–1
1
1
1
1
0
–1
0
0
0
1
0
0
0
–1
1/1=1 min
5/1=5
–
T Z1 0 –1 –2 0 0 0
M –2 0 –1 1 0 1
2
0
–M
x2
x4
y2
1
4
1
–1
2
1
1
0
0
–1
1
0
0
1
0
0
0
–1
–
4/2=2
1/1=1 min
T Z2 2 –3 0 –2 0 0
M –1 –1 0 0 0 1
2
0
1
x2
x4
x1
2
2
1
0
0
1
1
0
0
–1
1
0
0
1
0
–1
2
–1
–
2/1=2
–
T Z3 5 0 0 –2 0 –3
M 0 0 0 0 0
2
0
1
x2
x3
x1
4
2
1
0
0
1
1
0
0
0
1
0
1
1
0
1
2
–1
Z 9 0 0 0 2 1
Алгоритм решения симплексным методом был подробно рассмотрен в
предыдущих разделах.
Оценки первой таблицы
( 1) 0 0 ( ) 0 0 0,
1 0 1 ( ) 0 2 2,
( 1) 0 1 ( ) 1 1 0 1,
03
02
01
a M M M
a M M M
a M M M
0 0 0 ( ) ( 1) 0 .
0 0 0 ( ) 0 0 0,
05
04
a M M M
a M M
Так как в М-строке есть отрицательная оценка, то первый опорный план не
оптимален. Перейдем к более лучшему плану методом однократного замещения.
Алгоритм решения повторяется до тех пор, пока в оценочной строке все оценки станут
неотрицательными. В последней строке оценки неотрицательны, следовательно,
последний опорный план является оптимальным для М-задачи.
Tmax 9 , при (1; 4; 2; 0, 0).
*
X y1 y2
Так как в оптимальном плане М-задачи все искусственные переменные
обратились в нуль, то соответствующее решение является оптимальным для исходной
задачи.
Следовательно, Zmax 9 , при (1; 4).
*
X
49
1.6. Двойственность и анализ чувствительности
1.6.1. Определение двойственной задачи
исходную задачу линейного программирования будем называть прямой.
Двойственная задача – это задача, формируемая с помощью определенных правил из
прямой задачи.
Если рассматривать стандартную задачу линейного программирования, модель
которой имеет вид
n
j
Z c j x j
1
max, (1.6.1.1)
, ( 1, ),
1
a x b i m
n
j
ij j i (1.6.1.2)
x j 0, ( j 1,n), (1.6.1.3)
то модель двойственной к ней задачи формируется по следующим правилам:
1) Каждому ограничению прямой задачи соответствует переменная двойственной
задачи.
2) Каждой из переменных прямой задачи соответствует ограничение
двойственной задачи.
3) Коэффициенты при какой-либо переменной в ограничениях прямой задачи
становятся коэффициентами при переменных двойственной задачи.
4) Коэффициенты целевой функции прямой задачи становятся свободными
членами системы ограничений двойственной задачи.
5) Свободные члены системы ограничений прямой задачи становятся
коэффициентами целевой функции двойственной задачи.
6) Если целевая функция прямой задачи стремится к максимуму, то целевая
функция двойственной стремится к минимуму.
7) В двойственной задаче меняются знаки между левой и правой частями
ограничений на противоположный (с на ).
Т.е. математическая модель двойственной задачи к стандартной будет:
m
i
W bi yi
1
min, (1.6.1.4)
, ( 1, ),
1
a y c j n
m
i
ij i j (1.6.1.5)
yi 0, i (1,m) . (1.6.1.6)
Если иметь ввиду, что прямая задача представляет задачу линейного
программирования о распределении ограниченных ресурсов, где
xi – объем выпускаемой продукции j-го вида,
cj – цена единицы j-го вида продукции,
bi – запас i-го ресурса,
aij – затраты i-го ресурса на выпуск j-го вида продукции,
Z – целевая функция представляет собой прибыль от реализации готовой
продукции и стремится к максимуму, то в двойственной задаче
yi – оценка (теневая цена) единицы i-го вида ресурса,
а целевая функция двойственной задачи W – представляет собой затраты всех ресурсов
на выпуск продукции всех видов и стремится к минимуму.
50
m
i
aij yi c j
1
– показывает затраты всех ресурсов на выпуск единицы j-го вида
продукции.
Прямая и двойственная задачи, модели которых выражены в виде соотношений
(1.6.1.1)-(1.6.1.3) и (1.6.1.4)-(1.6.1.6), называются симметричными.
Кроме симметричных задач в линейном программировании существуют
несимметричные двойственные пары.
Например, к основной задаче линейного программирования, модель которой
имеет вид
n
j
Z c j x j
1
max (min),
, ( 1, ),
1
a x b i m
n
j
ij j i
x j 0, ( j 1,n),
модель двойственной будет
1)
m
i
W bi yi
1
min,
, ( 1, ),
1
a y c j n
m
i
ij i j
2)
m
i
W bi yi
1
max,
, ( 1, ),
1
a y c j n
m
i
ij i j
В последних задачах отсутствует неотрицательность переменных yi , i (1,m).
1.6.2. Теоремы двойственности
Связь между оптимальными планами пары двойственных задач устанавливаются
с помощью теоремы двойственности.
Будем рассматривать в взаимосвязи либо только симметричные задачи, либо не
симметричные. Полученные свойства. Справедливые для одной из них справедливы и
для другой.
Теорема 1. (о неравенствах)
Если вектор X ( 1, 2 ,..., n ) – допустимое решение прямой задачи (1.6.1.1)-
(1.6.1.3), а Y ( 1, 2 ,..., m) – допустимое решение двойственной к ней задачи
(1.6.1.3)-(1.6.1.4), тогда
CX YA0.
Доказательство:
Если X – допустимое решение исходной задачи, то оно удовлетворяет системе
ограничений этой задачи, т.е.
AX A0.
51
Y – допустимо решение двойственной задачи, т.е. Y 0.Умножим левую и
правую часть неравенства на Y , получим
YAX YA0.
Кроме того Y допустимое решение системы ограничений двойственной задачи.
Поэтому YA C, тогда из двух последних неравенств следует
CX YA0 ,
что и требовалось доказать.
Теорема 2. Если для некоторых планов ( 1*, *2 ,..., *)
*
X n и ) ( *, *,..., * 1 2
*
Y m
исходной и двойственной задач выполняется равенство
,
* *
CX Y A0
то векторы
*
и
*
X Y являются оптимальными планами соответствующих задач.
Доказательство:
Пусть X – любой допустимый план исходной задачи, тогда для пары X и
,
*
Y согласно теореме 1 справедливо неравенство
,
*
CX Y A0 так как ,
* *
Y A0 CX то ,
*
CX CX если выполняется такое
неравенство для любого допустимого плана X , то X -
*
есть оптимальный план
исходной задачи. Аналогично, если
Y – любое допустимое решение двойственной задачи, тогда для пары Y и ,
*
X согласно
теореме 1 справедливо неравенство
,
*
CX YA0 так как ,
* *
CX Y A0 то ,
* *
Y A0 Y A0 это означает, что Y -
*
есть
оптимальный план двойственной задачи.
Определение. Говорят, что целевая функция W не ограничена снизу на множестве
планов, если для любого сколь угодно большого положительного числа M > 0 найдется
такой план Y , что W(Y )<–M.
Теорема 3. Если целевая функция двойственной задачи не ограничена снизу на
множестве своих планов, то прямая задача не имеет ни одного допустимого плана.
Доказательство:
По условию теоремы, существует такая последовательность {Yk } планов
двойственной задачи такая. Что
lim ( ) lim Y A0 .
k
W Y
k
k k
Предположим, что исходная задача имеет допустимый план X , тогда согласно
теореме 1
CX Yk A0
для любого k. Перейдем к пределу при k , получим
lim lim Y A0 ,
k
CX
k
k
lim Y A0 ,
k
CX k
CX .
52
Так как все соответствующие векторы X – конечные величины, то в последнем
неравенстве величина CX будет конечна. Следовательно, предположение о наличии
допустимого плана у исходной задачи было ошибочным. Т.е. исходная задача не будет
иметь ни одного допустимого плана.
Рассмотрим основную задачу линейного программирования.
0,
.......... .......... .......... .......... .......... .......... .......... .......... ....
1 1 , 1 1 0
11 1 1 1 1 1 1 10
j
m mm m m m m mn n m
m m m m n n
x
a x a x a x a x a
a x a x a x a x a
max. Z c1x1 amxm am 1xm 1 anxn
Пусть x , , xm 1 - базисные переменные системы ограничений, тогда m n x , , x 1 -
свободные переменные обозначим
;
1 2
11 12 1
1
m m mn
m
a a a
a a a
A
;
, 1 , 2
1, 1 1, 2 1
2
m m m m mn
m m n
a a a
a a a
A
;
1
1
Xm
X
X
;
1
2
n
m
X
X
X
;
0
10
0
m a
a
A
( , , , ); C1 c1 c2 cm
( , , , ). 2 m 1 m 2 n C c c c
где 1 A матрица коэффициентов при базисных переменных,
2 A матрица коэффициентов при свободных переменных,
0 A матрица коэффициентов свободных членов;
1 X матрица столбец базисных неизвестных;
2 X матрица столбец свободных неизвестных;
1 C матрица строка коэффициентов при базисных переменных целевой функции;
2 C матрица строка коэффициентов при свободных переменных целевой
функции.
A1 X1 A2 X2 A0, (1.6.2.1)
X1 0, X2 0,
Z C1X1 C2 X2 max (1.6.2.2)
0,
, (1.6.2.4)
, (1.6.2.3)
2 2
1 1
Y
YA C
YA C
W1 YA0 min, (1.6.2.5)
где Y (Y1,Y2 ,...,Ym, ).
53
Пусть оптимальный план исходной задачи будет ( , ,..., ,0,...,0), 0 0
2
0
1
0
Y X X Xm если
;
0
0
1
0
1
Xm
X
X
0.
0
0
0
X2
Подставим
0
X1 и
0
X 2 в систему ограничений исходной задачи, получим
2 0 0 ,
0
A1 X1 A A отсюда
0
0
A1 X1 A или 0. (1.6.2.6)
1
1
0
X1 A A
Оптимальное значение целевой функции будет
0 0 ,
1
1 1
0
2 1 1
0
Zmax C1 X1 C C X C A A
0. (1.6.2.7)
1
Zmax C1A1 A
Теорема 4. (основная)
Если одна из пары двойственных задач имеет оптимальное решение, то и другая
имеет оптимальное решение, при этом целевые функции на оптимальных планах равны
между собой
),
*
) (
*
Z(X W Y если
*
X и
*
Y – оптимальные планы пары двойственных задач
Доказательство:
Пусть исходная задача имеет оптимальное решение
; max .
*
0
1
0 1 1
1
X1 A1 A Z C A A
Докажем, что и двойственная задача имеет оптимальное решение.
Пусть X – любое допустимое решение исходной задачи, которое удовлетворяет
системе ограничений, т.е.
A1 X1 A2 X2 A0,
A1 X1 A0 A2 X2 ,
2 2.
1
0 1
1
X1 A1 A A A X
Найдем значение Z для плана X :
( 2 2 ) 2 2 ,
1
0 1
1
Z CX C1 X1 C2 X2 C1 A1 A A A X C X
2 2 2 2 ,
1
0 1 1
1
Z C1A1 A C A A X C X
( 2 ) 2.
1
0 2 1 1
1
Z C1A1 A C C A A X
Т.к. X – произвольный план, то
,
*
0
1
CX CX Zmax C1A1 A
( ) 0.
1
2 2 1 1
1
0 2 1 1
1
C1A1 A C C A A X C A A
Из последнего неравенства
( 2 ) 2 0.
1
C2 C1A1 A X (1.6.2.8)
54
Т.к. X2 0, то
( 2 ) 0.
1
C2 C1A1 A (1.6.2.9)
Обозначим
1 *
C1A1 Y и покажем, что
*
Y – план двойственной задачи. Из
(1.6.2.9) имеем
2
1
C2 C1A1 A или
2 2
*
C Y A или .
*
Y A2 C2
Это означает, что
*
Y – является решением ограничения (1.6.2.4).
Подставим значение 1
1
*
Y C A в неравенство (1.6.2.3), получим
,
*
1 1
1
Y A1 C1A1 A C или C1 C1.
Т.е
*
Y – решение ограничения (1.6.2.3) и, следовательно, является решением всей
системы ограничений (1.6.2.3)-(1.6.2.5).
Докажем, что
*
Y – является оптимальным решением двойственной задачи.
Так как ),
*
(
*
0 0
1
Zmax C1A1 A Y A W Y таким образом ),
*
Zmax W(Y откуда
следует, что
*
Y – оптимальный план двойственной задачи, при этом
.
*
Wmin Y A0 Zmax
Основная теорема дает правило оптимального решения двойственной задачи по
оптимальному решению исходной задачи.
Поясним правило на примере симметричных задач.
Исходная задача.
0, ( 1, ).
, ( 1, ),
max,
1
1
x j n
a x b i m
Z c x
j
n
j
ij j i
n
j
j j
Двойственная задача.
0, ( 1, ).
, ( 1, ),
min,
1
0
1
0
y i m
a y b j n
Z a y
i
m
i
i i j
n
j
i i
Преобразуем неравенства систем ограничений обоих задач в уравнения, получим
n
j
aij x j xn i ai i m
1
0, ( 1, ), (1.6.2.10)
, ( 1, ).
1
m
i
aij yi ym i c j j n (1.6.2.11)
Систему из (1.6.2.11) приведем к системе с базисом
55
.
1
m
i
aij yi ym j c j (1.6.2.12)
Пусть ai0 0, тогда для исходной задачи можно записать первоначальное
опорное решение и решать задачу симплексным методом.
Из системы (1.6.2.12) следует, что базисное решение двойственной задачи имеет
вид
(0, 0, …, 0, –с1, –с2,…, –сn).
Таблица 1.6.2.1
ym+1 ym+2 … ym+n y1 ym
сj Базис 0 c1 c2 … cn 0 0
ai0 x1 x2 … xn xn+1 xn+i xn+m
0
0
…
0
…
0
Xn+1
Xn+2
…
Xn+i
…
Xn+m
a10
a20
…
ai0
…
am0
a11
a21
…
ai1
…
am1
a12
a22
…
ai2
…
am2
…
…
…
…
…
…
a1n
a2n
…
ain
…
amn
1
0
…
0
…
0
0
0
…
1
…
0
0
0
…
0
…
1
Z 0 -c1 -c2 … -cn 0 0 0
Из таблицы следует соответствие между базисными и свободными переменными
взаимно двойственных задач: базисным переменным исходной задачи.
xn 1, xn 2 ,..., xn m
соответствуют свободные переменные двойственной задачи
y1, y2 ,..., ym и наоборот.
Для нахождения оптимального решения двойственной задачи нужно найти
симплексным методом оптимальное решение исходной задачи. Оптимальное решение
двойственной задачи равно .
* 1
Y C1A1 Матрица 1
A1 оказывается расположенной в
последней таблице на месте первоначальных единичных столбцов исходной таблицы.
На основании равенства 1
1 1
*
Y C A и формулы для вычисления оценок в симплексной
таблице получим следующее соотношение для вычисления оптимальных значений
двойственных переменных
* .
0
i ki yi a k c
Теорема 5. (о равновесии)
Для того, чтобы допустимые решения
( *, *,..., * )
*
( *, *,..., *) и
*
X x1 x2 xn Y y1 y2 ym
исходной и двойственной стандартных задач были оптимальными, необходимо и
достаточно, чтобы имели место следующие соотношения:
1) Если * , то * 0.
1
n
j
aij x j bi yi (1.6.2.13)
2)Если * , то * 0.
1
n
j
aij x j bi yi (1.2.2.14)
3) Если * 0, то * .
1
m
i
xi aij yi c j (1.2.2.15)
56
4) Если * 0, то * .
1
m
i
x j aij yi c j (1.2.2.16)
То есть в оптимальном плане для каждой пары сопряженных условий прямой и
двойственной задач соблюдаются соотношения: если одно из них закреплено, то другое
свободно и наоборот.
Условие считается закрепленным, если оно выполняется как строгое равенство, а
свободным если выполняется как строгое неравенство
Теорема о равновесии справедлива для задач с невырожденными оптимальными
планами( когда все базисные переменные задач больше нуля).
Пример 1.
Решить задачу симплексным методом
Z 5x1 3x2 max,
3
2
1
1 2
1 2
1 2
2 3 12,
2 4,
4 6,
y
y
y
x x
x x
x x
x1 0, x2 0.
Составить к исходной задаче двойственную, найти ее оптимальный план.
Решение.
Составим математическую модель двойственной задачи.
W 6y1 4y2 12y3 min,
при ограничениях
y y y
y y y
2 3 3,
4 2 5,
1 2 3
1 2 3
yi 0, (i 1,3).
Решим исходную задачу симплексным методом.
Составим симплексную таблицу.
Таблица 1.6.2.2
Сi Базис ai0 0 5 2 0 0 θ
x1 x2 x3 x4 x5
0
0
0
x3
x4
x5
6
4
12
–4
1
2
1
–2
3
1
0
0
0
1
0
0
0
1
–
4/1 = 4 min
Z1 0 –5 –5 0 0 0
0
5
0
x3
x1
x5
22
4
4
0
1
0
–7
–2
7
1
0
0
4
1
–2
0
0
1
–
–
4/7
Z2 20 0 –12 0 5 0
0
5
2
x3
x1
x2
26
36/7
4/7
0
1
0
0
0
1
1
0
0
2
3/7
–2/7
1
2/7
1/7
Z3 188/7 0 0 0 11/7 12/7
y1 y2 y3
Оптимальный план исходной задачи
.
7
188
, max
7
4
;
7
* 36
X Z
57
Оптимальный план двойственной задачи
.
7
188
, max
7
12
;
7
11
0;
*
Y Wmin Z
Проверка:
Wmin 6y1 4y2 12y3 min. ,
7
12
;
7
11
y1 0; y2 y3 получим
.
7
188
7
144
7
44
7
12
12
7
11
Wmin 6 0 4
Пример 2.
Составить к исходной задаче двойственную.
Z x1 x2 2x3 x4 2x5
3
2
1
2 3 5 6
2 3 4
1 2 3 5
4 3 8 6,
2 4 2,
2 7,
y
y
y
x x x x
x x x
x x x x
x j 0, ( j 1,6).
Решить исходную задачу симплексным методом и найти оптимальное решение
двойственной задачи.
Решение.
Составим модель двойственной задачи
W 7y1 2y2 6y3 min,
при ограничениях
y y
y
y y y
y y y
y
8 2,
1,
4 3 2,
3 2 4 1,
1,
1 3
2
1 2 3
1 2 3
1
yi 0, (i 1,3).
Решим исходную задачу симплексным методом.
Составим симплексную таблицу.
Таблица 1.6.2.3
Сi Базис ai0 1 –1 2 1 2 0 θ
x1 x2 x3 x4 x5 x6
0
0
0
х1
x4
x6
7
2
6
1
0
0
3
–2
–4
–1
4
3
0
1
0
1
0
8
0
0
1
7/1 = 7
–
6/8=3/4 min
Z1 9 0 –5 1 0 –1 0
0
5
0
х1
x4
x5
25/4
2
3/4
1
0
0
–7
–2
7
–11/8
4
3/8
0
1
0
0
0
1
–1/8
0
1/8
Z2 39/4 0 –12 11/8 0 0 1/8
y1
x1
y2
x4
y3
x6
58
Оптимальный план исходной задачи:
.
4
39
,
4
3
; 0; 0; 2;
4
* 25
X Zmax
Оптимальный план двойственной задачи:
.
4
39
.
8
1
0
8
* 1 * 0 1 1; * 0 1 1;
y1 y2 y3 Wmin
Проверка:
.
4
39
4
3
9
8
1
Wmin 7y1 2y2 6y3 7 1 2 1 6
1.6.3. Экономико-математический анализ полученных оптимальных
решений
Оптимальное решение задачи линейного программирования определяется
условиями, которые нашли отражение в модели в момент ее формирования.
Оптимальное решение существенно зависит от реальной экономической ситуации, т.к.
в реальной жизни условия, формирующие модель, не остаются неизменными.
В связи с этим особое значение приобретают средства, позволяющие оценить
изменения в оптимальном решении, вызванные изменениями в параметрах исходной
модели. На решение задачи могут повлиять следующие экономические ситуации:
1) изменение запасов ресурсов,
2) происшедшие изменения в ценовой политике на предприятии.
Результаты влияния данных ситуаций на оптимальное решение можно получить в
ходе проведения экономико-математического анализа модели на чувствительность.
Анализ модели на чувствительность оптимального решения базируется на
следующих свойствах двойственных оценок.
Свойство 1. Оценка, как мера влияния на значение целевой функции в
оптимальном плане.
Двойственные оценки показывают на сколько изменится целевая функция в
оптимальном плане при изменении правой части системы ограничений (ресурсов) на
единицу.
Свойство 2. Оценка как мера дефицитности ресурсов.
Если в оптимальном плане i-й ресурс используется полностью и оценка этого
ресурса больше нуля ( 0 *
yi ), то этот ресурс называют дефицитным. Чем больше
оценка, тем ресурс дефицитнее.
Если же в оптимальном плане ресурс используется не полностью (есть остатки) и
оценка этого ресурса равна нулю ( 0 *
k y ), то такой ресурс называют недефицитным.
Свойство 3. Оценка как мера эффективности выпуска продукции.
В оптимальный план включается лишь тот вид продукции, затраты ресурсов на
выпуск единицы которых, совпадают с ценой единицы этого вида продукции.
Свойство 4. Оценка, как мера балансировки затрат и результатов.
На оптимальных планах, значения целевых функций прямой и двойственной
задач, совпадают.
Т.к. )
*
Zmax (X значение целевой функции, это результат производства, а
)
*
Wmin (Y – затраты ресурсов для получения результата, то
)
*
) (
*
Zmax (X Wmin Y ,
59
где
*
X и
*
Y – оптимальные планы пары двойственных задач.
Пример 1. Рассмотрим задачу по определению оптимального плана выпуска
продукции, максимизирующего выручку при известных нормах расхода ресурсов,
объемах ресурсов и ценах реализации продукции.
Исходные условия задачи даны в табл.1.6.3.1.
Таблица 1.6.3.1
Вид продукции
Вид ресурсов
Затраты ресурсов на единицу продукции Запасы
1 2 3 4 ресурсов
1
2
3
4
4
3
0
4
2
0
5
1
5
3
2
3
2
1
6
2
550
350
650
650
Цена единицы
продукции
9 3 5 4,5
Составим математическую модель задачи.
Пусть Х1, Х2, Х3, Х4 – соответствующие объемы выпускаемой продукции.
Тогда выручка от реализации продукции
Z 9x1 3x2 5x3 4,5x4
достигает максимума при таких значениях x j , ( j 1,4), которые удовлетворяют
условию ограниченности расхода ресурсов:
4 3 2 650,
5 2 6 650,
3 5 350,
4 2 5 2 550,
1 2 3 4
2 3 4
1 3 4
1 2 3 4
x x x x
x x x
x x x
x x x x
x j 0, ( j 1,4).
При решении задачи симплексным методом она приводится к каноническому
виду добавлением к левой части ограничений неотрицательных балансовых
переменных:
4 3 2 650,
5 2 6 650,
3 5 350,
4 2 5 2 550,
1 2 3 4 4
2 3 4 3
1 3 4 2
1 2 3 4 1
x x x x s
x x x s
x x x s
x x x x s
x j 0, ( j 1,4), si 0, (i 1,4).
Значения балансовых переменных Si показывают размеры неиспользованных
ресурсов в соответствующем плане.
Двойственная задача:
Найти оптимальные оценки ) ( *, *, *, *
*
Y Y1 Y2 Y3 Y4 , удовлетворяющие условиям:
2 6 2 4,5,
5 3 2 3 5,
2 5 3,
4 3 4 9,
1 2 3 4
1 2 3 4
1 3 4
1 2 4
y y y y
y y y y
y y y
y y y
yi 0, (i 1,4).
60
При которых целевая функция
W 550y1 350y2 650y3 650y4
принимает минимальное значение (стремится к min).
Приведем модель задачи к основному виду. Неотрицательные балансовые
переменные вычитаем из левой части ограничений, тогда модель примет вид:
2 6 2 4,5,
5 3 2 3 5,
2 5 3,
4 3 4 9,
1 2 3 4 4
1 2 3 4 3
1 3 4 2
1 2 4 1
y y y y l
y y y y l
y y y l
y y y l
yi 0, (i 1,4), l j 0, ( j 1,4).
Здесь превышение оценок ресурсов на выпуск единицы j-го вида продукции над
ценой единицы этой продукции.
Отчет о решениях исходной и двойственной задач с помощью ППП QM for
Windows по модулю Linear Programming имеет следующий вид.
Таблица 1.6.3.2
Таблица оптимального решения
(untitled) Solution
X1 X2 X3 X4 RHS Dual
Maximize 9 3 5 4,5
Constraint 1 4 2 5 2 550 1,211538
Constraint 2 3 0 3 1 350
Constraint 3 0 5 2 6 650
Constraint 4 4 1 3 2 650
Solution-> 82,69231 7,69231 0 101,9231 $1 225,96
В последней строке этого отчета под соответствующими переменными указаны
их значения в оптимальном решении, а так же значение целевой функции (в столбце
RHS). В последнем столбце (Dual – двойственный) указаны двойственные оценки
оптимального решения.
Итак, для получения максимального дохода необходимо выпустить продукции в
объемах: 101,9231, * 82,6923; * 7,6923; * 0; *
x1 x2 x3 x4 при этом Zmax 1 225,96
единиц.
Оптимальное решение двойственной задачи будет
* 0,8333; * 0; * 1,1667; * 0,1667.
y1 y2 y3 y4 Wmin Zmax 1 225,96единиц.
Исследуем полученное оптимальное решение задачи по свойствам двойственных
оценок. Под двойственной оценкой будем понимать оценку единицы i-го вида ресурса,
или, по другому, теневой ценой i-го ресурса.
Проиллюстрируем свойства двойственных оценок на основе этой задачи.
1. Каждая из оценок указывает, на сколько изменится максимальное значение
целевой функции (максимальная выручка), если изменить на единицу запасы
соответствующих ресурсов. Наибольшее изменение выручки произойдет, если
изменить объем 2-го ресурса ( *
2 y = 1,384615), а изменение четвертого ресурса (в
границах устойчивости) не приведет к изменению целевой функции ( *
4 y = 0).
61
2. Оценки
*, *, *
y1 y2 y3 положительны. Это означает, что при реализации
оптимального плана соответствующие ресурсы расходуются полностью. Проверим это.
Подставим *
j x в систему ограничений исходной задачи.
Получим:
0 82,6923 5 7,6923 2 0 6 101,9231 650.
3 82,6923 0 7,6923 3 0 1 101,9231 350,
4 82,6923 2 7,6923 5 0 2 101,9231 550,
Следовательно, 1, 2, 3-й ресурсы дефицитны, т.е. расходуются полностью. Т.к.
*4
y = 0 это означает, что в оптимальном решении четвертый ресурс расходуется не
полностью. Проверим это. Подставим *
j x в четвертое ограничение исходной задачи:
4 82,6923 1 7,6923 3 0 2 101,9231 542,3077 650.
Остаток четвертого ресурса составляет 650-542,3077 107,69. Это и есть значение
балансовой переменной в оптимальном решении исходной задачи.
3. Рентабельными являются 1-я, 2-я и 4-я продукции ( * , * , *
x1 x 2 x 4 в оптимальном
плане положительны), а нерентабельной 3-я –
*
x 3 . Проверим это, подставив
*
yi в
сопряженные условия двойственной задачи. Для первой продукции:
4 1,2125 3 1,3846 0 0,1154 4 0 8,9999 9.
Аналогично для второй и четвертой продукции:
2 1,2125 0 1,3846 5 0,1154 1 0 2,9999 3,
2 1,2125 1 1,3846 6 0,1154 2 0 4,4999 4,5.
Покажем нерентабельность третьей продукции, подставив
*
yi в третье
ограничение двойственной задачи. Получим:
5 1,2125 3 1,3846 2 0,1154 3 0 10,4423 5.
Таким образом, оценка ресурсов, необходимых для производства единицы 3-й
продукции больше цены этой продукции на 10,4423 – 5= 5, 4423.
На оптимальных планах целевые функции прямой и двойственной задач должны
быть равны. Для проверки подставим значения переменных оптимального плана
исходной задачи x*j , ( j 1,4) в целевую функцию исходной задачи, получим
Z 9 82,69231 3 7,692307 5 0 4,5101,9231 1225,96,
И подставим значения переменных в оптимальном плане двойственной задачи в
целевую функцию двойственной задачи, получим
W 550 1,211538 350 1,384615 650 0,1153857 650 0 1225,96.
Zmax Wmin 1225,96.
Таким образом, эффект от выпуска продукции в оптимальном плане совпадает с
затратами, исчисленными в «теневых ценах».
Исходя из полученных оптимальных решений двойственных задач можно
определить план действий при формировании запасов ресурсов для дальнейшего
производства, наметить мероприятия по переводу продукции из нерентабельной в
рентабельную, как при этом можно изменять цена на продукцию и запасы ресурсов без
резкого изменения полученного оптимального решения. Речь идет об определении
границ устойчивости полученного решения.
62
Под устойчивостью понимается неизменность набора базисных переменных при
изменении цен на продукцию и неизменность оценок при изменении запасов ресурсов.
В связи с этим необходимо определить такие интервалы изменения каждого из
свободных членов системы линейных ограничений (запаса ресурсов), в которых
оптимальный план двойственной задачи не меняется.
Предельные оценки изменения запаса дефицитного k-го ресурса можно
определить по следующим формулам:
, для 0,
*
min ( )
jk
jk
j
k
k d
d
x
b
, для 0,
*
min
( )
jk
jk
j
k
k d
d
x
b
где *
j x – значение j-й базисной переменной оптимального плана,
d jk – элементы обратной матрицы коэффициентов при базисных переменных
Тогда пределы изменения запасов дефицитного k-го ресурса будут:
( ) ( ) ; bk bk bk bk ,
Для дефицитных видов ресурсов р-го вида пределы изменения составят:
; . ( ) bp bp
Если изменения ресурсов находятся в пределах устойчивости оценок, то их
раздельное влияние на величину доходов
k
Zmax определяется произведением оценки
*k
y и величины bk , т.е.
*
max k k
k
Z b y .
Предельные оценки изменения цен рентабельной продукции р-го вида можно
определить по формулам:
, для 0,
*
min ( )
ip
ip
i
p
p d
d
y
c
, для 0,
*
min ( )
ip
ip
i
p
p d
d
y
c
где
*
yi – значение i-й базисной переменной оптимального плана двойственной задачи,
dip – элементы обратной матрицы коэффициентов при базисных переменных.
Тогда пределы изменения цены рентабельной продукции р-го вида будут
; , ( ) ( )
c p c p c p c p
Для нерентабельной продукции q-го вида пределы изменения составят
0; . ) (
q cq c
63
) (
qc – совпадает с lq (превышением затрат над ценой). Если цену этого вида
продукции увеличить на величину lq , то продукция данного вида станет рентабельной.
Если изменения цен находятся в пределах границ устойчивости оценок, то их
влияние на величину доходов
p
Zmax определяется произведением величины
изменения цены c p на объем этого вида продукции в оптимальном плане *
x p , т.е.
* .
max p p
p
Z c x
Границы устойчивости для данной задачи находятся с помощью пакета
прикладных программ (ППП) QM for Windows, содержащий раздел линейного
программирования.
Таблица 1.6.3.3
Таблица границ устойчивости параметров исходной задачи.
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
X1 =
X2 =
X3 =
X4 =
82,69231
7,692307
0
101,9231
l1=0
l2=0
l3=5,442307
l4=0
c1=9
c2=3
c3=5
c4=4,5
3,75926
1,25
0
4
10,5
4,5
10,44231
6,6
Constraint Dual
value
Slack/Surplus Original
Value
Lower
Bound
Upper
Bound
Constraint 1
Constraint 2
Constraint 3
Constraint 4
y1 = 1,211538
y1 = 1,384615
y1 = 0,1153846
y1 = 0
s1=0
s2=0
s3=0
s4=107,6923
b1=550
b2=350
b3=650
b4=650
538,8889
217,5
208,3333
542,3077
726,6667
358,3333
750
Infinity
В табл. 1.6.3.3 показано окно Ranging (размах), в котором отражены границы
устойчивости параметров исходной задачи. В столбце Value указаны значения
переменных в оптимальном плане задачи. В столбце Reduced Cost (уменьшенный)
указаны величины, на которые нужно уменьшить левую или увеличить правую части
соответствующего ограничения двойственной задачи для того, чтобы они сравнялись.
В следующем столбце Original Value (первоначальная величина) указаны
коэффициенты целевой функции при соответствующих переменных. В последних двух
столбцах указаны нижние и верхние границы изменения этих коэффициентов. Если
коэффициенты изменяясь, не будут выходить за пределы этих границ, то основные
переменные исходной задачи не изменят свой статус в оптимальном решении, т.е. если
были базисными в оптимальном решении, то таковыми останутся и в новом решении
(структура выпуска продукции не изменится).
В нижней части (табл. 1.6.3.3) указаны границы устойчивости переменных
двойственной задачи (двойственных оценок). В первом столбце Dual value указаны
двойственные оценки оптимально решения для каждого ограничения, во втором
Slack/Surplus – значения балансовых переменных, в третьем Original Value исходные
значения правых частей ограничений. В последних двух столбцах – нижняя и верхняя
границы изменения правых частей. Если правые части ограничений изменяясь, не
выйдут за пределы этих границ, то двойственные оценки оптимального плана останутся
неизменными.
64
В табл. 1.6.3.3 приведены границы изменения цен на продукцию и запасов
ресурсов.
Цена (c1)на первую продукцию может меняться с 3,75926 до 10,5, на вторую
1,25 c2 4,5,
0 c3 10,44231,
4 c4 6,6.
Пока цена будет оставаться в указанных пределах, в базисе будут те же
переменные x1, x2, x4, s4. Из значения также не изменятся.
При изменении цены в границах устойчивости, можно спрогнозировать
изменение значения целевой функции в оптимальном плане.
Увеличение цены четвертого вида продукции до 6,5 ( 5 , 6 *
4 c ) данная цена входит
в границы устойчивости 6,5 4; 6,6 ; следовательно, изменение целевой функции в
оптимальном плане можно рассчитать по формуле x c Z , *
4 4
4
max
где c4 с*4 c4 , и Z (6,5 4) 101,9231 152,88465.
4
max
Для первой задачи
Z* Z Z 1225,96 152,88465 1378,8446.
4
max max max
Если же увеличить цену 4-го вида продукции до 10, то 6 , 6 ; 4 10 * *
4 c и
следовательно нарушится оптимальность плана, изменятся все оценки, изменится
ассортимент выпускаемой продукции и спрогнозировать изменение целевой функции
невозможно.
Проведем теперь анализ прямой задачи при изменении запасов ресурсов (правых
частей ограничений).
В случае изменения запаса ресурсов в границах устойчивости базис остается
прежним, хотя значение базисных переменных изменится, т.е. сохранится ассортимент
выпуска продукции. При этом оценки * и *
yi l j остаются без изменения.
Изменение запаса первого дефицитного ресурса до 700 (т.е. дополнительно
приобретем 150 ед. этого ресурса).
700 538,8889; 726,6667, следовательно, Z b y , 1 1
1
max , где * b1 b1 b1 т.е.
Z (700 550) 1,211538 150 1,211538 181,7307.
1
max
Если же дополнительно приобрести 200 ед. первого ресурса, то
** 550 200 750
b1 , то 750 538,8889; 726,66667, следовательно, спрогнозировать
изменение Zmax невозможно, т.к. оптимальный план нарушается, все оценки будут
другими, в базис будут входить другие переменные.
Вопросы для самопроверки
1. Правила составления двойственных задач.
2. Записать математическую модель двойственной к стандартной задаче.
3. Какова модель двойственной к основной задаче?
65
4. Что является достаточным условием оптимальности планов двойственных
задач?
5. Как читается основная теорема двойственности?
6. Как найти оптимальное решение двойственной задачи, если исходная решена
симплексным методом?
7. Сформулировать теорему о равновесии.
8.Каков экономический смысл двойственных оценок? Каковы их свойства?
9. Анализ модели на чувствительность.
10. Когда можно прогнозировать изменение целевой функции в оптимальном
плане?
1.7. Математические модели транспортных задач
Классическая постановка транспортной задачи давалась в разделе (1.2.6).
Математическая модель:
min
1 1
m
i
n
j
Z cij xij при ограничениях
n
j
xij ai
1
, (i = 1, 2, …, m), (ai – мощность i-го поставщика)
m
i
xij b j
1
, (j = 1, 2, …, n). (bj – спрос j-го потребителя)
xij 0, (i = 1, 2, …, m; j = 1, 2, …, n).
Задача разрешима, если выполняется условие баланса:
n
j
j
m
i
ai b
1 1
.
Пример 1. Три поставщика, запас однородного груза у которых соответственно
100, 300, 450, должны доставить его четырем потребителям, у которых спрос на этот
груз соответственно 150, 200, 100, 400. Составить математическую модель задачи, если
известны затраты на перевозку единицы груза от поставщиков к потребителям:
.
8 6 1 4
6 9 2 5
2 5 7 3
Cij
Проверим условие баланса:
100 300 450 850,
1
m
i
ai
150 200 100 400 850,
1
n
j
b j
n
j
j
m
i
ai b
1 1
.
Составим таблицу по условию задачи.
66
Таблица 1.7.1
B B4 2 B3
150 200 100 400
8 6
6 9
2
1 4
5
3
31 X32 X33 X
450
3 A
300
2
100
7
X24
X14
X23
X13
22 X
X12
21 X
11 X
X34
5
B1
Поставщики
Потребители
A1
A2
Xij – объем
поставки от i-го
поставщика j-му
потребителю
Тогда математическая модель задачи будет иметь вид:
Z 2x11 5x12 7x13 3x14 6x21 9x22 2x23 5x24 8x31 6x32
1x33 4x34 min.
При ограничениях:
400,
100,
200,
150,
450,
300,
100,
14 24 34
13 23 33
12 22 32
11 21 31
31 32 33 34
21 22 23 24
11 12 13 14
x x x
x x x
x x x
x x x
x x x x
x x x x
x x x x
xij 0 (i 1,m; j 1,n).
Методы первоначального распределения однородного груза:
1. Метод северо-западного угла.
2. Метод минимального элемента.
3. Метод двойного предпочтения и т.д.
Рассмотрим только один метод первоначального распределения: метод
минимального элемента.
Выбираем клетку с наименьшими затратами (Сij); записываем в нее максимально
возможную поставку. При этом могут встретиться три случая: 1) ai > bj; 2) ai < bj;
3) ai = bj.
В первом случае (ai > bj) спрос потребителя Bj удовлетворяется полностью
поставщиком Aj (ai = bj). Поэтому потребитель Bj в дальнейшем исключается из
распределения.
Во втором случае (ai < bj) исключаем из распределения поставщика Ai, записав в
клетку (i, j) поставку ai.
В третьем случае (ai = bj) принимаем хij = ai, затем записываем нуль в следующую
по строке или столбцу клетку и исключаем из распределения и i-го поставщика (Ai) и j-
го потребителя (Bj).
67
1.7.1. Теоремы о разрешимости транспортной задачи
Теорема 1. Транспортная задача при выполнении условия баланса всегда имеет
оптимальный план.
Доказательство.
Из основной теоремы линейного программирования следует, что необходимо
доказать существование хотя бы одного допустимого решения и ограниченность
целевой функции на множестве планов.
Пусть .
1 1
a b M
n
j
j
m
i
i
Докажем, что значение
M
a b
x
i j
ij является допустимым планом задачи.
Т.к. xij 0 и удовлетворяет системе
,
1
1 1
i i
j
i
i j
ij a
M
M
a
M
n
j
b
a
n
j M
n a b
j
x
1 .
1 1
j j
i
j
i j
ij b
M
M
b
M
m
i
a
b
m
i M
m a b
i
x
Докажем ограниченность Z на множестве планов. Выберем из Сij наименьшее
C minCij и наибольшее C maxCij .
,
1 1 1 1 1 1 1
C M
m
i
a
m
i
n
j
x C
m
i
n
j
C x C
m
i
n
j
Z cij xij ij ij i
Z C M,
,
1 1 1 1 1 1 1
C M
m
i
a
m
i
n
j
x C
m
i
n
j
C x C
m
i
n
j
Z cij xij ij ij i
Z C M,
C M Z C M.
Теорема доказана.
Отыскание оптимального плана начинается всегда с отыскания первоначального
опорного плана. Система ограничений транспортной задачи состоит из m n
неизвестных и m+n ограничений. Но эта система ограничений содержит в общем
случае меньше, чем m+n линейно независимых уравнений.
Теорема 2. Система ограничений транспортной задачи содержит m+n–1
положительных координат
Теорема 3 (о потенциалах).
Теорема о потенциалах применяется при дальнейшем решении задачи, когда
необходимо проверить оптимальность первоначального распределения однородного
груза.
Теорема о потенциалах. Если 0 0
X xij оптимальный план транспортной
задачи, то ему соответствует система из m n чисел , 0
ui и , 0j
v удовлетворяющих
условиям
68
1) 0 0 ,
ui v j cij для 0 0
xij (базисных),
2) , 0 0
ui v j cij для 0 0
xij (свободных),
i = 1, 2, …, m; j = 1, 2, …, n.
Доказательство.
Рассмотрим модель закрытой транспортной задачи
,
,
1
1
j ij mj j
i ij in i
x x x b
x x x a
xij 0,
m
i
n
j
Z cij xij min
1 1
.
Составим к ней двойственную. Пусть каждому ограничению вида
xi1 xij xin ai
соответствует в двойственной задаче переменная ui , а каждому ограничению вида
x1 j xij xmj bj - переменная v j .
Тогда двойственная задача запишется так
ui v j cij , i = 1, 2, …, m; j = 1, 2, …,n.
.
1 1
W a u b v max
n
j
j j
m
i
i i
Структура левой части ограничений двойственной задачи видна из того, что каждая
переменная xij встречается лишь в двух ограничениях исходной задачи, а именно, в
i м ограничении
xi1 xij xin ai ,
которому соответствует переменная ui , и в j м ограничении
x1 j xij xmj b j ,
которому соответствует переменная v j .
Пусть ( ) * *
X xij оптимальный план исходной задачи. Тогда двойственная задача
также имеет оптимальный план
( , ). * * *
Y ui v j
Из теоремы о равновесии следует, что положительной компоненте в оптимальном
плане исходной задачи соответствует ограничение двойственной задачи, выполняемое
как строгое равенство. Нулевой компоненте в оптимальном плане исходной задачи
соответствует ограничение двойственной задачи, выполняемое как неравенство, т.е.
, * *
ui v j cij для 0 *
xij ,
, * *
ui v j cij для 0 *
xij .
Из теоремы следует: для того чтобы опорный план был оптимальным,
необходимо выполнение следующих условий:
i = 1, 2, …, m,
j = 1, 2, …, n,
69
а) для каждой занятой клетки сумма потенциалов равна тарифу этой клетки
ui v j cij ;
б) для каждой свободной клетки сумма соответствующих ей потенциалов должна
быть меньше тарифа этой клетки
ui v j cij .
Может оказаться, что для некоторых свободных клеток сумма потенциалов равна
тарифу. Это является признаком альтернативного оптимума.
Если хотя бы для одной свободной клетки не выполняется условие (3.2), то
опорный план не будет оптимальным и его можно улучшить, занеся поставку в ту
клетку, для которой не выполняется условие оптимальности.
1.7.2. Алгоритм решения транспортной задачи методом потенциалов
1. Составляем исходный опорный план.
2. Находим потенциалы потребителей и поставщиков. Для этого составляем
систему уравнений
ui v j cij ,
где cij тарифы занятых клеток. Уравнений в системе будет столько, сколько
заполнено клеток, т.е. m n 1. Потенциалов m n. Поскольку число неизвестных
превышает на единицу число уравнений, то одному неизвестному предадим
произвольное значение, например, положим u1 0, остальные неизвестные находим из
уравнений (3.1).
3. Для каждой свободной клетки находим сумму потенциалов, соответствующих
этой клетке. Назовем ее косвенным тарифом и обозначим ' .
cij ui v j
4. Определим разности между тарифами и косвенными тарифами ' .
Eij cij cij
Эти разности называются характеристиками свободных клеток.
Если все характеристики неотрицательны, то план оптимален.
Если среди характеристик есть хотя бы одна отрицательная, то план можно
улучшить. Отрицательные характеристики обычно записывают в верхний правый угол
клетки, заключают в кружок.
5. Для улучшения плана занесем поставку в ту клетку, которая соответствует
наименьшей отрицательной характеристике. Для определения величины поставки
отметим выбранную клетку знаком “+” и построим для нее “контур” (или “цепь”).
Для контура характерно следующее:
1. Контур является замкнутой ломаной, состоящей из горизонтальных и
вертикальных отрезков.
2. Вершины контура лежат в занятых клетках, за исключением клетки, для которой
контур строится.
3. Отрезки контура могут пересекать занятые клетки, не являющиеся вершинами
данного контура.
4. Каждой свободной клетке соответствует только один контур.
Некоторые разновидности контуров показаны в табл. 1.7.2.1.
70
Таблица 1.7.2.1
Двигаясь по контуру от клетки, отмеченной знаком “+”, поочередно проставляем в
вершинах знаки “-” и “+”.
Затем находим объем поставки Q min xij , где xij величина груза в клетках
(вершинах контура), отмеченных знаком “-”.
Эта величина Q и определяет объем поставки, который перераспределяется по
контуру, т.е. прибавляется к величинам поставок в клетках со знаком “+” и вычитается
из объемов поставок в клетках, обозначенных знаком “–”.
Получаем новый опорный план и проверяем его на оптимальность. Процесс
продолжается до тех пор, пока все характеристики свободных клеток станут
неотрицательными.
Пример 1. Решить транспортную задачу
Имеются четыре поставщика с определенными запасами однородного груза ai
=(80; 70; 20; 30) и пять потребителей, спрос на этот груз у которых равен bj = (40; 60;
30; 40; 30).
Кроме того задана матрица затрат на перевозку единицы груза от i-го
поставщика j-му потребителю:
.
3 7 4 3 1
4 2 5 4 3
3 6 4 5 2
2 4 1 3 5
Cij
Проверим условие разрешимости задачи:
n
j
j
m
i
ai b
1 1
.
80 70 20 30 200,
4
i 1
ai
40 60 30 40 30 200.
5
j 1
bj
Условие выполняется, следовательно, задача имеет оптимальное решений.
Составим первоначальную таблицу и выполним первое распределение груза
методом минимального элемента.
71
Таблица 1.7.2.2
Ui
40
2
1
3
2
1
30
B1
V1=2 V2=4 V3=1 V4=3 V5=0
U4=1
U3=-2
U2=2
U1=0
V j
2
0
30
5
3
30
4 3
30 10
4
20
40
30 3 7
A4
B2 B3 B4 B5
40 60 30 40
4
6
5 4
5
3
3 20 A
70
4
80
Ai
Bj
A1
A2
Поставку выполняем вначале в клетки с минимальным тарифом.
Проверим второе условие разрешимости. Количество базисных переменных (т.е.
заполненных клеток) должно быть m+n–1, где m =4 – число поставщиков, а n = 5 –
число потребителей, тогда m+n–1=4 + 5 – 1 = 8.
Так как при первом распределении только семь заполненных клеток, то
необходимо в пустую клетку таблицы выполнить нулевую поставку и считать эту
клетку заполненной. Нуль ставится таким образом, чтобы было невозможно составить
замкнутого контура по заполненным клеткам.
Введем нулевую поставку в пустую клетку (2. 5).
Определим первоначальное значение целевой функции:
Z1 40 2 30 1 10 3 40 6 30 5 20 2 30 1 600.
Проверим полученный первый план на оптимальность методом потенциалов.
Из первого условия оптимальности: Cij Ui Vj (для заполненных клеток)
следует
1.
2,
2,
5,
6,
3,
1,
2,
4 5
3 2
2 5
2 4
2 2
1 4
1 3
1 2
U V
U V
U V
U V
U V
U V
U V
U V
В системе 8 уравнений, а переменных 9, следовательно, одна переменная
свободная и ей можно придать нулевое значение.
Пусть U1 0, тогда V3 1, V4 3, следовательно, U2 5 3 2, тогда V5 2 2 0 и
U4 1 0 1, V2 6 2 4, V4 5 2 3.
72
+
+
–
30
40 10
–
Рис.10
Пустую клетку отмечаем знаком “+”, затем знаки чередуются в каждой соседней
вершине (рис. 10). По контуру необходимо перераспределить минимальный объем
груза, расположенного в вершинах контура отмеченных знаком минус.
min 40; 30 30.
Следовательно, перераспределяем 30 единиц груза по контуру и тогда получим
следующее распределение при Z2 = 600 – 30 = 570.
Таблица 1.7.2.3
Ui
10
2
1
3
2
1
30
B1
V1=2 V2=5 V3=1 V4=3 V5=1
U4=0
U3=-3
U2=1
U1=0
V j
2
0
30
5
3
30
4 3
30 40
4
20
40
30 3 7
A4
B2 B3 B4 B5
40 60 30 40
4
6
5 4
5
3
3 20 A
70
4
80
Ai
Bj
A1
A2
И этот план не оптимален, т.к. есть E12 4 (5 0) 4 5 1 0.
Составим контур перераспределения.
+
+
–
30 40
10
–
Рис. 11
Перераспределим min 10; 40 10.
Таблица будет иметь вид:
73
Таблица 1.7.2.4
Ui
10
2
1
3
2
1
30
B1
V1=1 V2=4 V3=1 V4=3 V5=0
U4=0
U3=-2
U2=2
U1=0
V j
2
0
30
5
3
40
4 3
30 40
4
20
30
30 3 7
A4
B2 B3 B4 B5
40 60 30 40
4
6
5 4
5
3
3 20 A
70
4
80
Ai
Bj
A1
A2
При этом распределении план оптимален, т.к. все Eij 0.
Т.к. E44 0, то план не единственный Zmin = 570 – 10 = 560.
Проверим второе условие оптимальности: Eij cij (ui v j ) 0 (для пустых
клеток).
E12 4 (0 4) 0; E15 5 (0 0) 5; E21 3 (2 2) 1 0; E23 4 (2 1) 1;
E43 4 (1 1) 2; E33 5 ( 2 4) 3; E34 4 ( 2 3) 3; E35 3 ( 2 0) 5;
E41 3 (1 2) 0; E42 7 (1 4) 2; E44 3 (1 3) 1 0.
Есть две отрицательные характеристики, следовательно план не оптимален.
Характеристика Eij показывает на сколько изменится целевая функция, если в
клетку (i, j) переместить единицу груза. Составим контур перераспределения в клетку
(4. 4) с характеристикой E44 1.
Контур должен быть замкнутым, единственным, проходить через заполненные
клетки (в вершинах), линии контура проходят только по строкам и столбцам.
1.7.3. Открытая транспортная задача
Если в транспортной задаче не выполняется условие баланса, т.е.
n
j
j
m
i
ai b
1 1
, то
такие задачи называют открытыми.
Если
n
j
j
m
i
ai b
1 1
, то модель задачи имеет вид:
m
i
n
j
Z cij xij min
1 1
74
m
i
ij j
n
j
ij i
x b
x a
1
1
,
,
xij 0.
Чтобы привести задачу к задаче закрытого типа, вводится дополнительный
фиктивный потребитель, спрос которого
n
j
j
m
i
bф ai b
1 1
. Затраты на перевозку
единицы груза для фиктивного потребителя равны нулю.
Если
n
j
j
m
i
ai b
1 1
, то модель задачи имеет вид:
m
i
n
j
Z cij xij min
1 1
m
i
ij j
n
j
ij i
x b
x a
1
1
,
,
xij 0.
Для того чтобы привести задачу к задаче закрытого типа, необходимо ввести
фиктивного поставщика, с объемом возможных поставок:
.
1 1
m
i
i
n
j
aф bj a
Затраты на перевозку единицы груза от фиктивного поставщика тоже равны нулю.
Вопросы для самопроверки
1. Постановка транспортной задачи.
2. Условия разрешимости транспортной задачи.
3. Методы первоначального распределения
4. Суть метода минимального элемента.
5. Теорема о потенциалах (с доказательством).
6. Алгоритм решения транспортной задачи методом потенциалов.
7. Задачи открытого типа.
i = 1, 2, …, m,
j = 1, 2, …, n,
i = 1, 2, …, m,
j = 1, 2, …, n.
75
1.8. Модели сетевого планирования и управления
1.8.1. Назначение и области применения сетевого планирования и
управления
При планировании сложных комплексов взаимосвязанных работ и управления
ходом их выполнения наиболее эффективны методы сетевого планирования и
управления (СПУ). Доступность и простота этих методов позволяет широко
использовать их в практической работе. В рамках теории исследования операций
рассматривается большое количество практических задач, которые можно
сформулировать и решить как сетевые модели. Примеры таких задач:
1) Проектирование газопровода, соединяющего буровые скважины морского
базирования с находящейся на берегу приемной станцией. Целевая функция
соответствующая модели должна минимизировать стоимость строительства
газопровода.
2) Нахождение кратчайшего маршрута между двумя городами по существующей
сети дорог.
3) определение максимальной пропускной способности трубопровода для
транспортировки угольной пульпы от угольных шахт к электростанциям.
4) Определение схемы транспортировки нефти от пунктов нефтедобычи к
нефтеперерабатывающим заводам с минимальной стоимостью перевозки.
5) Составление временного графика строительных работ (определение дат начала
и завершения отдельных этапов работ).
Система СПУ позволяет:
1. формировать календарный план реализации некоторого комплекса работ;
2. выявлять и мобилизировать резервы времени, трудовые, материальные и
денежные ресурсы;
3. осуществлять управление комплексом работ по принципу «ведущего звена» с
прогнозированием и предупреждением возможных сбоев в ходе работ;
4. повышать эффективность управления в целом при четком распределении
ответственности между руководителями разных уровней и исполнителями работ.
Под комплексом работ будем понимать всякую задачу, для выполнения которой
необходимо осуществить достаточно большое количество разнообразных работ.
В основе метода СПУ лежит графическое представление комплекса работ (для
достижения поставленной цели) в виде сетевого графика, в котором показывается в
какой последовательности, когда, что, для чего необходимо выяснить, чтобы
обеспечить окончание всех работ не позже заданного срока.
Основными понятиями сетевой модели являются работа и событие.
Работа – любые действия, трудовые процессы, сопровождающиеся затратами
ресурсов или времени и приводящие к определенным результатам.
На сетевых графиках работы изображены отрезками прямых с указанием
направления (стрелками).
Работой можно назвать ожидание – протяженный во времен процесс, не
требующий затрат труда (процесс затвердевания бетона, сушки после покраски,
старения металла и т.д.).
Кроме того, есть фиктивные работы, определяющие логическую связь между
двумя или несколькими работами (событиями), требующие затрат труда, материальных
ресурсов и времени. Показывает, что возможность одной работы непосредственно
зависит от результатов другой. Продолжительность таких работ принимается равной
нулю.
76
Событие – это момент завершения какого-либо процесса, отражающий отдельный
этап выполнения проекта. Т.е. событие обозначает факт окончания всех работ в него
входящих или начала работ из него выходящих. Событие не имеет протяженности во
времени. На сетевом графике события изображаются кружками
Событие, за которым непосредственно начинается работа называется начальным
для данной работы и обозначается символом i. Событие, которому непосредственно
предшествует данная работа называется конечным для данной работы и обозначается
символом j.
Первоначальное событие в сети, не имеющее предшествующих событий,
называется исходным событием; не имеющее последующих событий – завершающим.
Событие может свершиться только тогда, когда закончатся все работы ему
предшествующие. Последующие работы могут начаться только тогда, когда событие
свершится. Отсюда двойственный характер события: для всех непосредственно
предшествующих ему работ оно является конечным, а для всех непосредственно
следующих за ним работ – начальным. При этом предполагается, что событие не имеет
продолжительности и свершается как бы мгновенно.
1.8.2. Порядок и правило составления сетевого графика
Сетевые графики составляются на начальном этапе планирования. Вначале
планируется процесс, разбивается на отдельные работы, составляется перечень работ и
событий, предусматриваются их логические связи и последовательности выполнения.
Работы закрепляются за ответственными исполнителями. С их помощью оценивается
длительность каждой работы. Затем составляется сетевой график. После упорядочения
сетевого графика рассчитываются параметры событий и работ, рассчитываются
резервы времени и критический путь.
Критический путь – это путь наибольшей продолжительности между начальным и
завершающим событиями.
Затем проводится анализ и оптимизация сетевого графика, после чего
пересчитываются все параметры событий и работ.
При построении сетевого графика необходимо соблюдать ряд правил:
1. В сетевом графике не должно быть событий, из которых не выходит ни одна
работа, за исключение завершающего события.
2. В сетевом графике не должно быть событий, в которые не входит ни одной
работы, кроме исходного события.
3. В сети не должно быть замкнутых контуров, петель, т.е. путей соединяющие
некоторые события сами с собой. Не должно быть изолированных участков.
4. Любые два события должны быть связаны не более одной работой.
5. В сетевом графике должно быть только одно исходное и одно завершающее
события.
6. Сетевой график должен быть упорядочен.
При нарушении этих условий можно вводить фиктивные работы и события.
Фиктивные работы в сетевом графике обозначаются пунктирными линиями.
Пример 1. Если два события соединены не одной, а двумя работами
1 2 ,
то можно ввести фиктивную работу и фиктивное событие.
77
1 2
2’
Пример 2. Работа А и В могут выполняться независимо друг от друга, но по
условиям производства, работа Б не может начаться раньше, чем окончится работа А.
Это обстоятельство тоже требует введения фиктивной работы С и события.
В
С
А
1
2 3’
3 4
5
Пример 3. Работа С требует для своего начала завершения работ А и В, но работа
D зависит только от завершения работы В, а от работы А не зависит, тогда требуется
введение фиктивной работы F и фиктивного события 3 .
D
F
В
А С
1
2
3’
3
4
5
Правило упорядочения сетевого графика. Понятие пути.
Упорядочение сетевого графика заключается в таком расположении событий и
работ, при котором для любой работы предшествующее ей событие расположено левее
и имеет меньший номер по сравнению с завершающим эту работу событием.
Т.е. все работы направлены слева направо от событий с меньшими номерами к
событиям с большими номерами.
Все события сетевого графика разбиваются по слоям. В первый слой поместим
исходное событие. Затем мысленно вычеркнем исходное событие и выходящие из него
работы, тогда во второй слой войдут события, которые остались без входных стрелок
(работ). Тоже самое выполняем с событиями второго слоя, т.е. мысленно вычеркиваем
сами события второго слоя и выходящие из них работы и тогда в третий слой войдут
события, оставшиеся без входных стрелок – работ.
Пример 4. Проверить упорядоченность следующего сетевого графика (рис. 12).
78
1
2
8
3
4
5
7
6
Рис. 12
Расположение событий по слоям:
1 2
3
6
4
5 7 8
Слои 1 2 3 4 5 6
Этот график не упорядочен, так как в четвертом слое номер события меньше, чем
номер события в третьем слое, поэтому необходимо поменять нумерацию этих
событий, т.е. пятое событие заменить шестым номером, а шестое пятым и тогда сетевой
график будет такого вида (рис. 13):
Рис. 13
1
2
8
3
4
6
7
5
Одно из важнейших понятий сетевого графика – понятие пути.
Путь – любая последовательность работ, в которой конечное событие каждой
работы совпадает с начальным событием следующей за ней работы.
Полный путь – любой путь, начало которого совпадает с исходным событием
сети, а конец с завершающим.
Критический путь – наиболее продолжительный полный путь в сетевом графике.
Критическими называются также работы и события, расположенные на этом пути.
Критический путь имеет особое значение в системе СПУ, так как работы этого
пути определяют общий цикл завершения всего комплекса работ, планируемых при
помощи сетевого графика. Для сокращения продолжительности проекта, необходимо в
первую очередь сокращать продолжительность работ, лежащих на критическом пути.
1.8.3. Временные характеристики сетевого графика
Параметры событий. Событие не может наступить прежде, чем свершатся все
предшествующие работы. Поэтому ранний (или ожидаемый) срок (ET) свершения j-го
события определяется продолжительностью максимального пути, предшествующего
этому событию. По сети определяется от исходного события к завершающему.
Для начального события ET = 0, для других событий определяется по формуле:
j max ETi tij ,
j
ET
где ETj – ранний срок наступления завершающего события работы (i-j),
79
ETi – ранний срок наступления начального события работы (i-j),
tij – продолжительность работы (i-j).
Поздний срок наступления события (LT) – это наиболее поздний срок, в который
может наступить событие без задержки выполнения всего комплекса работ.
Определяется при движении по сети от последнего события к исходному по формуле:
i min LTi tij ,
i
LT
где LTj – поздний срок последующего события работы(i-j),
LTi – поздний срок начального события работы (i-j).
Для критических событий ранние и поздние сроки наступления событий
совпадают. Для завершающего события эта величина совпадает с длиной критического
пути.
Временные характеристики работ. К ним относятся свободный и полный (общий)
резервы времени работ. Общий или полный резерв времени работы (i-j) обозначается
TSij и определяется из соотношения:
TSij LT j ETi tij .
Полный резерв времени работы (i-j) показывает, на сколько можно увеличить
время выполнение данной работы при условии, что срок выполнения комплекса работ
не изменится.
Свободный резерв времени (FSij) работы (i-j)представляет часть полного резерва
времени, на которую можно увеличить продолжительность работы, не изменив при
этом раннего срока ее конечного события.
Рассчитывается свободный резерв работы (i-j) по следующей формуле:
FSij ET j ETi tij .
Для критических работ TS и FS равны нулю.
Резерв времени i-го события – это разность между поздним сроком свершения i-го
события (LTi) и его ранним сроком свершения (ETi), т.е.
Ri = LTi – ETi.
События, не имеющие резерва времени (Ri =0) называются критическими.
Рассмотрим конкретный пример.
Задана следующая последовательность работ с их временными характеристиками:
Таблица 1.8.3.1
Работа (1,2) (1,3) (1,4) (2,4) (2,5) (3,4) (3,6) (4,5) (4,6)
Продолжительность 8 6 6 8 4 7 4 10 3
(4,7) (5,7) (5,8) (6,7) (6,9) (7,8) (7,9) (7,10) (8,10) (9,10)
9 10 13 10 7 6 5 9 12 9
Построим сетевой график так, чтобы все дуги работы были направлены слева
направо (рис). Над дугами проставлены длительности работ.
10 10 6
12
9
3 10 5
4 7
8
9 9
4 13
8
6
7
6
2
10
9
8
7
5
6
4
3
1
Рис. 14
80
Критический путь представляет собой путь от начальной до конечной работы,
имеющий наибольшую длительность. Любое замедление в выполнении работ
критического пути неизбежно приведет к срыву выполнения всего комплекса работ,
поэтому критическому пути и уделяется столько внимания.
Определим ранние сроки наступления событий:
ET1 0, ET6 max 6 4; 16 3 19,
ET2 0 8 8, ET7 max 16 9; 26 10; 19 10 36,
ET3 0 6 6, ET8 max 26 13; 36 6 42,
ET4 max 0 6; 8 8; 6 7 16, ET9 max 19 7; 36 5 41,
ET5 max 8 4; 16 10 26, ET10 max 42 12; 41 9 54.
Теперь выполним расчеты в обратном направлении и найдем поздние сроки
наступления событий:
LT10 ET10 54, LT5 min 42 -13; 36 -10 26,
LT9 54 9 45, LT4 min 36- 9; 26- 3; 26-10 16,
LT8 54 12 42, LT3 min 26 - 4; 16 - 7 9,
LT7 min 54 - 9; 42 - 6; 45- 5 36, LT2 min 26- 4; 16-8 8,
LT6 min 45- 7; 36 -10 26, LT1 min 16- 6; 9 - 6; 8 -8 0.
Рассчитаем резервы времени события:
R1 0 0 0, R6 26 19 7,
R2 8 8 0, R7 36 36 0,
R3 9 6 3, R8 42 42 0,
R4 16 16 0, R9 45 41 4,
R5 26 26 0, 54 54 0. 10 R
Например, R6 7, это означает, что на данный промежуток времени может быть
задержано выполнение соответствующих работ без риска задержать проект в целом.
Другой способ вычисления показателей – табличный.
События отмечаются в квадратах «главной» диагонали. Работы отмечаются
дважды в верхних и нижних «побочных» квадратах таблицы. Номер строки
соответствует предыдущему событию, номер столбца – последующему. В нижних
«побочных» квадратах наоборот.
Заполним таблицу.
1. Сначала заполняем числители верхних и нижних «побочных» квадратов. В них
записываем продолжительности соответствующих работ.
2. Заполняем знаменатели верхних «побочных» квадратов как суммы числителя
главного квадрата и числителя верхнего «побочного» в той же строке.
3. Числитель первого главного квадрата принимается равным нулю, числители
остальных главных квадратов равны максимуму знаменателей верхних «побочных»
квадратов в том же столбце.
4. Знаменатель последнего главного квадрата принимается равным числителю
этого квадрата. Знаменатели нижних «побочных» квадратов равны разности
знаменателя главного и числителя «нижнего» побочного в той же строке.
81
5. Знаменатели главных квадратов равны минимуму знаменателей «нижних»
побочных в том же столбце (табл. 1.8.3.1).
Таблица 1.8.3.1
Расчет показателей сетевого графика
1 2 3 4 5 6 7 8 9 10
1 0
0
8
8
6
6
6
6
2 8
0
8
8
8
16
4
12
3 6
3
6
9
7
13
4
10
4 6
10
8
8
7
9
16
16
10
26
3
19
9
25
5
4
22
10
16
26
26
10
36
13
39
6
4
22
3
23
19
26
10
29
7
26
7
9
27
10
26
10
26
36
36
6
42
5
41
9
45
8
13
29
6
36
42
42
12
54
9
7
38
5
40
41
45
9
50
10
9
45
12
42
9
45
54
54
Из табл. 1.8.3.1 находятся показатели графика:
1. Ранние сроки наступления событий (числители главных квадратов).
2. Поздние сроки наступления событий (знаменатели главных квадратов).
3. Резервы времени событий (разность между знаменателем и числителем
главного квадрата). В нашем случае критическими событиями (не имеющими резервов)
являются 1, 2, 4, 5, 7, 8, 10. Они составляют критический путь. Продолжительность
критического пути равна 54 (числитель или знаменатель последнего главного
квадрата).
4. Ранний срок окончания работ (знаменатели верхних «побочных» квадратов).
5. Поздний срок окончания работ (знаменатели соответствующих нижних
«побочных» квадратов).
6. Общие резервы времени работ (разность между знаменателем главного
квадрата и знаменателем верхнего «побочного» в том же столбце).
7. Свободные резервы времени работ (разность между числителем главного
квадрата и знаменателем верхнего «побочного» в том же столбце).
Воспроизведем график сети, проставив над каждым событием слева – ранний, а
справа – поздний сроки наступления события (рис. 15).
82
36/36 6
10 10
12
9
3 10 5
4 7
19/26
8
9
9
4 13
8
6
7
6
54/54
42/42
6/9 41/45
26/26
0/0 16/16
8/8
2
10
9
8
7
5
6
4
3
1
Рис. 15
Критический путь проходит вдоль работ 1-2-4-5-7-8-10 и его продолжительность
равна 54.
Окончательно имеем:
Критический путь Продолжительность
1-2
2-4
4-5
5-7
7-8
8-10
8
8
10
10
6
12
Общая 54
Временные характеристики работ
Некритические
работы
Продолжительность Общий резерв Свободный резерв
1-3
1-4
2-5
3-4
3-6
4-6
4-7
5-8
6-7
6-9
7-9
7-10
9-10
6
6
4
7
4
3
9
13
10
7
5
9
9
9-0-6=3
16-0-6=10
26-8-4=14
16-9-7=0
26-6-4=16
26-16-3=7
36-16-9=11
42-26-13=3
39-19-10=7
45-19-7=19
45-36-5=4
54-36-9=9
54-41-9=4
6-0-6=0
16-0-6=10
26-8-4=14
16-6-7=3
19-6-4=9
19-16-4=0
36-16-9=11
42-26-13=3
36-19-10=7
41-19-7=15
41-36-5=0
54-36-9=9
54-41-9=4
Вопросы для самопроверки
1. Основные элементы сетевого графика.
2. Определения работы, события и пути.
3. Какой путь называют критическим?
4. Условия составления сетевого графика.
5. Временные характеристики событий.
6. Временные характеристики работ.
7. Формулы расчета временных характеристик и методы.
83
2. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Динамическое программирование (ДП) – это метод нахождения оптимальных
решений в задачах с пошаговой (многоэтапной) структурой.
В экономической практике встречается несколько типов задач, которые по
постановке или способу решения относятся к задачам ДП. Это задачи управления
запасами, задачи календарного планирования производства, задачи распределения
капитальных вложений между возможными направлениями их использования, задачи
составления календарных планов текущего и капитального ремонта сложного
оборудования и его замены.
Модели ДП позволяют на основе стандартного подхода принимать важные
микроэкономические решения. И если каждое взятое в отдельности такое решение
малосущественно, то в совокупности эти решения могут оказать большое влияние на
прибыль.
2.1. Постановка задачи динамического программирования
Пусть рассматривается задача, распадающаяся на n шагов или, этапов, например,
планирование деятельности предприятия на несколько лет, поэтапное планирование
инвестиций, управление производственными мощностями в течение длительного срока.
В результате управления система (объект управления) S переходит из начального
состояния S0 в состояние Sn.
Показатель эффективности задачи в целом обозначим через Z, а показатели
эффективности на отдельных шагах – через Zi, i 1,n.
Если целевая функция Z обладает свойством аддитивности, т.е.
,
1
n
i
Z Zi (2.1.1)
То можно найти оптимальное решение задачи методом ДП.
Таким образом, динамическое программирование это метод оптимизации
многошаговых или многоэтапных процессов, критерий эффективности которых
обладает свойством (2.1.1). В задачах ДП критерий эффективности называется
выигрышем. Данные процессы управляемые и от правильности управления зависит
величина выигрыша.
Определение 1. Переменная xi, от которой зависят выигрыш на i-м шаге и,
следовательно, выигрыш в целом, называется шаговым управлением, i 1,n.
Определение 2. Управлением процесса в целом, переводящим систему из
состояния S0 в состояние Sn, называется последовательность шаговых управлений
X (x1, x2 ,..., xi ,..., xn ).
Определение 3. Оптимальное управление x* – это значение управления x, при
котором значение Z(x*) является максимальным (или минимальным, если требуется
уменьшить проигрыш)
Z* Z(x*) max Z(x) , x ,
где область допустимых управлений.
Оптимальной управление x* определяется последовательностью оптимальных
шаговых управлений
* ( *, *,..., *,..., * ).
1 2 i n
x x x x x
84
Обозначим через sk состояние системы после k-го шага управления. Получаем
последовательность состояний s0 , s1,..., sk 1,..., sk ,...sn 1, sn , которую изобразим
кружками (рис.16).
xn
…
xk xk+1 Xn-1
…
x1 x2 xk-1
S0 S1 Sk-1 Sk Sn-1 Sn
Рис. 16
Показатель эффективности рассматриваемой управляемой операции зависит от
начального состояния и управления:
Z F(s0 , x).
Предполагается, что состояние S0 в состояние Sk, системы в конце k-го шага
зависит только от предшествующего состояния sk-1 и управления на k-ом шаге xk и не
зависит от того, каким путем система пришла в него. Такие процессы называются
процессами без последствия. Сформулированное положение записывается в виде
уравнений
sk k (sk 1, xk ), k 1, 2,..., n, (2.1.2)
которые называются уравнениями состояний.
Таким образом. Задача пошаговой оптимизации (задача ДП) формулируется так:
определить такое допустимое управление x, переводящее систему s из состояния s0 в
состояние sn, при котором целевая функция Z принимает наибольшее (наименьшее)
значение.
Особенности задач ДП.
1. Задача оптимизации интерпретируется как n-шаговый процесс управления.
2. Целевая функция равна сумме целевых функций каждого шага.
3. Выбор управления на k-ом шаге зависит только от состояния системы к этому
шагу, и не влияет на предшествующие шаги (нет обратной связи).
4. Состояние sk после k-го шага управления зависит только от предшествующего
состояния sk-1 и управления xk (отсутствие последствия).
5. На каждом шаге управление xk зависит от конечного числа управляющих
переменных, а состояние sk – от конечного числа параметров.
2.2. Принципы динамического программирования
Идея постепенной, пошаговой оптимизации составляет суть метода
динамического программирования. Оптимизация одного шага, как правило, проще
оптимизации всего процесса в целом. При этом принцип ДП вовсе не предполагает, что
каждый шаг оптимизируется изолированно, независимо от других. Напротив,
пошаговое управление должно выбираться с учетом всех его последствий.
Пусть, например, планируется работа группы промышленных предприятий, из
которых одни заняты выпуском предметов потребления, а другие производят для этого
машины. Задачей является получение за N лет максимального объема выпуска
предметов потребления. Пусть планируются капиталовложения на первый год. Исходя
из узких интересов этого года, мы должны были бы все средства вложить в
производство предметов потребления, пустить имеющиеся машины на полную
мощность и добиться к концу года максимального объема выпуска продукции. Однако
относительно всего периода планирования такое решение будет нерациональным.
Необходимо выделить часть средств на производство машин. При этом объем
85
продукции за первый год снизится, зато будут созданы условия, позволяющие
увеличить его выпуск в последующие годы.
Другой момент, который следует учитывать при выборе управления на данном
шаге, – это возможные варианты окончания предыдущего шага. Например, при
определении количества средств, вкладываемых в предприятие в i-ом го, необходимо
знать, сколько осталось в наличии к этому году и какая прибыль получена в
предыдущем (i-1)-ом году. Таким образом, при выборе шагового управления
необходимо учитывать: 1) возможные исходы предыдущего шага и 2) влияние
управления на все оставшиеся до конца процесса шаги.
В задача ДП первый пункт учитывают, делая на каждом шаге условные
предположения о возможных вариантах окончания предыдущего шага и проводя для
каждого из вариантов условную оптимизацию. Выполнение второго пункта
обеспечивается тем, Что в задачах ДП условная оптимизация проводится от конца
процесса к началу. Сперва оптимизируется последний N-й шаг, на котором не надо
учитывать возможные воздействия выбранного управления xN на все последующие
шаги, так как эти шаги просто отсутствуют.
Для каждого возможного шага (N-1)-го шага проводят условную оптимизацию N-
го шага и определяют условное оптимальное управление ( ) *
xN sN 1 на N-м этапе.
Завершив анализ конечного этапа, рассматривают аналогичную задачу для
предпоследнего этапа, требуя, чтобы целевая функция достигла экстремального
значения на двух последних этапах вместе. Для этого делаются всевозможные
предположения об исходах окончания (N-2) го шага и для каждого исхода находится
такое управление на (N-1)-ом шаге, при котором эффект за последние два шага (из них
последний уже оптимизирован) будет максимален. Тем самым мы найдем для каждого
исхода (N-2)-го шага условно-оптимальное управление ( ) *
xN 1 sN 2 на (N-1)-ом шаге и
условно-оптимальное значение функции цели на последних двух шагах.
Таким же образом, действуют на всех остальных шагах от конца к началу и
получают последовательность условно-оптимальных управлений
*( ), *( ),..., * ( ).
x1 s0 x2 s1 xN sN 1 Так как начальное состояние системы S0 определяется
однозначно, то ( ) *
x1 s0 является оптимальным управлением для первого шага. Далее из
уравнений (4.2) находим оптимальное состояние системы ) * ( , *
s1 1 s0 x1 на начало
второго этапа. Но для всех возможных состояний на начало второго этапа уже найдены
оптимальные управления. И, зная *
s1 , установим оптимальное управление для второго
шага *( )
x2 s1 и т.д. Проделав обратное движение по условно-оптимальным управлениям
от начала к концу, получим оптимальное решение задачи ДП:
* ( *, *,..., * ).
x x1 x2 xN
Таким образом, в процессе оптимизации управления методом ДП многошаговый
процесс проходит дважды. Первый раз – от конца к началу, в результате чего находятся
условно-оптимальные управления и условно-оптимальное значение целевой функции
для каждого шага, в том числе оптимальное управление для первого шага и
оптимальное значение функции цели для всего процесса. Второй раз – от начала к
концу, в результате чего находятся уже оптимальные управления на каждом шаге с
точки зрения всего процесса. Первый этап сложнее и длительнее второго, на втором
остается лишь отобрать рекомендации, полученные на первом. Следует отметить, что
понятие «конец» и «начало» можно поменять местами и разворачивать процесс
86
оптимизации в другом направлении. С какого конца начать – диктуется удобством
выбора этапов и возможных состояний на их начало.
2.3. Принцип оптимальности
Функциональные уравнения Беллмана
В основе метода динамического программирования лежит принцип
оптимальности Беллмана, формулирующийся следующим образом: управление на
каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей всех
оставшихся до конца процесса шагах, включая выигрыш на данном шаге.
Так как оптимальной стратегией может быть только та, которая одновременно
оптимальна и для любого количества оставшихся шагов, ее можно строить по частям:
сначала для последнего этапа, затем для двух последних, для трех и т.д., пока не
придем к первому шагу. Получается, что принцип оптимальности связан со вторым
принципом – погружения, согласно которому при решении исходной задачи ее как бы
погружают в семейство подобных ей и решают для одного последнего этапа, для двух
последних и т.д. пока не получат решение исходной задачи.
Дадим математическую формулировку принципа оптимальности для задач с
аддитивным критерием оптимальности, т.е.
( , ) ( , ).
1
0 1
N
i
Z Z s x Zi si xi (2.3.1)
Будем считать известными начальное s0 и конечное sn состояние системы. Найдем
оптимальное управление ) * ( *, *,..., *
x x1 x2 xN , при котором значение целевой функции
является максимальным при ограничениях x ..
Для решения этой задачи погружаем ее в семейство себе подобных.
Пусть N , N 1,N ,..., 1,2,...,N соответственно области определения для
подобных задач на последнем этапе, двух последних и т.д.; область определения
исходной задачи.
Пусть F1(SN 1),F2 (SN 2 ),..., Fk (SN k ),..., FN (S0 ) соответственно условно-
оптимальные значения функции цели на последнем этапе, двух последних и т.д. на k
последних и т.д.; на всех N этапах.
Определяем SN 1 возможные состояния системы на начало N-го этапа.
Находим:
1( 1) max N ( N 1, N ).
N N
N Z s x
x
F S (2.3.2)
Для двух последних этапов получаем
( ) max 1( 2, 1) 1( 1) .
1 1,
2 2 N N N N
N N N
N Z s x F s
x
F S (2.3.3)
Аналогично:
( ) max 2 ( 3, 2 ) 2 ( 2 ) ,
2 2, 1,
3 3 N N N N
N N N N
N Z s x F s
x
F S (2.3.4)
………………………………………………………………………………………
( ) max 1( , 1) 1( 1) ,
1 1,...,
N k N k N k k N k
N k N k N
k N k Z s x F s
x
F S (2.3.5)
……………………………………………………………………………………………
( ) max 1( 0 , 1) 1( 1) .
1
0 Z s x F s
x
FN S N (2.3.6)
87
Выражения (2.3.2) – (2.3.6) называются функциональными уравнениями
Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, так
как для нахождения оптимального управления на N шагах нужно знать условно-
оптимальное управление на предшествующих N-1 шагах и т.д. Поэтому
функциональные уравнения также называют рекуррентными соотношениями Беллмана.
2.4. Оптимальное распределение ресурсов как задача динамического
программирования
Пусть на реконструкцию и модернизацию основного производства объединению
выделяется некоторый объем материальных ресурсов x0. Объединение включает в себя
N предприятий, между которыми нужно распределить данный ресурс.
Средства xi, выделенные i-му предприятию ( i 1,N ), приносят в конце года
прибыль Zi(xi) усл.ед. Предполагается, что:
а) размер прибыли зависит как от выделенного количества ресурса, так и от
предприятия;
б) прибыль, получаемая каждым предприятием, измеряется в одних и тех же
единицах;
в) прибыль, получаемая любым из предприятий, не зависит от вложения средств в
другие предприятия;
г) общая прибыль объединения состоит из прибылей отдельных предприятий.
Нужно определить какое количество средств нужно выделить каждому
предприятию, чтобы суммарная прибыль была наибольшей.
Решение.
Задача оптимального распределения возникает от того, что имеется ограниченный
объем ресурса x0, т.е.
x1 x2 xN X0 , xi 0, (i 1,N). (2.4.1)
Суммарная прибыль равна:
max Z Z1(x1) Z2 (x2 ) ZN (xN ). (2.4.2)
Введем последовательность функций F1(x),F2 (x),..., FN (x), где F1(x) – это
максимальная прибыль, если бы ресурс 0 x X0 был выделен только одному
первому предприятию, F2 (x) максимальная прибыль, полученная при условии, что
ресурс 0 x X0 был распределен между двумя предприятиями, и т.д. Пусть, наконец,
FN (x) максимальная прибыль, получаемая от распределения ресурса 0 x X0
между N предприятиями. Очевидно, что FN (X0 ) max Z.
В двух случаях элементы последовательности F(x) имеют особенно простой вид:
Fi (0) 0, (i 1,N), F1(x) Z1(x), 0 x X0.
Пусть ресурс 0 x X0 распределяется между двумя предприятиями. Если x2–
объем ресурса, выделенного второму предприятию, то его прибыль составит Z2(x2).
Оставшийся ресурс x–x2 распределяется наилучшим образом. Общая прибыль для двух
предприятий составит:
( ) ( ) .
0
( ) max 2 2 1 2
2 0
2 Z x F x x
x X
F x
Рассуждая аналогичным образом, найдем рекуррентное соотношение,
связывающее Fk (x) и Fk 1(x xk ), (k 1, N) для произвольных значений 0 x X0
88
( ) ( ) .
0
( ) max 1
0
k k k k
k
k Z x F x x
x X
F x
Решение исходной задачи получим при x=X0, k=N, т.е из рекуррентного
соотношения
( ) ( ) .
0
( ) max 1 0
0
0 N N N N
N
N Z x F X x
x X
F X
Из уравнения ( 0 ) max Z(X0 )
x
FN X определяем . *
xN Зная , *
xN находим
* .
X 0 xN Следовательно ). ( * FN 1 X0 xN
Из соотношения
( ) ( * )
0
( * ) max 1 1 2 0 1
*
1 0
1 0 N N N N N
N N
N N Z x F X x x
x X x
F X x
находим
*
xN 1и т.д., т.е. процесс разворачивается в обратном направлении, при
котором находятся уже не условно-оптимальные, а оптимальные значения целевой
функции на каждом этапе и оптимальное выделение ресурса для одного, двух и более
предприятий.
Проведем численный расчет модели.
Пример 1. Планируется деятельность трех предприятий, между которыми следует
распределить 5 усл. ед. ограниченного ресурса. Полученная предприятием прибыль в
зависимости от выделенной суммы представлена в табл. 2.4.1.
Таблица 2.4.1
Выделенный объем
ресурса x, (усл. ед.)
Z1(x) Z2(x) Z3(x)
0
1
2
3
4
5
0
1,5
2
2,5
3
3,6
0
2
2,1
2,3
3,5
4
0
1,7
2,4
2,7
3,2
3,5
Пусть W=1, тогда F1(x)=Z1(x).
Значения функции F1(x) помещены в табл.1. Предположим, что ресурс x0=5
распределяется между двумя предприятиями. Тогда
F2 (x) max Z2 (x2 ) F1(x x2 ) , 0 x 5.
Произведем вычисления значений функции F2(x) и представим их в табл.2.
(1) max (0) (1); (1) (0) max 0 1,5; 2 0 2;
2
2 1 2 1
2
2
x
Z F Z F
x
F
(2) max (0) (2); (1) (1); (2) (0) max 0 2; 2 1,5; 2,1 0 3,5;
2
2 1 2 1 2 1
2
2
x
Z F Z F Z F
x
F
(3) max 2 (0) 1(3); 2 (1) 1(2); 2 (2) 1(1); 2 (3) 1(0)
2
2 Z F Z F Z F Z F
x
F
max 0 2,5; 2 2; 2,1 1,5; 2,3 0 4;
2
x
89
(4) max 2 (0) 1(4); 2 (1) 1(3); 2 (2) 1(2); 2 (3) 1(1); 2 (4) 1(0)
2
2 Z F Z F Z F Z F Z F
x
F
max 0 3; 2 2,5; 2,1 2; 2,3 1,5; 3,5 0 4,5;
2
x
(5) max 2 (0) 1(5); 2 (1) 1(4); 2 (2) 1(3); 2 (3) 1(2); 2 (4) 1(1);
2
2 Z F Z F Z F Z F Z F
x
F
(5) (0) max 0 3,6; 2 3; 2,1 2,5; 2,3 2; 3,5 1,5; 4 0 5,
2
2 1
x
Z F
(1) max (0) (1); (1) (0) max 0 2;1,7 0 2;
3
3 2 3 2
3
3
x
Z F Z F
x
F
(2) max (0) (2); (1) (1); (2) (0) max 0 3,5;1,7 2; 2,4 0 3,7;
2
3 2 3 2 3 2
3
3
x
Z F Z F Z F
x
F
(3) max 3(0) 2 (3); 3(1) 2 (2); 3(2) 2 (1); 3(3) 2 (0)
3
3 Z F Z F Z F Z F
x
F
max 0 4;1,7 3,5; 2,4 2; 2,7 0 5,2;
3
x
(4) max 3(0) 2 (4); 3(1) 2 (3); 3(2) 2 (2); 3(3) 2 (1); 3(4) 2 (0)
3
3 Z F Z F Z F Z F Z F
x
F
max 0 4,5;1,7 4; 2,4 3,5; 2,7 2; 3,2 0 5,9;
3
x
(5) max 3(0) 2 (5); 3(1) 2 (4); 3 (2) 2 (3); 3(3) 2 (2); 3(4) 2 (1);
3
3 Z F Z F Z F Z F Z F
x
F
(5) (0) max 0 5;17 4,5; 2,4 4; 2,7 3,5; 3,2 2; 3 5 0 6,4.
3
3 2 , ,
x
Z F
Таблица 2.4.2
x F1(x) Z2(x) F2(x) Z3(x) F3(x)
0 0 0 0 0 0
1 1,5 2 2 1,7 2
2 2 2,1 3,5 2,4 3,7
3 2,5 2,3 4 2,7 5,2
4 3 3,5 4,5 3,2 5,3
5 3,6 4 5 3,5 6,4
Из сводной табл. 2.4.2 находим оптимальный план распределения максимального
значения функции цели составляет 6,4 единиц, т.е.max Z 6,4. Из приведенных
расчетов значений F3(5) находим, что третьему предприятию должно быть выделено
* 2
x3 усл. ед. ресурса, остальным двум предприятиям 5–2=3 усл. ед. Из табл. 2
находим, что оптимальное распределение ресурса в 3 единицы между двумя
предприятиями доставляет объединению 4 усл. ед. прибыли. При этом второму
предприятию следует выделить 1 *
2 x усл. ед. ресурса. Отсюда * 2.
x1
Оптимальный план распределения .
2
*
1
*
2
*
* X1 X2 X3
X
Проверка очевидна: (2) (1) (2) 2 2 2,4 6,4. *
Z X Z1 Z2 Z3
90
Таким образом, для получения максимальной прибыли в размере 6,4 усл. ед.
следует по 2 усл. ед. вложить в первое и третье предприятие и 1 усл. ед. – во второе
предприятие.
Следует понимать, что полученное решение есть лишь некоторое приближение к
оптимальному, взяв более мелкий шаг оптимизации, например, вкладывать в
предприятия средства, кратные 0,5 усл. ед.
ГЛАВА 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
3.1. Постановка задачи нелинейного программирования
Во многих экономических моделях зависимость между постоянными и
переменными факторами не являются линейными. Как правило, такие показатели, как
прибыль, себестоимость, капитальные затраты на производство зависят от объема
производства, расхода ресурсов нелинейно.
В общем виде задача нелинейного программирования (ЗНП) формулируется
следующим образом:
Z f (x1, x2 ,..., xn ) max(min) (3.1.1)
( , ,..., ) , 1, 1, ,
. . . . . . . . . . . . . . . . . . . . . . . . . . .
( , ,..., ) , 1, ;
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
( , ,..., ) , 1, ;
1 2 2
1 2 1 2
1 2 1
g x x x b i m m
g x x x b i m m
g x x x b i m
i n i
i n i
i n i
(3.1.2)
где xj – управляющие переменные или решения ЗНП, j 1,n; bi – фиксированные
параметры, i 1,m; f, gi – заданные функции от n переменных, i 1,n .
Задача математического программирования, в которой либо целевая функция
(5.1), либо ограничения (5.2), либо то и другое нелинейны, называется нелинейной. На
языке математического анализа такие задачи получили название задач на условный
экстремум.
Условия неотрицательности включаются в ограничения (3.1.2). Если f и gi –
линейные функции, то получаем модель задачи линейного программирования (ЗЛП).
ЗЛП рассматриваются как частный вид задач нелинейного программирования.
Универсальные методы, которые позволяли бы решать любые нелинейные задачи
отсутствуют. В зависимости от целевой функции (3.1.1) и ограничений (3.1.2)
разработано несколько специальных методов решения, к которым относятся методы
множителей Лагранжа, квадратичное и выпуклое программирование, градиентный
методы, ряд приближенных методов, графический метод.
Решить задачу нелинейного программирования – значит найти такие значения
переменных хj, j 1,n, которые удовлетворяют системе ограничений (5.2) и доставляют
максимум или минимум функции f.
Основная трудность решения задач нелинейного программирования состоит в
том, что эти задачи являются многоэкстремальными. Наиболее изученным разделом
нелинейного программирования является выпуклое программирование, задачи
которого характеризуются тем, что любая точка локального минимума является точкой
глобального минимума.
91
3.2. Геометрическая интерпретация задачи нелинейного программирования
Рассмотрим задачу нелинейного программирования, содержащую две
переменные.
Z f (x1, x2 ) max (3.2.1)
( , ) , 1, 1, .
( , ) , 1, ;
( , ) , 1, ;
1 2 2
1 2 1 2
1 2 1
g x x b i m m
g x x b i m m
g x x b i m
i i
i i
i i
(3.2.2)
Система ограничений (3.2.2) определяет в n-мерном пространстве некоторую
область, которая является областью допустимых решений.
Решить задачу нелинейного программирования графически – это значит найти
точку, или набор точек из области допустимых решений (3.2.2), через которую
проходит линия f (x1, x2 ) C наивысшего уровня.
Решение может принадлежать либо границе, либо внутренней области
допустимых решений (3.2.2), в отличие от задач линейного программирования.
ЗНП удобно решать графическим методом, когда функция и ограничения
содержат две переменные.
Пример 1.
В области решений системы ограничений:
2 14,
2 5 30,
1 2
1 2
x x
x x
x1 0, x2 0.
определить глобальные экстремумы функций:
1) ( 4) ( 8) ; 2
2
2
Z x1 x
2) ( 2) ( 4) . 2
2
2
Z x1 x
Решение. Построим на плоскости X10X2 область допустимых решений:
x1
Zmin x1
Zmin
0 C
B
D
A
O1
Рис. 1
x1
Zmin x1
Zmax
0 C
B
D
A
Рис. 2
а) 2x1 5x2 30 прямая, которую можно построить, например, по точкам (15; 0)
и (0; 6). Область решений неравенства 2x1 5x2 30 полуплоскость, лежащая над
этой прямой, включая и саму прямую.
92
б) 2x1 x2 14 прямая, которую можно построить, например, по точкам (7; 0) и
(0; 14). Область решений неравенства 2x1 x2 14 строится аналогично.
Таким образом, с учетом условий неотрицательности переменных, областью
допустимых решений данной задачи является многоугольник OABC.
1) Линии уровня функции 2
2
2
Z (x1 4) (x 8) представляют собой семейство
окружностей с центром О1 (4;8) и радиусом r Z.
Из рисунка 1 ясно, что Zmax достигается в точке О (0; 0), а Zmin – в точке D, где
окружность касается границы области допустимых решений. Для определения
координат точки D необходимо решить систему уравнений О1D и AB. Составим
уравнение прямой О1D:
,
5
2
AB , т.к. (AB) ( О1D), то .
2
5
O1B
Используя уравнение пучка прямых: y y0 (x x0 ),
получим:
2.
2
5
( 4),
2
5
8
2 1
2 1
x x
x x
Решая систему уравнений:
6,
5
2
2,
2
5
2 1
2 1
x x
x x
получим
29
142
;
29
80
D и .
841
75
8 11
29
142
4
29
80
2 2
Zmin
Zmax достигается в точке О (0; 0). Таким образом, получаем
841
75
Zmin 11 и
0 4 2 0 8 2 80.
Zmax
2) Линиями уровня функции 2
2
2
Z x1 2 x 4 являются окружности с
центром О1(2; 4) и радиусом r Z (рис. 2).
В любой точке этой линии уровня при перемещении от центра окружности О1
функция Z возрастает, а при перемещении к центру – убывает. Таким образом,
Zmin 0 достигается в точке О1(2; 4), а Zmax 41 в точке С (7; 0).
3.3. Математические основы выпуклого программирования
Под n-мерным евклидовым пространством Rn будем понимать совокупность n-
мерных векторов (или точек) x (x1,..., xn ) с вещественными координатами xj, для
которых определены сумма x+y любых двух векторов x и y из Rn, произведение x
любого вектора n x R на произвольное вещественное число и скалярное
произведение < x, y > произвольной пары векторов x, y пространства Rnсогласно
следующим правилам:
93
,..., ), ( ,..., ).
1
, , (
( ,..., ),
( ,..., ),
1 1
1
1 1
j j n n
n
n n
x x y y y
n
j
x y x y г x
x x x
x y x y x y
С помощью скалярного произведения вводится норма для любого n x R :
, . 2 2
2
2
x x x x1 x xn
Множество точек минимума (максимума) целевой функции f(x) на множестве X
обозначим X*. Оно может содержать конечное число точек, бесконечное число точек
или быть пустым.
Задача поиска минимума или максимума целевой функции f(x) называется задачей
поиска экстремума
( *) f (x).
x X
f x extr
Если множество допустимых решений X задается ограничениями (условиями),
накладываемыми на вектор x, то решается задача поиска условного экстремума. Если
n X R , т.е. ограничения на вектор x отсутствуют, решается задача поиска
безусловного экстремума.
Определение 1. Точка x X называется точкой глобального (абсолютного)
минимума функции f(x) на множестве X, если функция достигает в этой точке своего
наименьшего значения, т.е. f (x*) f (x) для любых x X.
Определение 2. Точка x* X называется точкой локального (относительного)
минимума функции f(x) на множестве X, если существует 0, такое, что если x X и
x x* , то f (x*) f (x) .
Здесь 2 2
2
2
x x1 x xn евклидова норма вектора x.
Замечание 1.
1. В определении 1 точка x* сравнивается со всеми точками из множества
допустимых решений X, а в определении 2 – только с принадлежащими –
окрестности.
x*
X
Рис. 17
2. Если в определениях 1 и 2 знак неравенства заменить на , то получатся
определения глобального и локального максимумов.
3. Глобальный экстремум всегда является одновременно локальным, но не
наоборот.
94
Определение 3. Поверхностью уровня f(x) называется множество точек, в которых
функция принимает постоянное значение, т.е. f(x)=const. Если n=2, то поверхность
уровня изображается линией уровня на плоскости R2.
Определение 4. Функция F(X ) F(x1,..., xn ), определенная на выпуклом
множестве X n-мерного пространства, называется выпуклой на этом множестве, если
F( X1 (1 )X2 ) F(X1) (1 )FX2 (3.3.1)
для любых точек X1, X2 X и любого числа 0; 1.
Замечание.
1. Если в условии (3.3.1) изменить знак на , то получим определение
вогнутой функции.
2. Если в условии (3.3.1) неравенство выполняется как строгое, то функция
называется строго выпуклой (или строго вогнутой).
3. Функцию F(X) называют выпуклой, если она целиком лежит не выше отрезка,
соединяющего две ее произвольные точки. Функцию называют строго выпуклой, если
она лежит ниже отрезка, соединяющего две ее произвольные, но не совпадающие
точки.
F(X)
X1 X= X1+(1- )X2 X1 X
F(X)
F(X2)
F(X1)
Рис. 18
Например, функции y=x2 и y=ex являются всюду строго выпуклыми, а y=lnx
строго вогнута на интервале (0, ∞).
Рассмотрим свойства выпуклых функций.
Все рассматриваемые функции предполагаются определенными на некотором
выпуклом множестве X.
Свойства выпуклых функций:
1. Если функция F(х) выпукла, то функция –F(х) вогнута.
2. Если i (x) выпуклые функции при всех x 0, то будет выпуклым и
множество решений системы i (x) b, x 0 для любого числа b (i 1,m).
3. Выпуклая функция F(х) достигает своего глобального минимума в каждой
точке x, в которой градиент функции обращается в нуль.
4. Если F(х) выпуклая функция, то всякая точка локального минимума является
точкой ее глобального минимума.
5. Если F(х) строго выпуклая функция, то она может достигать своего
глобального минимума не более чем в одной точке. Для вогнутой функции
стационарная функция (т.е. точка, в которой равны нулю все частные производные)
всегда является точкой локального и глобального максимума.
95
Для определения выпуклости конкретной функции удобно использовать
критерий Сильвестра: дважды дифференцируемая функция F(X)=F(x1,…, xn) является
выпуклой тогда и только тогда, когда неотрицательны все главные миноры матрицы
вторых частных производных, т.е. определители
, 1, .
( ) 2
1 2
21 21 2
11 12 1
n
x x
F X
, a
a a a
a a a
a a a
i j
ij
(3.3.2)
Если все 0, то функция F(х) является строго выпуклой.
Пример 2. Показать, что функция F(х)=х1
2-4х1х2+4х2
2 является выпуклой на
множестве R2.
Находим частные производные: 2 1 4 2 ,
1
x x
x
F
4 1 8 2 ,
2
x x
x
F
2,
2
1
2
x
F
4,
1 2
2
x x
F
8.
2
2
2
x
F
Матрица вторых частных производных имеет вид .
4 8
2 4
A Ее главные
миноры 1 2 2 0, 16 16 0.
4 8
2 4
2 Следовательно, F(х) является
выпуклой при всех Х.
3.4. Метод множителей Лагранжа. Экономический смысл множителей
Лагранжа
Метод множителей Лагранжа является классическим методом решения задач
математического программирования (в частности выпуклого). При практическом
применении метода могут встретиться значительные вычислительные трудности,
сужающие область его использования. Метод Лагранжа активно используется как
основа для теоретического анализа.
Пусть требуется решить задачу нелинейного программирования следующего
вида:
Z f (x1, x2 ,..., xn ) max(min) (3.4.1)
( , ,..., ) ,
( , ,..., ) ,
( , ,..., ) ,
1 2
2 1 2 2
1 1 2 1
m n m
n
n
g x x x b
. . . . . . . . . . . . . . . . . . . . . . . . . . .
g x x x b
g x x x b
(3.4.2)
где функции f, gi, i 1,m непрерывны, и непрерывны их частные производные по xj,
j 1,n. Это – классическая задача нахождения условного экстремума. Обычно
предполагается, что n>m и разность n–m называется числом степеней свободы данной
задачи.
Эта задача отличается от задачи (3.1.1), (3.1.2) тем, что среди ограничений (3.4.2)
нет неравенств, нет условий неотрицательности переменных и n>m.
96
Классических подход к решению задачи (3.4.1) дает систему уравнений
(необходимые условия), которым должна удовлетворять точка Х*, доставляющая
функции f(x) локальный экстремум на множестве точек, удовлетворяющим
ограничениям (3.4.2) (для задачи выпуклого программирования найденная точка Х* в
соответствии со свойством 4 выпуклых функций будет одновременно и точкой
глобального экстремума).
Предположим, что в точке Х* функция (3.4.1) имеет локальный условный
экстремум и ранг матрицы
m n
x
g
j
i равен m. Тогда необходимые условия можно
записать в виде:
0, ( 1, ),
0, ( 1, ),
1
b g i m
L
j n
x
m g
x i
f
x
L
i i
j
j
i
i
j j
(3.4.3)
где
( ( ,..., ))
1
( 1,..., n , 1,..., m) ( 1,..., n ) i bi gi x1 xn
m
i
L x x f x x (3.4.4)
есть функция Лагранжа;
1,..., m множители Лагранжа.
Существуют такие и достаточные условия, при выполнении которых решение
системы уравнений (3.4.3) определяет точку экстремума функции f(x). При этом
исследуется знак второго дифференциала функции Лагранжа. Однако, достаточные
условия представляют главным образом теоретический интерес.
Решения задачи (3.4.1), (3.4.2) методом множителей Лагранжа:
1) составить функцию Лагранжа (3.4.4);
2) найти частные производные функции Лагранжа по всем переменным
x1,..., xn , 1,..., m и приравнять их к нулю. Тем самым будет получена система (3.4.3),
состоящая из n+m уравнений;
3) решить систему (3.4.3) и найти все стационарные точки функции Лагранжа;
4) из стационарных точек, взятых без координат 1,..., m выбрать точки, в
которых функция f(x) имеет условные локальные экстремумы при наличии
ограничений (3.4.2). Этот выбор осуществляется, например, с применением
достаточных условий локального экстремума. Часто исследование упрощается, если
использовать конкретные условия задачи;
5) определить экстремальное значение функции f в найденной точке.
Рассмотрим применение изученных методов на примере решения задачи
оптимальной реализации продукции.
Пример 3. Фирма реализует автомобили двумя способами: через магазин и через
торговых агентов. При реализации х1 автомобилей через магазин расходы на
реализацию составят 8х1+2х1
2 усл. ед., а при продаже х2 автомобилей через торговых
агентов расходы составят 2х2
2 усл. ед. Найти оптимальный способ реализации
автомобилей, минимизирующий суммарные расходы, если общее число
предназначенных для продажи автомобилей составляет 400 штук.
Решение.
Составим математическую модель задачи.
97
Целью является минимизация суммарных расходов: 8 2 2 min. 2
2
2
Z x1 x1 x
Управляющие переменные – это число автомобилей, реализуемых первым и
вторым способом: х1 и х2, соответственно.
Окончательно математическая модель имеет следующий вид:
8 2 2 min, 2
2
2
Z x1 x1 x
0.
0,
400,
2
1
1 2
x
x
x x
Функция Лагранжа имеет вид:
( , , ) 8 2 2 (400 1 2 ).
2
2
2
L x1 x2 x1 x1 x x x
Найдем частные производные функции L по х1, х2, и приравняем их к нулю.
Получим систему уравнений:
400 0.
4 0,
8 4 0,
1 2
2
2
1
1
x x
L
x
x
L
x
x
L
Решая систему, найдем
х1=199, х2=201, =804.
Определитель, составленный из вторых частных производных функции L по х1, х2
имеет вид:
16 0.
0 4
4 0
1 1
2
2 1
2
1 2
2
1 1
2
x x
L
x x
L
x x
L
x x
L
Следовательно, по теореме о достаточном условии существования условного
экстремума Z(х1, х2) в точке х1=199, х2=201 имеет экстремум 4 0,
2
1
2
x
L
поэтому в
этой точке функция Z имеет условный минимум
Zmin 161596(усл. ед).
Таким образом, для получения минимальных расходов, нужно реализовать 199
автомобилей через магазин и 201 автомобиль через торговых агентов. При этом
расходы на реализацию составят 161596 усл. ед.
Дадим множителям Лагранжа экономическую интерпретацию. Если f(x1, х2,…, xn)
– доход, соответствующий плану X=(x1, х2,…, xn), а функция gi (x1, х2,…, xn) – издержки
i-го ресурса, соответствующие этому плану, то i – цена (оценка) i-го ресурса,
характеризующая изменение экстремального значения целевой функции в зависимости
от i-го ресурса. Таким образом, метод множителей Лагранжа позволяет
проанализировать, насколько оптимальное значение целевой функции чувствительно к
изменениям констант ограничений.
Особенно важны анализ множителей Лагранжа в задачах рациональной
экономической деятельности. В экономических задачах распределения ресурсов
98
целевая функция имеет размерность стоимости, т.е. цены, умноженной на объем
продукции (например, прибыль, выручка, издержки), а с помощью ограничений
устанавливается определенное значение некоторого количества (например, затрат).
Поскольку в таких задачах с помощью множителя Лагранжа измеряют
чувствительность величины, имеющей размерность стоимости к изменениям
некоторого количества, то он имеет размерность цены. По этой причине множитель
Лагранжа часто называют теневой ценой (данного вида затрат).
Таким образом, множители Лагранжа показывают, как изменится
максимальный доход (или минимальная стоимость), если количество ресурса i-го вида
увеличится на единицу.
3.5. Теорема Куна-Таккера
В теории нелинейного программирования центральное место занимает теория
Куна-Таккера, обобщающая классический метод множителей Лагранжа на случай,
когда в нелинейной задаче, помимо ограничений равенств, содержаться также и
неравенства.
В частности, для задачи выпуклого программирования: минимизировать Z=f(x)
при ограничениях gi (x) 0 (i 1,m), (x 0), где все функции f и gi выпуклые.
Теорема Куна-Таккера устанавливает связь между оптимальным решением задачи и
седловой точкой функции Лагранжа для этой задачи:
m
i
L X f X i gi X
1
( , ) ( ) ( ) . (3.5.1)
Точка )
*
(X*, называется седловой точкой функции (5.11) , если n-мерная точка
Х* является точкой минимума функции L(X, )
*
, а m-мерная точка
*
– точкой
максимума функции L(X*, ), так что для всех Х и выполняется неравенство:
).
*
) ( ,
*
L(X*, ) L(X*, L X (3.5.2)
Теорема Куна-Таккера. Предположим, что существует вектор x 0, такой, что
gi<0 (i 1,m). Тогда необходимым и достаточным условием оптимальности вектора Х*,
принадлежащих допустимой области, является существование такого вектора ,
*
что
для всех X 0 и 0 имеет место неравенство (3.5.2).
Если функции f(х) и gi(х) являются дифференцируемыми, то неравенства (3.5.2),
где 0,
*
X* 0, эквивалентны следующим «локальным» условиям Куна-Таккера:
0,
)
*
( *,
X
L X
(3.5.3)
0,
)
*
* ( *,
X
L X
X (3.5.4)
X* 0, (3.5.5)
0,
)
*
L(X *,
(3.5.6)
99
0,
)
*
* L(X *,
(3.5.7)
0.
*
(3.5.8)
Хотя условия Куна-Таккера дают полную характеристику решения, они не
содержат конструктивного метода отыскания решения.
Пример 4. Найти 2 max. 2
2
2
Z x1 x
0, 0.
6,
2 8,
2 2,
1 2
1 2
1 2
1 2
x x
x x
x x
x x
Решим данную задачу графическим методом.
x2
x1
8
6
2
4
2 4 6
Рис. 19
–х1
2–х2
2=с,
х1
2+х2
2=–с – окружность с центром в т. О (0; 0) и r c, где c 0.
Z=–Z1,
min. 2
2
2
Z1 x1 x
Составим уравнение ОА:
(АА1): 2х1+х2=2, х2=2–2х1.
2;
AA1
Т.к. (AА1) (ОА), то ,
2
1
OA
уравнение прямой ( ).
2
1
( 0),
2
1
0
2 1
2 1
x x ОА
x x
100
Найдем координаты т. А:
2 2 ,
,
2
1
2 1
2 1
x x
x x
2,
2
5
2 2 ,
2
1
1
1 1
x
x x
0,4,
5
2
0,8,
5
4
2
1
x
x
(0,8) (0,4) 0,8. 2 2 Z
Покажем, что существует такой вектор
*
,при котором в точке оптимума
выполняются условия Куна-Таккера для функции L(X, ):
( , ) 1(2 1 2 2) 2 (8 2 1 2 ) 3 (6 1 2 ),
2
2
2
L X x1 x x x x x x x
2 2 2 ; 2 ; 2 1 2 2;
1
2 1 2 3
2
1 1 2 3
1
x x
L
x
x
L
x
x
L
x x .
L
x x
L
1 2
3
1 2
2
8 2 ; 6
Подставим х1 = 0,8 и х2 = 0,4 в выражения
2
L
и :
3
L
2
L
= 6 > 0, 4,8 0.
3
L
Следовательно, по условию (3.5.7) 2 и 3 должны принимать нулевые значения.
Согласно условию 1может принимать ненулевое значение, так как 0.
1
L
В соответствии с (3.5.4) производные
1 2
,
x
L
x
L
должны принимать нулевые
значения, так х1, х2 отличны от нуля.
0,8.
2 0,4 0.
2 0,8 2 0,
1
1
1
Следовательно, в точке (Х*,
*
) выполняются условия Куна-Таккера и она
действительно является точкой экстремума.
3.6. Задача квадратичного программирования и ее решение
Одним из частных видов задачи выпуклого программирования является задача, в
которой целевая функция содержит квадратичное слагаемое, а ограничения носят
линейный характер.
В качестве основной в квадратичном программировании рассматривается задача
минимизации функции:
n
i
n
j
d x x
n
j
f x c j x j ij i j
1 1 1
( ) (3.6.1)
при ограничениях:
0, ( 1, ).
1
(1, ),
x j n
n
j
a x b , i m
j
ij j i
(3.6.2)
101
Матрица
n n
D dij квадратичной формы предполагается симметрической и
неотрицательно определенной. В это случае функция (3.6.1) будет выпуклой.
Как и в общем случае решения задач нелинейного программирования, для
определения глобального экстремума задачи квадратичного программирования не
существует эффективного вычислительного метода, если не известно, что любой
локальный экстремум одновременно и глобальный.
С геометрической точки зрения задача (3.6.1)-(3.6.2) сводится к определению
точки выпуклого многогранника решений, через которую проходит линия уровня
поверхности f(x) , имеющая наименьшее значение функции f(x).
Необходимыми и достаточными условиями оптимальности решения Х* являются
локальные условия Куна-Таккера (3.5.3)-(3.5.8).
Функция Лагранжа в данном случае имеет следующий вид:
.
1 1 1 1 1
m
i
n
j
a x b
n
i
n
j
d x x
n
j
L c j x j ij i j i ij j i (3.6.3)
Найдем частные производные функции (5.21):
.
1
, ( 1, )
1
2
m
i
a j n
n
c d x
x
L
j j i ij
j
(3.6.4)
, ( 1, ).
1 1
i m
n
j
a x b
L
ij j i (3.6.5)
обозначим в равенствах (3.6.4) и (3.6.5)
,
1
, ( 1, )
1
2
m
i
a v j n
n
c j d j x i ij j
, ( 1, ).
1
y i m
n
j
aij x j bi i
С учетом этих обозначений условия Куна-Таккера (3.5.3)-(3.5.8), записанные в
координатной форме, примут следующий вид:
0, 0, ( 1, ),
1
0,
1
2
x v x j n
m
i
a v
n
c d x
j j j
j j i ij j
(3.6.6)
( ) 0, 0, ( 1, ).
1
0,
y i m
n
j
a x b y
j i i
ij j i i
(3.6.7)
объединяя соотношения (3.6.6) и (3.6.7), окончательно получаем:
n
j
aij x j yi bi i m
1
, ( 1, ), (3.6.8)
m
i
v a c , j n ),
n
d j x j i ij j
1
(1,
1
2 (3.6.9)
102
x j 0, v j 0, ( j 1,n), yi 0, i 0, (i 1,m), (3.6.10)
m
i
y
n
i
x jv j i i
1
0,
1
(3.6.11)
Равенства (3.6.8)-(3.6.9) образуют систему N=n+m линейных уравнений с
2N=2(n+m) неизвестными x1,..., xn ,v1,..., vn , y1,..., ym, 1,..., m.
Итак, в соответствии с локальными условиями Куна-Таккера решение
* ( *,..., *)
X x1 x2 является оптимальным для задачи (3.6.1), (3.6.2) тогда и только тогда,
когда совместно с решением V (v1,..., vn ) существуют решения ( 1,..., m),
Y ( y1,..., ym), такие, что Z (x1,..., xn ,v1,..., vn , y1,..., ym, 1,..., m) является решением
системы (3.6.8)-(3.6.10) при условии выполнения равенства (3.6.11).
Таким образом, применение теоремы Куна-Таккера для решения задачи
квадратичного программирования позволяет нелинейную задачу сводить к решению
системы линейных алгебраических уравнений при соблюдении дополнительного
комбинаторного условия (3.6.11). Это условие требует, чтобы из каждых двух
ограниченных по знаку переменных хj и vj (соответственно yi и i ) хотя бы одна
равнялась нулю. Иначе говоря, не все решения Z = (x1;…; ym) системы (3.6.8), (3.6.9)
удовлетворяют условию (3.6.11), а только те, в которых по крайней мере n+m
компонент равны нулю, т.е. столько, сколько уравнений в системе. Но таким свойством
обладают базисные решения системы. Следовательно, для поиска решения,
удовлетворяющего условию (3.6.11) удобно использовать симплексный метод. При
этом в вычислительную процедуру вносятся определенные изменения, обусловленные
спецификой рассматриваемой задачи.
Ограничения (3.6.8)-(3.6.11) представим в векторно-матричной форме:
AX EY 0V 0 b, (3.6.12)
2DX 0Y EV A c, Т (3.6.13)
X 0, Y 0, V 0, 0, (3.6.14)
X V Y 0, (3.6.15)
где
, , ,
0 1
1 0
,
1
11 1
1
11 1
1
11 1
n mn
m
T
n nn
n
m mn
n
a a
a a
A
d d
d d
E D
a a
a a
A
, .
1 1
cn
c
c
bm
b
b
Объединяя равенства (3.6.12) и (3.6.13), получим:
.
2 0
0 0
c
b
c
b
Y
X
D E A
A E
T (3.6.16)
103
Вопросы и задачи для самопроверки
1. Сформулируйте общую задачу математического программирования. При каких
условиях общая задача математического программирования является:
а) задачей линейного программирования,
б) задачей нелинейного программирования.
2. в чем состоит отличие оптимального решения задачи нелинейного
программирования от оптимального решения задачи линейного программирования.
3. Сформулируйте определения глобального и локального максимума функции.
4. Исследуйте на выпуклость следующие функции:
а) Z = 5–x1
2–x2
2;
б) Z =–x1х2+2x1.
5. Как используются экстремальные свойства выпуклых функций при решении
задачи выпуклого программирования?
6. в каком случае задача выпуклого программирования всегда имеет единственное
решение?
7. Каким условиям должны удовлетворять функции f(x1,…, xn) и gi(x1,…, xn),
чтобы метод множителей Лагранжа был применим?
8. Сформулировать условия Куна-Таккера для задачи максимизации.
9. Рассмотреть задачу отыскания минимального расстояния от начала координат
до выпуклого множества:
2 5.
4,
1 2
1 2
x x
x x
Решить задачу графически и показать, что необходимые условия Куна-Таккера в
точке минимума выполняются.
ВАРИАНТЫ ЗАЧЕТНЫХ ЗАДАНИЙ
Вариант 1
1. Множество точек n-мерного пространства называется выпускным, если любые
две точки данного множества можно соединить отрезком, который ….. данному
множеству.
2. Найти два опорных решения системы
3 2.
3 5,
2 2 4,
2 5
3 4 5
1 4 5
x x
x x x
x x x
Ответы первого опорного решения:
1)
0
X1 = (3; 1; 4; 3; 2), 2)
0
X1 = (4; 0; 5; 0; 2), 3)
0
X1 = (4; 2; 5; 0), 4)
0
X1 = (7; 0; 1; 2; 0),
5)
0
X1 = (2; 0; 5; 0; 4).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи, найти оптимальное решение двойственной задачи.
104
Z 4x1 5x2 max
0, 0.
10,
2 14,
5,
1 2
1 2
1 2
1 2
x x
x x
x x
x x
4. На предприятии имеется 4 вида ресурса и оно выпускает 4 вида продукции.
Исходные условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 5 3 4 2 730
В2 4 0 5 1 450
В3 0 6 3 4 600
В4 4 1 3 5 540
Цена 1 единицы
продукции
7 6 2 9
Найти оптимальный план выпуска продукции при котором прибыль от реализации
продукции будет оптимальным.
Требуется:
а) Составить математическую модель исходной и двойственной задачи и двойст-
венной к ней.
б) Записать оптимальный план исходной задачи ,
*
X Zmax .
в) Записать оптимальный план двойственной задач ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок (4
свойства).
д) Можно ли спрогнозировать изменение целевой функции в отчетном плане,
если дополнительно приобрести 100 ед. четвертого ресурса, если можно, то на сколько
изменится целевая функция ( Zmax ) при этом величину изменения обозначайте
Zmax .
Ответы: Zmax 1) 56,9; 2) 115,38; 3) 47,69; 4) 0.
К задаче прилагаются распечатки решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 7 6 2 9
Constraint 1 5 3 4 2 <= 730 0,4769
Constraint 2 4 0 5 1 <= 450 0
Constraint 3 0 6 3 4 <= 600 0,5692
Constraint 4 4 1 3 5 <= 540 1,1538
Solution 86 85,2308 0 22,1538 1312,769 1312,769= Zmax
105
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 86 l1 = 0 с1= 7 4,6154 12,6923
x2 85,2308 l2 = 0 с2 = 6 2,125 13,5
x3 0 l3 = 5,0769 с3 = 2 - Infinity 7,0769
x4 22,1538 l4 = 0 с4 = 9 4 11,5833
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0.4769 s1 = 0 b1 = 730 300 850
Constraint 2 y2 = 0 s2 = 83.8462 b2 = 450 366,1539 Infinity
Constraint 3 y3 = 0,5692 s3 = 0 b3 = 600 357,7778 1460
Constraint 4 у4 = 1,1538 s4 = 0 b4 = 540 444 903,3333
5. Решить транспортную задачу.
ai = (170, 130, 150, 200),
bj = (100, 190, 150, 130, 80),
.
5 6 8 7 2
2 6 4 5 4
8 3 4 2 5
3 9 5 4 3
cij
Ответы: 1) Zmin = 1200; 2) Zmin = 400; 3) Zmin = 7200; 4) Zmin = 2390;
5) Zmin = 8640.
6. Найти критический путь, длину критического пути и свободный резерв
времени работы (3-6).
15
18
10
17
20
9
12
15
10
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 50; 2) 46; 3) 40; 4) 47.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
2
2
2 Z (x1 6) (x 2)
,
3 ,
2 ,
1 2
1 2
1 2
x x
x x
x x
x1 , x2 .
106
Варианты ответов: 1) Zmax = 37; Zmin = 2,6;
2) Zmax = 40; Zmin = 2,5;
3) Zmax = 42; Zmin = 2,4.
Вариант 2
1. Если в оптимальном плане М-задачи хотя бы одна искусственная переменная
....., то система ограничений исходной задачи несовместна в области допустимых
решений.
2. Найти два опорных решения системы:
3.
2 1,
3 3 4,
3 4 5
2 4 5
1 4 5
x x x
x x x
x x x
Ответы первого опорного решения:
1)
0
X1 = (0; 1; 3; 4; 1); 2)
0
X1 = (3; 0; 1; 0; 1); 3)
0
X1 = (4; 1; 3; 0; 0); 4)
0
X1 = (0; 3; 0; 2; 1);
5) 0 X (6; 0; 2; 0; 3).
3. Решить исходную задачу симплексным методом, составить к ней
двойственную, найти оптимальное решение двойственной задачи.
Z x1 x2 x3 x4 max
0, ( 1,5).
1,
5,
1,
1 2 5
1 2 4
1 2 3
x j
x x x
x x x
x x x
j
4. На предприятии имеются 4 вида ресурсов и выпускает 4 вида продукции. Все
данные задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 5 4 6 3 600
В2 3 1 4 2 450
В3 0 5 3 7 700
В4 4 1 5 4 520
Цена 1 единицы
продукции
7 4 5 8
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальный план исходной задачи ,
*
X Zmax .
107
в) Записать оптимальный план двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок (4
свойства).
д) На сколько изменится, целевая функция в оптимальном плане, если
дополнительно приобрести 300 единиц первого ресурса.
Ответы: 1) Zmax 36,75; 2) Zmax 24,79; 3) Zmax 129,06; 4)
Zmax 125,38; 5) Zmax 300.
К задаче прилогается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 7 4 5 8
Constraint 1 5 4 6 3 <= 600 0,3675
Constraint 2 3 1 4 2 <= 450 0
Constraint 3 0 5 3 7 <= 700 0,2479
Constraint 4 4 1 5 4 <= 520 1,2906
Solution 46,6667 35,8974 0 74,1359 1065,128= Zmax
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 46 l1 = 0 с1= 7 3,6923 9,2308
x2 35,8974 l2 = 0 с2 = 4 2,4643 8,3143
x3 0 l3 = 4,4017 с3 = 5 - Infinity 9,4017
x4 74,359 l4 = 0 с4 = 8 5,3636 10,15
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0,3675 s1 = 0 b1 = 600 450 1035
Constraint 2 y2 = 0 s2 = 125,3846 b2 = 450 324,6154 Infinity
Constraint 3 y3 = 0,2479 s3 = 0 b3 = 700 175,0001 1120
Constraint 4 у4 = 1,2906 s4 = 0 b4 = 520 172,0 640
5. Решить транспортную задачу
ai = (130, 170, 150, 50)
bj = (100, 90, 150, 90, 70)
.
6 5 7 8 2
1 6 4 5 4
2 9 6 4 3
8 3 1 5 2
cij
Ответы: 1) Zmin 740; 2) Zmin 1380; 3) Zmin 670; 4) Zmin 1200; 5)
Zmin 1580.
108
6. Найти критический путь и его длину, полный резерв времени работы (2-5).
17
12
25
18
20
10
15
11
16
15
8
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 70; 2) 65; 3) 80; 4) 78; 5) 68.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом
1 2
2
2
2
Z x1 x x 6x
.
,
5,
3 ,
7,
2
1
1
1 2
1 2
x
x
x
x x
x x
Варианты ответов: 1) Zmax = 7; Zmin = -13;
2) Zmax = 5; Zmin = 0;
3) Zmax = 8; Zmin = -7.
Вариант 3
1. Признаком существования альтернативного оптимума при расчете по
симплексным таблицам является наличие …?
2. Найти два опорных решения системы уравнений.
10.
3 - 2x 6,
2 3 8,
1 3 5
1 3 4
1 2 3
x x x
x x
x x x
Ответы первого опорного решения: 1)
0
X1 = (0; 3; 2; 0; 1); 2)
0
X1 = (0; 0; 6; 2; 3);
3)
0
X1 = (0; 8; 0; 6;10); 4)
0
X1 = (2; 0; 3; 0; 6); 5)
0
X1 = (0; 3; 0; 10; 6).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи, найти оптимальный план двойственной задачи.
Z 2x4 x2 max
0, ( 1,5).
2,
- 2,
4 3 12,
1 2 5
1 2 4
1 2 3
x j
x x x
x x x
x x x
j
109
4. На предприятии имеется 4 вида ресурса и оно выпускает 4 вида продукции.
Исходные условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 3 0 3 1 550
В2 1 5 2 6 350
В3 4 1 3 2 600
В4 1 6 2 3 520
Цена 1 единицы
продукции
5 4 3 2
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальна.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальный план исходной задачи ,
*
X Zmax .
в) Записать оптимальный план двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок .
д) Как изменится , целевая функция в оптимальном плане , если цену первого
вида продукции увеличить до 15 ?
Ответы: 1) Zmax 56,9; 2) ) Zmax 550,2; 3) ) Zmax 39,47; 4) ) Zmax 1526,
316; 5) ) Zmax 921,5.
К задаче прилогается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 5 4 3 2
Constraint 1 3 0 3 1 <= 550 0
Constraint 2 1 5 2 6 <= 350 0,5789
Constraint 3 4 1 3 2 <= 650 1,1053
Constraint 4 1 6 2 3 <= 520 0
Solution 152,6316 39,4737 0 0 Zmax =921,0526
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 152,6316 l1 = 0 с1= 5 2,8462 16
x2 39,4737 l2 = 0 с2 = 4 1,25 25,0
x3 0 l3 = 1,4737 с3 = 3 - Infinity 4,4737
x4 0 l4 = 3,6842 с4 = 2 - Infinity 5,6842
110
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0 s1 = 92,1053 b1 = 550 457,8947 Infinity
Constraint 2 y2 = 0,5789 s2 = 0 b2 = 350 162,5 457,8261
Constraint 3 y3 = 1,1053 s3 = 0 b3 = 650 70 766,6667
Constraint 4 у4 = 0 s4 = 130,5263 b4 = 520 389,4737 Infinity
5. Решить транспортную задачу
ai = (100, 120, 80, 200),
bj = (100, 150, 100, 75, 75),
.
1 3 6 5 8
2 2 5 6 9
3 4 8 4 5
7 5 3 2 1
cij
Ответы: 1) Zmin 1840; 2) Zmin 1415; 3) Zmin 1250; 4) Zmin 895; 5)
Zmin 1720.
6. Найти критический путь и его длину, полный резерв времени работы (2-5).
14
20
16
20
10
17
17
9
25
15
10
1
3
7
5
4
2
6
Ответы:
1) 70; 2) 92; 3) 100; 4) 66; 5) 65.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
1 2
2
2
2
Z 4x1 4x 8x 2x
, .
2 6,
2 4,
1,
1 2
1 2
1 2
1 2
x x
x x
x x
x x
Варианты ответов: 1) Zmax = 30; Zmin = 1,875;
2) Zmax = 56; Zmin = 2,5;
3) Zmax = 32; Zmin = 2.
111
Вариант 4
1. Решение системы линейных уравнений называется базисным, если ...
обращаются в ноль.
2. Найти два опорных решения системы .
3 4.
2 - 3,
4 2,
1 3 5
1 3 4
1 2 3
x x x
x x x
x x x
Ответы первого опорного решения:
0
X1 = (0; 5; 3; 6; 0);
0
X1 = (0; 2; 5; 7; 6) 3)
0
X1 = (0; 1; 0; 5; 3); 4)
0
X1 = (0; 2; 0; 3; 4); 5)
0
X1 = (4; 0; 2; 3; 4).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи и найти ее оптимальное решение.
Z 2x1 x2 3x3 x4 max
0, 1,5.
3 4,
7,
2 10,
1
1 3 5
1 3 4
1 2 3
x j
x x x
x x x
x x x
4. Предприятие имеет 4 вида ресурсов и выпускает 4 вида продукции. Исходные
условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 4 20 5 2 560
В2 3 1 3 5 250
В3 0 5 8 3 600
В4 4 2 2 4 520
Цена 1 единицы
продукции
6 7 5 3
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальный план исходной задачи ,
*
X Zmax .
в) Записать оптимальный план двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок .
д) Как изменится целевая функция в оптимальном плане, если цену первого вида
продукции увеличить до 20?
112
Ответы: 1) Zmax 606,6662; 2) Zmax 708,982; 3) Zmax 902,386; 4) Zmax 728,625;
5) Zmax 708,6662.
К задаче прилагается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 6 7 5 3 0
Constraint 1 4 2 5 2 <= 560 2
Constraint 2 3 1 3 5 <= 250 1
Constraint 3 0 5 8 3 <= 600 0
Constraint 4 4 2 2 4 <= 520 1,1538
Solution 43,3333 120 0 0 1 100= Zmax
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 43,3333 l1 = 0 с1= 6 0 21
x2 120 l2 = 0 с2 = 7 2 Infinity
x3 0 l3 = 9 с3 = 5 - Infinity 14
x4 0 l4 = 10 с4 = 3 - Infinity 13
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0 s1 = 146,6667 b1 = 560 413,3333 Infinity
Constraint 2 y2 = 2 s2 = 0 b2 = 250 120,0 330
Constraint 3 y3 = 1 s3 = 0 b3 = 600 0 1250
Constraint 4 у4 = 0 s4 = 106,6667 b4 = 520 143,3333 Infinity
5. Решить транспортную задачу
ai = (270, 230, 200, 250),
bj = (170, 210, 200, 170, 200),
.
8 7 8 5 4
3 4 6 7 5
9 8 10 8 4
4 5 7 4 3
cij
Ответы: 1) Zmin 1925; 2) Zmin 8645; 3) Zmin 9725; 4) Zmin 9675;
5) Zmin 4750.
6. Найти критический путь его длину и определить свободный резерв времени
работы (3-6)
113
15
17
20
10
30
10
28
10
20
25
15
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 82; 2) 95; 3) 79; 4) 84; 5) 100.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
2
2
4)2 ( 4) Z (x1 x
.
5 3 24,
0 3,
2
1 2
1
x
x x
x
Варианты ответов: 1) Zmax = 32; Zmin = 2;
2) Zmax = 34; Zmin = ;
153
32
2
3) Zmax = 30; Zmin = 1,9.
Вариант 5
1. Каждому опорному решению системы уравнений задачи линейного
программирования соответствует … множество допустимых решений системы
ограничений.
2. Найти два опорных решения системы уравнений.
4 2 12.
- 2 2,
3 2,
1 2 5
1 2 4
1 2 3
x x x
x x x
x x x
Ответы первого опорного решения: 1)
0
X1 = (0; 2; 5; 3; 4); 2)
0
X1 =(4; 1; 0; 0; 5); 3)
0
X1 = (0; 0; 2; 2; 12); 4)
0
X1 =(0; 2; 0; 0; 12); 5)
0
X1 = (2; 2; 12; 0; 0).
3. Составить к исходной задаче двойственную. Решить исходную задачу
симплексным методом, найти оптимальное решение двойственной задачи.
Z 2x1 3x2 2x3 x4 max
0, 1,5.
2 5,
2,
2 2 3 6,
1 2 3
1 3 4
1 2 3 4
x j
x x x
x x x
x x x x
j
114
4. Предприятие имеет 4 вида ресурсов и выпускает 4 вида продукции. Исходные
условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 3 0 3 1 400
В2 4 2 5 2 550
В3 0 5 2 6 650
В4 4 1 3 2 520
Цена 1 единицы
продукции
6 5 7 9
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальна.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать решение исходной задачи ,
*
X Zmax .
в) Записать решение двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок (4
свойства).
д) Как изменится, значение целевая функция в оптимальном плане, если
дополнительно приобрести 100 единиц второго ресурса.
Ответы: 1) Zmax 25; 2) Zmax 125; 3) Zmax 100; 4) Zmax 120; 5)
Zmax 45.
К задаче прилагается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 6 5 7 9
Constraint 1 3 0 3 1 <= 400 0
Constraint 2 4 2 5 2 <= 550 0,25
Constraint 3 0 5 2 6 <= 650 1
Constraint 4 4 1 3 2 <= 520 1,25
Solution 67,0833 0 15 103,3333 Zmax 1437,5
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 67,0833 l1 = 0 с1= 6 3,6923 6,8571
x2 0 l2 = 1,75 с2 = 5 - Infinity 6,75
x3 15 l3 = 0 с3 = 7 6,5 9,5
x4 103,3333 l4 = 0 с4 = 9 6,375 10,5
115
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0 s1 = 50,4167 b1 = 400 349,5833 Infinity
Constraint 2 y2 = 0,25 s2 = 0 b2 = 550 520 660
Constraint 3 y3 = 1 s3 = 0 b3 = 650 45 1455
Constraint 4 у4 = 1,25 s4 = 0 b4 = 520 396,1538 550
5. Решить транспортную задачу
ai = (150, 200, 200, 210)
bj = (220, 170, 210, 150, 200)
.
10 7 6 12 11
16 11 8 8 7
13 10 4 10 6
14 8 5 4 6
cij
Ответы: 1) Zmin 4350; 2) Zmin 742; 3) Zmin 1780; 4) Zmin 5620; 5)
Zmin 978.
6. По сетевому графику найти ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работы (2-5).
16
15
12
21
23
18
14
25
30
15
1
3
7
5
4
2
6
Ответы:
1) 65; 2) 78; 3) 56; 4) 85; 5) 56.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
2
2
2 Z (x1 3) (x 2)
2 0,
6,
2 2,
1 2
1 2
1 2
x x
x x
x x
x1 , x2 .
Варианты ответов: 1) Zmax = 30; Zmin = -1;
2) Zmax = 25; Zmin = 0;
3) Zmax = 28; Zmin = 1.
116
Вариант 6
1. Путь ... связывающий начальное и завершающее события называется ...
2. Найти два опорных решения системы
4 2.
3 - 2 4,
2 3 6,
1 2 3
1 3 5
1 3 4
x x x
x x x
x x x
Ответы первого опорного решения:
0
X1 =(6; 0; 4; 2; 0);
0
X1 =(0; 1; 0; 6; 2) 3)
0
X1 =(7; 4; 2; 0; 0); 4)
0
X1 = (0; 2; 4; 6; 0); 5)
0
X1 = (0; 2; 0; 6; 4).
3. Решить исходную задачу симплексным методом, составить к ней
двойственную, найти оптимальное решение двойственной задачи.
Z 2x1 4x2 max
0, 0.
2,
- 2 3 6,
2 8,
1 2
1 2
1 2
1 2
x x
x x
x x
x x
4. Предприятие имеют 4 вида ресурсов и выпускает 4 вида продукции. Все
данные задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 3 4 2 5 400
В2 4 2 5 2 800
В3 0 3 6 2 300
В4 3 1 0 4 500
Цена 1 единицы
продукции
4 3 9 2
Найти оптимальный план при котором выручка будет оптимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальный план исходной задачи ,
*
X Zmax .
в) Записать оптимальный план двойственной ,
*
Y Wmin.
г) Провести анализ решения задачи с помощью свойств двойственных оценок (4
свойства).
д) Как изменится , целевая функция в оптимальном плане , если цену первого
вида продукции увеличить до 12 ?
Варианты ответов: 1) Zmax 56,9; 2) Zmax 1000; 3) Zmax 800; 4)
Zmax 2100, 5) Zmax 920.
К задаче прилагается распечатка решения на ЭВМ.
117
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 4 3 9 2
Constraint 1 3 4 2 5 <= 400 1,3333
Constraint 2 4 2 5 2 <= 800 0
Constraint 3 0 3 6 2 <= 300 1,0556
Constraint 4 3 1 0 4 <= 500 0
Solution 100 0 50 0 Zmax 850
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 100 l1 = 0 с1= 4 0 13,5
x2 0 l2 = 5,5 с2 = 3 - Infinity 8,5
x3 50 l3 = 0 с3 = 9 2,6667 Infinity
x4 0 l4 = 6,7778 с4 = 2 - Infinity 8,7778
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 1,3333 s1 = 0 b1 = 400 100 512,5
Constraint 2 y2 = 0 s2 = 150 b2 = 800 650 Infinity
Constraint 3 y3 = 1,0556 s3 = 0 b3 = 300 0 685,7142
Constraint 4 у4 = 0 s4 = 200 b4 = 500 300 Infinity
5. Решить транспортную задачу
ai = (270, 350, 200, 230)
bj = (190, 210, 200, 230, 220)
.
8 4 6 7 6
6 5 10 9 3
12 7 3 4 5
10 9 5 5 4
cij
Ответы: 1) Zmin 12170; 2) Zmin 4470; 3) Zmin 7125; 4) Zmin 3520; 5)
Zmin 8746.
6. По сетевому графику найти ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работ.
118
10
20
18
19
21
16
21
12
9
20
15
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 70; 2) 87; 3) 64; 4) 60; 5) 65.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом
Z 3x1 x2
, .
6,
2,
1 2
2
2
2
1
1 2
x x
x x
x x
Варианты ответов: 1) Zmax = 2 10; Zmin = - 2 10;
2) Zmax = 4 10; Zmin = 2 6;
3) Zmax = 4 10; Zmin = 0.
Вариант 7
1. Если в оптимальном плане М-задачи все искусственные переменные ..., то
...решение будет оптимальным и в исходной задаче.
2. Найти два опорных решения системы
- 2.
2 - 5,
2 3,
1 2 5
1 2 4
1 2 3
x x x
x x x
x x x
Ответы первого опорного решения:1)
0
X1 = (0; 3; 5; 2; 0);
0
X1 = (2; 1; 1; 0; 5) 3)
0
X1 = (0; 2; 0; 3; 5); 4)
0
X1 = (0; 0; 3; 5; 2); 5)
0
X1 = (2; 3; 5; 0; 0).
3. Решить исходную задачу симплексным методом, составить к ней
двойственную,
найти оптимальное решение двойственной задачи.
Z 2x1 3x2 5x3 max
0, ( 0,5).
2 2 3 6,
2 3 5,
3,
1 2 3
1 2 3
1 2 3
x j
x x x
x x x
x x x
j
119
4. Предприятие имеют 4 вида ресурсов и производит 4 вида продукции. Все
данные задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 4 5 2 3 240
В2 3 2 5 4 250
В3 2 0 5 1 190
В4 2 6 1 3 300
Цена 1 единицы
продукции
9 12 5 8
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальный план исходной задачи ,
*
X Zmax
в) Записать оптимальный план двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок (4
свойства)
д) Как изменится , целевая функция в оптимальном плане , если дополнительно
приобрести 50 единиц второго ресурса.
Ответы: 1) Zmax 20,128; 2) Zmax 14,285; 3) Zmax 22,142; 4)
Zmax 13,178; Zmax 25,642.
К задаче прилогается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 9 12 5 8
Constraint 1 4 5 2 3 <= 240 2,2857
Constraint 2 3 2 3 4 <= 250 0,2857
Constraint 3 2 0 5 1 <= 190 0
Constraint 4 2 6 1 3 <= 300 0
Solution 0 15 0 55 Zmax 620
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 0 l1 = 1 с1= 9 - Infinity 10
x2 15 l2 = 0 с2 = 12 10 13,3333
x3 0 l3 = 0,4286 с3 = 5 - Infinity 5,4286
x4 55 l4 = 0 с4 = 8 7,4545 24
120
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 2,2857 s1 = 0 b1 = 240 187,5 275
Constraint 2 y2 = 0,2857 s2 = 0 b2 = 250 96 320
Constraint 3 y3 = 0 s3 = 135 b3 = 190 55 Infinity
Constraint 4 у4 = 0 s4 = 45 b4 = 300 255 Infinity
5. Решить транспортную задачу
ai = (300, 250, 150, 150)
bj = (145, 195, 180, 140, 190)
.
4 6 5 4 6
9 3 7 6 5
7 7 3 9 6
9 4 8 7 4
cij
Ответы: 1) Zmin 712; 2) Zmin 1260; 3) Zmin 3840; 4) Zmin 2120; 5)
Zmin 3475.
6. По сетевому графику найти ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работ.
9
10
18
19
11
16
21
12
20
20
15
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 70; 2) 85; 3) 90; 4) 105; 5) 60.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом
2
2
2
Z 2 x1 x
, .
1,
4 ,
1 2
1 2
2
2 1
x x
x x
x x
Варианты ответов: 1) Zmax = 1; Zmin = -8;
2) Zmax = 1,5; Zmin = -14;
3) Zmax = 3; Zmin = -15.
121
Вариант 8
1. Если исходная задача имеет ..., то и двойственная ей задача имеет …
2. Найти два опорных решения системы уравнений.
- 4 3 8 10.
- 2 4 2,
3 2x 7,
2 3 5 6
2 3 4
1 2 3 5
x x x x
x x x
x x x
Ответы первого опорного решения:
0
X1 = (0; 0; 7; 2; 10; 9);
0
X1 = (7; 0; 0; 2; 0;
10); 3)
0
X1 = (7; 2; 10; 0; 0; 0); 4)
0
X1 = (0; 2; 7; 10; 0; 0); 5)
0
X1 = (3; 2; 7; 0; 0; 0).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи, найти оптимальный план двойственной задачи.
Z 2x1 x2 x3 max
0, ( 1,5).
3 2,
4,
2 3 6,
1 3 5
2 3
1 3 4
xj j
x x x
x x
x x x
4. Предприятие имеет 4 вида ресурса и выпускает 4 вида продукции. Исходные
условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 1 6 0 2 250
В2 3 2 3 4 300
В3 1 0 5 1 240
В4 4 5 2 3 350
Цена 1 единицы
продукции
3 5 7 3
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет оптимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать решение исходной задачи ,
*
X Zmax
в) Записать решение двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок (4
свойства).
д) Как изменится , целевая функция в оптимальном плане , если продать 100
единиц третьего ресурса.
Ответы: 1) уменьшится на 128,92.
2) уменьшится на 27,71.
3) уменьшится на 60,24.
122
4) увеличится на 128,92.
5) увеличится на 100.
К задаче прилагается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 3 5 7 3
Constraint 1 1 6 0 2 <= 250 0,6024
Constraint 2 3 2 3 4 <= 300 0
Constraint 3 1 0 5 1 <= 240 1,2892
Constraint 4 4 5 2 3 <= 350 0,2771
Solution 16,506 38,9157 44,6988 0 Zmax 556,988
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 16,506 l1 = 0 с1= 3 2,2333 5
x2 38,9157 l2 = 0 с2 = 5 3,8261 9,6
x3 44,6988 l3 = 0 с3 = 7 4,5455 10,8333
x4 0 l4 = 0,3253 с4 = 3 - Infinity 3,3253
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0,6024 s1 = 0 b1 = 250 116,6667 304,8
Constraint 2 y2 = 0 s2 = 38,5542 b2 = 300 261,4458 Infinity
Constraint 3 y3 = 1,2892 s3 = 0 b3 = 240 44,7368 354,1667
Constraint 4 у4 = 0,2771 s4 = 0 b4 = 350 304,3333 401,6129
5. Решить транспортную задачу
ai = (210, 200, 200, 290)
bj = (210, 150, 170, 200, 200)
.
7 6 7 10 5
12 14 8 12 7
5 10 8 9 6
9 11 12 10 8
cij
Ответы: 1) Zmin 3140; 2) Zmin 4820; 3) Zmin 4930; 4) Zmin 7420;
5) Zmin 6200.
6. По сетевому графику вычислить ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работ.
123
12
19
20
17
21
14
29
15
25
27
20
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 80; 2) 95; 3) 100; 4) 87; 5) 98.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
2
2
2
Z (x1 3) (x 2)
, .
3 ,
4 16,
1 2
1 2
1 2
x x
x x
x x
Варианты ответов: 1) Zmax = 13; Zmin = 0;
2) Zmax = 8; Zmin = 2;
3) Zmax = 8; Zmin = -1.
Вариант 9
1. Если в оптимальном плане ресурс используется ... и оценка единицы этого
ресурса…, то такой ресурс называют дефицитным.
2. Найти два опорных решения системы .
2 - 2 3.
3 1,
3 2,
1 2 5
1 4 5
1 2 5
x x x
x x x
x x x
Ответы первого опорного решения: 1)
0
X1 = (0; 2; 1; 3; 0);
0
X1 = (2; 1; 3; 0; 0) 3)
0
X1 = (2; 1; 0; 0; 3); 4)
0
X1 = (1; 3; 2; 0; 0); 5)
0
X1 = (1; 0; 0; 3; 2).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи, найти оптимальный план двойственной задачи.
Z x1 x2 x3 max
0, ( 1,6).
2 6,
2 3 4,
2 6,
3 5 6
2 4 5 6
1 4 6
x j
x x x
x x x x
x x x
j
124
4. Предприятие имеет 4 вида ресурса и выпускает 4 вида продукции. Исходные
условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 5 3 2 4 800
В2 2 4 6 5 720
В3 5 2 0 1 650
В4 3 4 1 2 700
Цена 1 единицы
продукции
9 4 6 3
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать решение исходной задачи ,
*
X Zmax .
в) Записать решение двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок .
д) Как изменится , целевая функция в оптимальном плане , если продать 300
единиц первого ресурса.
Ответы: 1) уменьшится на 235,67.
2) уменьшится на 484,62.
3) увеличится на 200,29.
4) увеличится на 38,46.
5) уменьшится на 300.
К задаче прилагается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 9 4 6 3
Constraint 1 5 3 2 4 <= 800 1,6154
Constraint 2 2 4 6 5 <= 720 0,4615
Constraint 3 5 2 0 1 <= 650 0
Constraint 4 3 4 1 2 <= 700 0
Solution 129,2308 0 76,9231 0 Zmax 1 624,615
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 129,2308 l1 = 0 с1= 9 2 15
x2 0 l2 = 2,6923 с2 = 4 - Infinity 6,6923
x3 76,9231 l3 = 0 с3 = 6 3,6 27,0
x4 0 l4 = 5,7692 с4 = 3 - Infinity 8,7692
125
Constraint Dual
Value
Slack/ Surplus Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 1,6154 s1 = 0 b1 = 800 240 803,3333
Constraint 2 y2 = 0,4615 s2 = 0 b2 = 720 710 2400
Constraint 3 y3 = 0 s3 = 3,8461 b3 = 650 646,1539 Infinity
Constraint 4 у4 = 0 s4 = 235,3846 b4 = 700 464,6154 Infinity
5. Решить транспортную задачу
ai = (100, 120, 80, 120)
bj = (60, 100, 95, 125, 40)
.
2 3 1 9 6
5 4 7 3 9
3 6 2 1 6
4 5 3 4 7
cij
Ответы: 1) Zmin 1125; 2) Zmin 2120; 3) Zmin 1720; 4) Zmin 2120; 5)
Zmin 175.
6. По сетевому графику вычислить ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работы (2-5).
10
8
14
17
16
19
25
11
15
21
12
1
3
7
5
4
2
6
Ответы длины критического пути:
1) 75; 2) 57; 3) 60; 4) 70; 5) 66.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
2 1 10 2 26
2
2
2
Z x1 x x x
, .
5 2 20,
2 4,
1 2
1 2
1 2
x x
x x
x x
Варианты ответов: 1) Zmax = 26; Zmin =
9
5
5 ;
2) Zmax = 30; Zmin = 4;
3) Zmax = 34; Zmin = 5.
126
Вариант 10
1. Оценка единицы i-го ресурса (yi) показывает, на сколько изменится целевая
функция в оптимальном плане , если ... изменится на ...
2. Найти два опорных решения системы .
- 3 2.
- 4,
2 1,
2 3 4
2 4 5
1 2
x x x
x x x
x x
Ответы первого опорного решения: 1)
0
X1 = (0; 1; 5; 4; 2); 2)
0
X1 = (1; 0; 2; 0; 4);
3)
0
X1 = (2; 3; 1; 0;0); 4)
0
X1 = (0; 0; 1; 4; 2); 5)
0
X1 = (1; 0; 0; 4; 2).
3. Решить исходную задачу симплексным методом, составить к ней модель
двойственной задачи, найти оптимальный план двойственной задачи.
Z 4x1 12x2 max
0, 0.
1,
- 0,
2 2,
1 2
1 2
1 2
1 2
x x
x x
x x
x x
4. Предприятие имеет 4 вида ресурса и выпускает 4 вида продукции. Исходные
условия задачи заданы в таблице.
Таблица данных
Вид
ресурса
Затраты ресурсов на 1 единицу продукции Запас
1 2 3 4 ресурса
В1 5 3 0 2 550
В2 3 3 1 2 500
В3 3 4 2 1 650
В4 2 3 5 6 750
Цена 1 единицы
продукции
4 4 5 8
Найти оптимальный план выпуска продукции при котором прибыль от
реализации продукции будет максимальной.
Требуется:
а) Составить математическую модель исходной и двойственной задач.
б) Записать оптимальное решение исходной задачи ,
*
X Zmax .
в) Записать оптимальное решение двойственной ,
*
Y Wmin.
г) Проанализировать решение задачи с помощью свойств двойственных оценок .
д) Как изменится , целевая функция в оптимальном плане, если дополнительно
приобрести 500 единиц четвертого ресурса. Если считать что увеличение целевой
функции.
Ответы: 1) Zmax 550; 2)
max Z 800; 3) Zmax 900; 4) Zmax 625;
Zmax 700.
127
К задаче прилогается распечатка решения на ЭВМ.
Распечатка к задаче № 4.
Module/submodule: Linear Programming
Problem title: ( untitled)
Objective: Maximize
Results -----------------
x1 x2 x3 х4 RHS Dual
Maximize 4 4 5 8
Constraint 1 5 3 0 2 <= 550 0,4769
Constraint 2 3 3 1 2 <= 500 0
Constraint 3 3 4 2 1 <= 650 0,5692
Constraint 4 2 3 5 6 <= 750 1,1538
Solution 46,875 0 0 109,375 Zmax 1 062,5
Ranging ---------------
Variable Value Reduced
Cost
Original
Value
Lower
Bound
Upper
Bound
x1 46,875 l1 = 0 с1= 4 2,6667 16
x2 0 l2 = 0,5 с2 = 4 - Infinity 4,5
x3 0 l3 = 1,5 с3 = 5 - Infinity 6,5
x4 109,375 l4 = 0 с4 = 8 6,6667 12
Constraint Dual
Value
Slack/
Surplus
Original
Value
Lower
Bound
Upper
Bound
Constraint 1 y1 = 0 s1 = 96,875 b1 = 5500 453,125 Infinity
Constraint 2 y2 = 0,25 s2 = 0 b2 = 500 250 619,2308
Constraint 3 y3 = 0 s3 = 400 b3 = 650 250 Infinity
Constraint 4 у4 = 1,25 s4 = 0 b4 = 750 166,6667 1500
5. Решить транспортную задачу
ai = (150, 100, 150, 100)
bj = (100, 70, 130, 110, 90)
.
5 6 8 7 2
2 6 4 5 4
8 3 4 2 5
3 9 5 4 3
cij
Ответы: 1) Zmin 1800; 2) Zmin 1670; 3) Zmin 7920; 4) Zmin 6120;
5) Zmax 2450.
6. По сетевому графику вычислить ранний и поздний сроки свершения событий,
определить критический путь и его длину, найти свободный и полный резерв времени
работы (2-5).
128
10
9
18
17
14
12
20
14
21
19
15
1
3
7
5
4
2
6
Ответы длины критического пути: 1) 60; 2) 75; 3) 64; 4) 58; 5) 57.
7. В области решений системы неравенств определить глобальные экстремумы
функций. Решить задачу графическим способом.
( 3)2 ( 4)2 1 2 Z x x
, .
2 0,
2 5 20,
1 2
1 2
1 2
x x
x x
x x
Варианты ответов: 1) Zmax = 25; Zmin = ;
841
203
1
2) Zmax = 20; Zmin = ;
16
13
2
3) Zmax = 26; Zmin = .
81
19
1
