close

Вход

Забыли?

вход по аккаунту

?

1498.Исследование операций

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки РФ
Государственное образовательное учреждение
высшего профессионального образования
“Шуйский государственный педагогический университет”
Кафедра информационных систем и технологий
ИССЛЕДОВАНИЕ ОПЕРАЦИЙ. ПРАКТИКУМ
Шуя 2010
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 519.8
ББК 22.18
И 88
Печатается по решению редакционно-издательского
совета Государственное образовательное учреждение
высшего профессионального образования «Шуйский
государственный педагогический университет»
Автор-составитель: к.п.н Завьялова О.А.
Рецензенты:
к.п.н., доцент Замогильнова Л.В., доцент кафедры математики и
методики
обучения
Шуйского
государственного
педагогического университета
Грушанская Е.А., директор ОГУ Ивановский «Учебнометодический центр информатизации и оценки качества
образования»
И 88 Исследование операций. Практикум. / Автор-сост. Завьялова О.А. – Шуя:
Издательство ГОУ ВПО «ШГПУ», 2010.
В практикуме представлены необходимые теоретические сведения,
определения, примеры решения основных типов задач, а также задания для
самостоятельного решения по таким разделам исследования операций как:
линейное, нелинейное и динамическое программирование, элементы теории
игр. Постановки задач предусматривают графическое решение задач,
использование специальных методов решения, решение с помощью
электронных таблиц Excel.
Практикум предназначен для студентов, обучающихся по специальности
«Информатика»
© ГОУ ВПО «ШГПУ», 2010
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СОДЕРЖАНИЕ
Тема 1. Линейное программирование ............................................. 4
Практическая работа № 1. Постановка задачи линейного
программирования и ее графическое решение на плоскости ................ 4
Практическая работа № 2. Опорные и оптимальные планы ЗЛП ....... 22
Практическая работа № 3. Симплекс-метод решения задач линейного
программирования ................................................................................... 25
Практическая работа № 4. Двойственная задачи линейного
программирования ................................................................................... 28
Практическая работа № 5. Решение транспортной задачи линейного
программирования ................................................................................... 31
Тема 2. Нелинейное программирование ....................................... 40
Практическая работа № 6. Решение задачи нелинейного
программирования графическим методом ............................................ 40
Практическая работа № 7. Метод множителей Лагранжа решения
ЗНП. ........................................................................................................... 43
Тема 3. Элементы теории матричных игр ................................ 46
Практическая работа № 8. Матричные игры и их решение. ................ 46
Тема 4. Динамическое программирование ................................... 50
Практическая работа № 9. Решение задач динамического
программирования. .................................................................................. 50
Используемая литература............................................................. 54
Приложение 1 .................................................................................. 55
Приложение 2 .................................................................................. 58
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕМА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Практическая работа № 1. Постановка задачи линейного
программирования и ее графическое решение на плоскости
1.1. Постановка задачи линейного программирования
Необходимые теоретические сведения
Общая постановка задачи линейного программирования с экономической
точки зрения:
Необходимо составить программу получения наибольшей прибыли от
предприятия
F=c1x1+c2x2+…+ cnxn  max
Xj – количество продукции j-го вида, j=1,…,n
Cj – прибыль от реализации единицы j-го вида продукции, j=1,…,n
a11x1+a12x2+…+a1nxnb1
a21x1+a22x2+…+a2nxnb2
…
am1x1+am2x2+…+amnxn bm
xj≥0, j=1,…,n
aij – расход i-го вида ресурса на производство единицы j-го вида продукции
bi – количество i-го вида ресурса, i=1,…,m
Каноническая постановка задачи линейного программирования (ЗЛП):
F=c1x1+c2x2+…+ cnxn  min
(1)
a11x1+a12x2+…+a1nxn=b1
a21x1+a22x2+…+a2nxn=b2
(2)
…
am1x1+am2x2+…+amnxn=bm
xj≥0, j=1,…,n
(3)
Задача заключается в том, чтобы найти такие x1,x2,…,xn, которые
удовлетворяют ограничениям (2)-(3) и доставляют целевой функции (1)
минимальное значение.
Векторная форма записи ЗЛП:
Матричная форма записи ЗЛП:
F=(c,x)  min,
A1x1+A2x2+…+Anxn=A0,
x≥ 0
F=(c,x)  min,
Ax=A0,
x≥ 0
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Опр. 1. Планом, или допустимым значением ЗЛП называется вектор
x(x1,x2,…,xn), удовлетворяющий условиям (2)-(3).
Опр. 2. План называется невырожденным, если он содержит m
положительных компонент. Если, план содержит меньше, чем m
положительных компонент, он называется вырожденным.
Опр. 3. План называется оптимальным, если он доставляет экстремальное
значение целевой функции.
Примеры решения задач
Пример 1. Задача использования сырья (задача планирования
производства)
Для изготовления двух видов продукции P1 и P2 используют три вида
сырья:S1, S2 и S3. Запасы сырья, количество единиц сырья, затрачиваемых на
изготовление единицы продукции, а также величина прибыли, получаемая от
реализации единицы продукции, приведены в таблице 1. Необходимо
составить такой план выпуска продукции, чтобы при ее реализации получить
максимальную прибыль.
Таблица1
Количество единиц сырья,
затрачиваемых на изготовление
Виды сырья
Запасы сырья
единицы продукции
S1
S2
S3
b1
b2
b3
Прибыль от единицы продукции
(в руб.)
P1
P2
a11
a21
a31
a12
a22
a32
C1
C2
Составим экономико-математическую модель (математическое описание
исследуемого экономического процесса) задачи.
Обозначим через x1, x2 количество единиц продукции соответственно P1, P2,
запланированных к производству. Тогда учитывая количество единиц сырья,
затрачиваемых на изготовление единицы продукции, а также запасы сырья,
получим систему ограничений
(4)
По смыслу задачи переменные x1≥ 0, x2≥ 0 (5)
Суммарная прибыль F(x) составит c1x1 руб. от реализации продукции P1 и
c2x2 руб. – от реализации продукции P2, т.е.
F(x)= c1x1 + c2x2
(6)
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Итак, экономико-математическая модель задачи: найти такой план выпуска
продукции X=(x1,x2), удовлетворяющий системе (4) и условию (5), при котором
функция (6) принимает максимальное значение.
Задачу легко обобщить на случай выпуска n видов продукции с
использованием m видов сырья.
Пример 2. Задача составления рациона (задача о диете).
Имеется два вида корма I и II, содержащие питательные вещества (витамины)
S1, S2 и S3 Содержание количества единиц питательного вещества в 1 кг
каждого вида корма и стоимость 1 кг корма приведены в таблице 2.
Таблица 2
Необходимый
Количество единиц питательного
Питательные
минимум
вещества в 1 кг корма
вещества
питательных
Корм I
Корм II
веществ
S1
S2
S3
b1
b2
b3
a11
a21
a31
a12
a22
a32
Стоимость 1 кг корма (в руб.)
Необходимо составить дневной рацион, в котором содержание каждого
вида питательных веществ было бы не менее установленного минимума,
причем затраты на него должны быть минимальными.
Составим экономико-математическую модель задачи.
Обозначим через x1, x2 соответственно количество кормов I и II,
входящих в дневной рацион. Принимая во внимание значения, приведенные в
табл. 10.2, и условие, что дневной рацион удовлетворяет требуемой
питательности только в случае, если количество единиц питательных веществ
не меньше предусмотренного, получим систему ограничений
(7)
По смыслу задачи переменные x1≥ 0, x2≥ 0 (8)
Общая стоимость рациона (в руб.) составит
F(x) = c1x1 + c2x2 (9)
Итак, экономико-математическая модель задачи: составить дневной
рацион X=(x1,x2),, удовлетворяющий системе (7) и условию (8), при котором
функция (9) принимает минимальное значение.
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи для самостоятельного решения
Для задач 1.1-1.3 составить математическую модель.
1.1. Для изготовления трех видов изделий А,В и С используется токарное,
фрезерное, сварочное и шлифовальное оборудование. Затраты времени на
обработку одного изделия для каждого из типов оборудования, общий фонд
рабочего времени каждого из типов используемого оборудования, прибыль от
реализации одного изделия каждого вида даны в таблице.
Тип оборудования
Затраты времени (станко-ч) на
Общий фонд
обработку 1 изделия вида
рабочего времени
оборудования (час)
А
В
С
Фрезерное
2
4
5
120
Токарное
1
8
6
280
Сварочное
7
4
5
240
Шлифовальное
4
6
7
360
Прибыль (руб)
100
140
120
Требуется определить, сколько изделий и какого вида следует изготовить
предприятию, чтобы прибыль от их реализации была максимальной.
1.2. Кондитерская фабрика для производства трех видов карамели А, В и С
использует 3 вида основного сырья: сахарный песок, патоку и фруктовое пюре.
Нормы расхода сырья каждого вида на производство 1 т карамели данного
вида, общее количество сырья каждого вида, которое может быть использовано
фабрикой, а также прибыль от реализации 1 т карамели данного вида
приведены в таблице
Вид сырья
Нормы расхода сырья (т) на 1 т
карамели
А
В
С
0,8
0,5
0,6
0,4
0,4
0,3
0,1
0,1
1000
1500
2000
Общее
количество
сырья (т)
800
600
120
Сах. песок
Патока
Фруктовое пюре
Прибыль
от
реализации
1
т
продукции (в руб)
Найти план производства карамели, обеспечивающий максимальную прибыль
от ее реализации.
1.3. Продукцией городского молочного завода являются молоко, кефир и
сметана, расфасованные в бутылки. На производство 1 т молока, кефира и
сметаны требуется соответственно 1010, 1010 и 9450 кг молока. При этом
затраты рабочего времени при разливе 1 т молока и кефира составляют 0,18 и
0,19 машино-часов. На расфасовке 1 т сметаны заняты специальные автоматы в
течение 3,25 часов. Всего для производства цельномолочной продукции завод
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
может использовать 136 000 кг молока. Основное оборудование может быть
занято в течение 21,4 машино-часов, а автоматы по расфасовке сметаны – в
течение 16,25 часов. Прибыль от реализации 1 т молока, кефира и сметаны
соответственно равна 30,22 и 136 руб. Завод должен ежедневно производить не
менее 100 т молока, расфасованного в бутылки. На производство другой
продукции не имеется никаких ограничений.
Требуется определить, какую продукцию и в каком количестве следует
изготовлять ежедневно, чтобы прибыль от ее реализации была максимальной.
1.2. Графическое решение задачи линейного программирования
Необходимые теоретические сведения
Теоремы о планах ЗЛП
Теорема 1. Множество всех планов ЗЛП (1)-(3) выпукло.
Теорема 2. Целевая функция ЗЛП достигает своего экстремального значения в
угловой точке, если множество допустимых планов ограничено. Если
экстремальное значение достигается более, чем в одной угловой точке, то оно
достигается в любой точке, являющейся выпуклой линейной комбинацией
этих точек.
Графический метод решения ЗЛП
Графический метод основан на геометрической интерпретации задачи
линейного программирования и применяется в основном при решении задач
двумерного пространства и только некоторых задач трёхмерного пространства,
так как довольно трудно построить многогранник решений, который
образуется в результате пересечения полупространств. Задачу пространства
размерности больше трёх изобразить графически вообще невозможно.
Пусть задача линейного программирования задана в двумерном
пространстве, то есть ограничения содержат две переменные. Найти
экстремальное значение функции
F = с1*х1+с2*х2 max (min)
(10)
при
a11x1+a12x2 b1
a21x1+a22x2 b2
(11)
…
am1x1+am2x2 bm
xj ≥ 0, j=1,…,n
(12)
Допустим, что система (11) при условии (12) совместна и её многоугольник
решений ограничен. Каждое из неравенств (11) и (12), как отмечалось выше,
определяет полуплоскость с граничными прямыми:
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ai1x1 + ai2x2= bi, (i = 1, 2, …, m), х1=0, х2=0.
Линейная функция (10) при фиксированных значениях Z является
уравнением прямой линии:
c1х1 + c2х2 = const.
Построим многоугольник решений системы ограничений (11) и график
линейной функции (10) при F= 0. Тогда поставленной задаче линейного
программирования можно дать следующую интерпретацию. Найти точку
многоугольника решений, в которой прямая c1х1 + c2х2 = const опорная и
функция F при этом достигает минимума.
Значения F = c1х1 + c2х2 возрастают в направлении вектора N(c1, c2),
поэтому прямую F=0 передвигаем параллельно самой себе в направлении
вектора N (в противоположном направлении) до тех пор, пока прямая не
станет опорной. Пусть это точка А. Координаты точки А (х1, х2) находим,
решая систему уравнений прямых на пересечении которых она находится.
Если многоугольник решений представляет собой неограниченную
многоугольную область, то возможны два случая.
Случай 1. Прямая c1х1 + c2х2 = const, передвигаясь в направлении
вектора N или противоположно ему, постоянно пересекает многоугольник
решений и ни в какой точке не является опорной к нему. В этом случае
линейная функция не ограничена на многоугольнике решений как сверху, так и
снизу.
Случай 2. Прямая, передвигаясь, всё же становится опорной
относительно многоугольника решений. Тогда в зависимости от вида области
линейная функция может быть ограниченной сверху и неограниченной снизу,
ограниченной снизу и неограниченной сверху, либо ограниченной как снизу,
так и сверху.
Алгоритм решения задачи линейного программирования
графическим способом
Постановка задачи: Построить математическую модель задачи
линейного программирования (ЗЛП) и графическим способом найти
оптимальное значение целевой функции.
Указания к решению
1. Записать целевую функцию F(x1,x2)=c1x1+c2x2 и ограничения на
неизвестные в виде системы неравенств aj1x1+aj2x2  bj (j=1,…,m)
2. Найти полуплоскости, определяемые каждым из ограничений и определить
на плоскости x10x2 допустимое множество решений (планов) ЗЛП
3. Построить линию уровня целевой функции c1x1+c2x2=0.
4. Построить вектор-градиент с координатами (c1,c2).
5. Перемещая прямую c1x1+c2x2=0 в направлении вектора (c1,c2). (если задача
на максимум) или в направлении вектора (-c1,-c2). (если задача на минимум),
найти точки, в которых прямая c1x1+c2x2=0= const является опорной для
допустимого множества решений или же установить неограниченность целевой
функции сверху (снизу) на множестве планов
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. Найти оптимальный план (или множество оптимальных планов) для
данной задачи
7. Определить экстремальное значение целевой функции в найденной точке.
Примеры решения задачи
Пример3. ( Задача распределения ресурсов)
Для производства двух видов изделий А и В предприятие использует три вида
сырья. Нормы расхода сырья каждого вида на изготовление единицы
продукции каждого вида приведены в таблице. В ней же указаны прибыль от
реализации одного изделия каждого вида и общее количество сырья, которое
может быть использовано предприятием
Вид сырья
Нормы расхода сырья(кг)
Общее
на одно изделие
количество
сырья (кг)
Вида А
Вида В
1
12
4
300
2
4
4
120
3
3
12
252
Прибыль от
30
40
реализации одного
изделия (руб.)
Требуется составить такой план выпуска продукции, при котором прибыль
предприятия от реализации всех изделий является максимальной.
Решение.
1.
Составим математическую модель.
Предположим, что предприятие изготовит х1 изделий вида А и х2 изделий вида
В. Тогда общая прибыль от реализации изделий составит F(x1,x2)=30x1+40x2.
Так как производство продукции ограничено имеющимися в
распоряжении предприятия сырьем каждого вида, и количество изготовляемых
изделий не может быть отрицательным, должны выполняться неравенства:
12 x1  4 x 2  300,
4 x  4 x  120,
 1
2

3x1  12 x 2  252,
 x1 , x 2  0.
Таким образом, среди всех неотрицательных решений данной системы
линейных неравенств требуется найти такое, при котором целевая функция F
принимает максимальное значение.
2.
Определим множество допустимых решений задачи.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для этого в системе ограничений заменим знаки неравенств на знаки точных
равенств и построим на плоскости x10x2 соответствующие прямые. Каждая из
построенных прямых делит плоскость на две полуплоскости, для определения
искомой полуплоскости возьмем какую-либо точку, принадлежащую одной из
двух полуплоскостей, и проверим, удовлетворяют ли ее координаты данному
неравенству. В искомой полуплоскости поставим стрелочку. Пересечение
полуплоскостей определяет многоугольник решений задачи – ОАВСD (рис.1).
3.
Строим вектор-градиент N(30,40)
4.
Строим линию уровня целевой функции 30x1+40x2=с, где с – некоторая
постоянная величина, например, 480. Перемещая линию уровня 30x1+40x2=480
в направлении вектора – градиента, видим, что последней общей точкой ее с
многоугольником решений задачи будет точка В (линия уровня является
опорной к многоугольнику решений) .
5.
Найдем координаты точки В, решая систему уравнений
4 x1  4 x2  120,
 x1  12, x2  18.

3x1  12 x2  252.
6.
Найдем максимальное значение целевой функции
Fmax=30*12+40*18=1080 (руб.)
Ответ: Если предприятие изготовит 12 изделий вида А и 18 изделий вида В, то
оно получит максимальную прибыль, равную 1080 руб.
Рис.1
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи для самостоятельного решения
Задачи распределения ресурсов
1.4. Со станции А и В нужно развести грузы на склады №1, №2, №3. На
станции А можно погрузить груз на 80 машин, на станции В – на 100 машин.
На склад №1 должно попасть 50 машин, на склад №2 – 70 машин, на склад №3
– 80 машин. Затраты бензина отражены в таблице:
Станции/Склады №1 №2 №3
А
2
4
5
В
4
5
3
Составить план перевозок, чтобы общий расход бензина был минимальным.
1.5. Фирма по переработке картофеля производит три вида продукции: дольки,
кубики и хлопья. Анализ экономической ситуации показывает возможность
сбыть на рынке 1,8 т долек, 1,2 т кубиков, 2,4 т хлопьев. Необходимый
картофель фирма закупает у двух поставщиков.
Выход готовой продукции из 1 т
картофеля
Вид готовой продукции
Поставщик 1
Поставщик 2
Дольки
0.2
0.3
Кубики
0.2
0.1
Хлопья
0.3
0.3
Прибыль от реализации 1 т
5.0
6.0
продукции
Требуется определить, какое количество картофеля надо приобрести у каждого
поставщика, чтобы обеспечить максимальную прибыль.
1.6. На изготовление продукции П1 и П2 используется 4 вида сырья S1, S2, S3,
S4.Запасы каждого вида сырья ограничены. Количество единиц сырья,
необходимых для изготовления единицы каждого из видов продукции и доход
от продажи единицы изделия (в у.е.) даны в таблице
Виды
Запасы
Виды продукции
сырья
сырья
П1
П2
S1
19
2
3
S2
13
2
1
S3
15
0
3
S4
18
3
0
Доход
7
5
Требуется составить такой план выпуска продукции видов П1 и П2, при
котором доход от реализации изделий будет максимальным.
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.7. На изготовление продукции П1 и П2 используется 4 вида сырья S1, S2, S3,
S4.Запасы каждого вида сырья ограничены. Количество единиц сырья,
необходимых для изготовления единицы каждого из видов продукции и доход
от продажи единицы изделия (в у.е.) даны в таблице
Виды
Запасы
Виды продукции
сырья
сырья
П1
П2
S1
30
4
1
S2
16
6
2
S3
14
2
4
S4
28
5
2
Доход
4
6
Требуется составить такой план выпуска продукции видов П1 и П2, при
котором доход от реализации изделий будет максимальным.
1.8. Мебельное предприятие выпускает столы и тумбочки. Для их изготовления
используется два вида древесины. Расход древесины каждого вида на каждое
изделие (в куб. м), запас сырья и прибыль от продажи изделия каждого вида
даны в таблице
Изделие
Расход древесины
Прибыль от продажи
одного изделия (в
первого вида
второго
руб)
вида
стол
0,18
0,08
50
тумбочка
0,09
0,28
17
Запас сырья (куб.м)
72
52
Сколько изделий каждого вида требуется изготовить из имеющегося
материала, чтобы получить наибольший доход.
1.9.Для пошива курток и халатов используется два вида ткани А и В. Расход
ткани на каждое изделие (в м), запас ткани и прибыль от продажи изделия
каждого вида даны в таблице
Изделие
Расход ткани
Прибыль от продажи
одного изделия (в
вида А
вида В
руб)
куртка
2
0,25
10
халат
2,5
0,5
20
Запас ткани (м)
100
20
Сколько изделий каждого вида требуется сшить из имеющегося материала,
чтобы получить наибольший доход.
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.10. Для пошива двух видов швейных изделий используется два вида ткани А
и В. Расход ткани на каждое изделие (в м), запас ткани и прибыль от продажи
изделия каждого вида даны в таблице
Изделие
Расход ткани (в м)
Прибыль от продажи
одного изделия (в руб)
вида А
вида В
первого вида
3
0,5
30
второго вида
1
2,5
25
Запас
ткани
150
100
(м)
Сколько изделий каждого вида требуется сшить из имеющегося материала,
чтобы получить наибольший доход.
1.11. Для изготовление единицы сплава №1 требуется металла А – 2 единицы,
металла В – 3 единицы, металла С – 4 единицы. Для изготовление единицы
сплава №2 требуется металла А – 2 единицы, металла В – 5 единиц, металла С
– 2 единицы. Всего имеется металлов А, В и С соответственно 25, 50 и 40
единиц. Масса единицы сплава №1 равна 3 кг, а единицы сплава №2 – 4 кг.
Сколько единиц сплава №1 и сплава №2 нужно изготовить, чтобы их общая
масса была наибольшей.
1.12. Из двух видов сырья, запасы которого ограничены и составляют 60 и 45
единиц соответственно, изготавливается продукция трех видов А, В и С.
Затраты сырья каждого вида на изготовление единицы продукции каждого
вида и прибыль от производства единицы продукции каждого вида даны в
таблице
Вид сырья
Затраты сырья на 1 единицу
Запасы сырья
продукции вида
А
В
С
Вид 1
4
2
6
60
Вид 2
2
6
4
45
Прибыль (в руб)
12
15
19
Требуется найти такой план выпуска продукции, при котором сырье не будет
перерасходовано, а суммарная прибыль окажется наибольшей.
1.13. На участке работает 20 человек, каждый из них в среднем за год работает
1800 часов. Выделенные ресурсы: 32 т металла, 54000 квт/час электроэнергии.
План по реализации продукции: не менее 2000 изделий вида А и не менее 3000
изделий вида В. На выпуск 1000 изделий вида А затрачивается 3000 металла,
3000 квт/час электроэнергии и 3000 часов рабочего времени. На выпуск 1000
изделий вида В затрачивается 1000 металла, 6000 квт/час электроэнергии и
3000 часов рабочего времени. От реализации 1000 изделий вида А завод
получает прибыль 50000 рублей, от реализации 1000 изделий вида В – 70000
рублей. Выпуск какого количества изделий каждого вида надо запланировать
(в тыс.шт.), чтобы прибыль от их реализации была максимальной.
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.14. Завод выпускает два вида изделий на 4-х типах машин. Время,
необходимое для обработки каждого изделия этих видов изделий указанными
типами машин, время работы каждой машины и прибыль от реализации одного
изделия первого и второго видов указаны в таблице
Типы машин
1
2
3
4
Прибыль (у.е.)
Виды изделий
1
1
0,5
1
0
6
2
1
1
0
1
2
Время работы
18
12
12
9
Составить план выпуска продукции, чтобы прибыль от реализации этой
продукции была максимальной.
1.15. Для производства двух видов изделий А и В предприятие использует три
вида сырья. Нормы расхода сырья каждого вида на изготовление единицы
продукции вида А и В приведены в таблице. В ней также указаны прибыль от
реализации одного изделия каждого вида и общее количество сырья вида 1,2 и
3, которое может быть использовано предприятием.
Вид сырья
Норма расхода сырья (кг)
Общее количество
на одно изделие
сырья
А
В
1
12
4
300
2
4
4
120
3
3
12
252
Прибыль от реализации
30
40
1-го изделия (у.е.)
Составить план выпуска продукции, чтобы прибыль от реализации этой
продукции была максимальной.
1.16. На рынок в город привозят одним видом транспорта картофель из трех
сел А,В и С по 4,3 и 2 рубля за 1 кг соответственно. На погрузку тонны
картофеля в А требуется 1 мин., в В – 4 мин., в С – 3 мин. Чтобы продукт
вовремя поступал на рынок надо, чтобы на погрузку 12 тонн картофеля,
ежедневно требуемых для продажи, затрачивалось не более 40 мин. Сколько
надо привозить картофеля из каждого села, чтобы общая стоимость картофеля
на рынке была минимальной, если известно, что село А ежедневно может
отправлять не более 10т, село В – не более 8 т, село С – не более 6 т.
1.17. Ученической бригаде выделено два участка земли площадью 8 и 9 га
соответственно под посевы пшеницы и кукурузы. Средняя урожайность по
участкам и культурам (в ц с га) и прибыль от продажи 1 ц отражена в таблице
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
участки
1 участок
2 участок
культура
пшеница
16
14
кукуруза
35
30
прибыль от продажи 1 ц (д.е.)
3
2
Сколько гектаров и на каких участках необходимо отвести под каждую
культуру, чтобы получить от реализации наибольшую прибыль, если по плану
надо собрать не менее 150 ц пшеницы и не менее 220 ц кукурузы.
1.18. Для производства двух видов продукции П1 и П2 предприятие использует
4 типа станков. Количество станков, их необходимое количество на
изготовление одного комплекта продукции и прибыль от продажи на единицу
продукции приведены в таблице
Тип станка
Кол-во станков
Необходимое количество
станков на изготовление одного
комплекта продукции
П1
П2
строгальные
24
2
2
деревообделочные
16
1
2
токарные
32
4
фрезерные
24
4
Прибыль от реализации одной единицы
200
300
продукции (д.е.)
Сколько единиц каждого вида продукции требуется изготовить, чтобы
получить наибольшую сумму дохода?
1.19. Для производства двух видов продукции П1 и П2 предприятие использует
4 типа сырья. Запасы каждого вида сырья, необходимое количество сырья на
изготовление единицы каждого из видов продукции и прибыль от продажи на
единицу продукции приведены в таблице
Вид сырья
Запасы сырья
Необходимое количество сырья на
в условных
изготовление одной единицы
единицах
продукции
П1
П2
древесина
38 (вагонов)
2
3
кирпич
26 (вагонов)
2
1
шифер
30 (штабелей)
3
кровельное
36 (штабелей)
3
железо
Прибыль от реализации одной
700
500
единицы продукции (д.е.)
Сколько единиц каждого вида продукции требуется изготовить, чтобы
получить наибольшую сумму дохода?
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.20. Швейный цех фабрики изготавливает пальто и костюмы. На складе
имеется 448 метров костюмной ткани и 494 метра пальтовой. Цех располагает
фондом рабочего времени машинного оборудования в количестве 480 часов и
фондом работы мастеров 1200 человеко-часов. На изготовление пальто
требуется 2,6 м ткани, 2 часа рабочего времени машинного оборудования и 4
часа работы мастера. На изготовление костюма требуется 2,8 м ткани, 1,5 часа
рабочего времени машинного оборудования и 5 часов работы мастера.
Прибыль от реализации одного пальто составляет 300 рублей, а костюма – 200
рублей. Составить план выпуска продукции, при котором прибыль будет
наибольшей.
1.21. На мебельном комбинате для изготовления тумбочек и книжных шкафов
используется три вида сырья: древесина (куб. м), фанера (кв.м), стекло (кв.м).
Запасы сырья, количество единиц сырья, затрачиваемых на изготовление
продукции, а также величина прибыли, получаемая от реализации единицы
продукции, приведены в таблице
Нормы расхода сырья на
изготовление единицы
Запасы
продукции
Виды сырья
сырья
тумбочку
книжный
шкаф
Древесина (куб. м)
0,8
0,4
40
Фанера(кв. м)
0,2
0,1
20
Стекло (кв.м)
0,1
5
Прибыль от реализации
100
200
единицы продукции (в
руб)
Составить такой план выпуска продукции, чтобы от ее реализации получить
максимум прибыли.
1.22. На станках А и В разной производительности обрабатываются 3 вида
деталей. Всего нужно обработать деталей 1-го вида не более 100 штук, 2-го
вида – не более 140 штук, 3-го вида – не более 110 штук. На станке А можно
обработать 160 деталей, на станке В – 190 деталей. Стоимость электроэнергии
(в руб.), затрачиваемой одним станков на обработку одной детали, дано в
таблице
Тип
Вид детали
станка
1
2
3
А
4
8
12
В
8
10
6
Требуется составить такой план работы станков, при котором затраты
электроэнергии будут минимальными.
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.23. Для производства столов и шкафов мебельная фабрика использует
необходимые ресурсы. Нормы затрат ресурсов на одно изделие каждого вида,
прибыль от реализации одного изделия и общее количество имеющихся
ресурсов даны в таблице
Ресурсы
Нормы затрат ресурсов на
изготовление единицы
продукции
стол
шкаф
0,2
0,1
Древесина 1 вида (куб.
м)
Древесина 2 вида (куб.
м)
Трудоемкость
(человеко-часы)
Прибыль от реализации
единицы продукции (в
руб)
Составить такой план выпуска
максимум прибыли.
Общее количество
ресурсов
40
0,1
0,3
60
1,2
1,5
372
80
200
продукции, чтобы от ее реализации получить
1.24. Трикотажная фабрика использует для производства свитеров и пуловеров
следующие материалы: шерсть, силон, нитрон. Запасы материалов ограничены
и составляют соответственно 900, 400 и 300 кг. Количество пряжи каждого
вида (в кг), необходимой для изготовления 10 штук изделий, а также прибыль,
получаемая от реализации, приведены в таблице
Виды сырья
Запас сырья в кг
Затраты на 10 шт. (в кг)
свитера
пуловеры
Шерсть
900
4
2
Силон
400
2
1
Нитрон
300
1
1
Прибыль (в руб.)
80
50
Требуется установить такой план выпуска изделий каждого вида,
который бы обеспечил фабрике наибольшую прибыль от реализации всей
продукции.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи составления диеты
1.25. Требуется составить смесь, содержащую 3 химических вещества А, В и С.
Известно, что составленная смесь должна содержать вещества А не менее 6
единиц, В – не менее 8 единиц, С – не менее 12 единиц. Вещества содержатся в
двух видах продуктов в концентрации, указанной в таблице
Продукты
Химические вещества
А
В
С
1
2
1
3
2
1
2
4
Единица продукта вида 1 стоит 20 руб., продукта вида 2 – 30 рублей. Составить
смесь, чтобы стоимость используемых продуктов была минимальной.
1.26. Для сохранения здоровья человек должен потреблять в сутки некоторое
количество питательных веществ. Запасы этих веществ в продуктах П1 и П2 и
стоимость единицы продукта (в у.е.) даны в таблице
Питательные
Норма
Виды продуктов
вещества
П1
П2
жиры
8
2
5
белки
10
3
2
углеводы
14
1
6
вода
12
3
2
витамины
2
1
0
Стоимость
3
2
Определить минимальную стоимость питания из продуктов П1 и П2, при
которой организм получает не менее минимальной суточной нормы
питательных веществ всех видов.
1.27. Для кормления животных требуется составить суточный рацион,
содержащий необходимое количество питательных веществ видов А, В и С:
вещества вида А не менее 1000 единиц, вида В не менее 80 единиц, вида С не
менее 300 единиц. Указанные вещества содержатся в кормах двух видов 1 и 2.
Содержание количества единиц питательных веществ в 1 кг каждого вида
корма, запасы кормов и стоимость 1 кг корма приведены в таблице
Вид питательного
Содержание в 1 кг корма
Минимальная норма
вещества
вида
питательных веществ
1
2
А
50
20
1000
В
2
4
80
С
15
10
300
Стоимость 1 кг
40
30
корма (руб)
Запас кормов (в кг)
200
500
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Какое количество корма каждого вида надо расходовать ежедневно на
составление суточного рациона нужной питательности, чтобы затраты на него
были минимальными.
1.28. Для кормления животных требуется составить суточный рацион,
содержащий необходимое количество питательных веществ видов А, В и С:
вещества вида А не менее 10 единиц, вида В не менее 16 единиц, вида С не
менее 8 единиц. Указанные вещества содержатся в кормах двух видов 1 и 2.
Содержание количества единиц питательных веществ в 1 кг каждого вида
корма, запасы кормов и стоимость 1 кг корма приведены в таблице
Вид питательного
вещества
Содержание в 1 кг корма
вида
1
2
2
1
2
4
1
4
5
6
Минимальная
норма питательных
веществ
10
16
8
А
В
С
Стоимость
1
кг
корма (руб)
Запас кормов (в кг)
20
50
Какое количество корма каждого вида надо расходовать ежедневно на
составление суточного рациона нужной питательности, чтобы затраты на него
были минимальными.
1.29. Для кормления животных требуется составить суточный рацион,
содержащий необходимое количество питательных веществ видов А, В и С:
вещества вида А не менее 100 единиц, вида В не менее 40 единиц, вида С не
менее 30 единиц. Указанные вещества содержатся в кормах двух видов 1 и 2.
Содержание количества единиц питательных веществ в 1 кг каждого вида
корма, запасы кормов и стоимость 1 кг корма приведены в таблице
Вид питательного
Содержание в 1 кг корма
Минимальная норма
вещества
вида
питательных веществ
1
2
А
6
2
100
В
2
8
40
С
10
0
30
Стоимость 1 кг
20
30
корма (руб)
Запас кормов (в кг)
300
100
Какое количество корма каждого вида надо расходовать ежедневно на
составление суточного рациона нужной питательности, чтобы затраты на него
были минимальными
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.30. Минимальная суточная потребность живого организма в белках, жирах и
углеводах составляет соответственно 45, 10 и 60 условных единиц. Указанные
вещества содержатся в двух продуктах питания А и В, причем продукта А
можно потреблять в сутки не более 25 единиц, а продукта В не более 30
единиц. Содержание количества единиц питательных веществ в 1 кг каждого
вида продукта и стоимость 1 кг продукта приведены в таблице
Вид питательного
вещества
Содержание в 1 кг
продукта
А
В
3
3
2
1
3
8
10
8
Минимальная
норма питательных
веществ
45
10
60
белки
жиры
углеводы
Стоимость 1 кг продукта
(руб)
Рассчитать необходимое количество обоих продуктов, чтобы удовлетворить
потребность организма в указанных питательных веществах при минимальных
денежных затратах.
1.31. Минимальная суточная потребность живого организма в белках, жирах и
углеводах составляет соответственно 50, 20 и 60 условных единиц. Указанные
вещества содержатся в двух продуктах питания А и В, причем продукта А
можно потреблять в сутки не более 15 единиц, а продукта В не более 25
единиц.. Содержание количества единиц питательных веществ в 1 кг каждого
вида продукта и стоимость 1 кг продукта приведены в таблице
Вид питательного
Содержание в 1 кг
Минимальная
вещества
продукта
норма питательных
веществ
А
В
белки
8
5
50
жиры
7
2
20
углеводы
1
10
60
Стоимость 1 кг продукта
5
12
(руб)
Рассчитать необходимое количество обоих продуктов, чтобы удовлетворить
потребность организма в указанных питательных веществах при минимальных
денежных затратах.
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Практическая работа № 2. Опорные и оптимальные планы ЗЛП
1.2. Опорный план. Базис опорного плана. Оптимальный опорный план.
Необходимые теоретические сведения
Опр. 4. План называется опорным, если вектора Aj, j=1,..n, входящие в
разложение (2), соответствующие положительным компонентам xj вектора
x(x1,x2,…,xn), являются линейно независимыми.
Теорема 3. (о связи вершин и опорных планов)
Если x(x1,x2,…,xn) – угловая точка многогранника решений, то вектора Aj,
j=1,..n, входящие в разложение (2): A1x1+A2x2+…+Anxn=A0, соответствующие
положительным компонентам вектора х являются линейно независимыми, т.е.
х – опорный план.
Вывод: для отыскания оптимального плана необходимо исследовать только
опорные планы.
Теорема 4. (необходимое и достаточное условие оптимальности опорного
плана)
Невырожденный опорный план является оптимальным для задачи (1)-(3) тогда
и только тогда, когда
Fj-cj≤0 для всех j=1,..n, где
Сj - коэффициент целевой функции (1), соответствующий вектору Aj,
Fj – значение целевой функции (1), если вместо неизвестных подставить
коэффициенты разложения вектора Aj по векторам базиса, соответствующего
данному опорному плану.
Примеры решения задач
Пример 1. Найти какой-либо опорный план задачи линейного
программирования:
F=x1-5x2+3x3-x4 min
3x1  2 x 2  2 x3  x 4  5,

 x1  4 x 2  2 x3  x 4  5,

 x j  0( j  1,4)
Выпишем вектора Aj
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 3
 2
  2
1
A1   , A2   , A3   , A4   ,
1
  2
1
 4
1) Рассмотрим систему векторов
независима, т.к.
3 2
1 4
{A1, A2}.
Система {A1, A2} - линейно
 10  0
x1, x2 – базисные координаты, x3=x4=0. Найдем опорный план (х1, х2, 0, 0).
Подставим вектор в систему ограничений:
3x1  2 x 2  5,
 x1  1,
 

 x1  4 x 2  5
 x2  1
Х(0)=(1, 1, 0, 0) – невырожденный опорный план.
2) Рассмотрим систему векторов
независима, т.к.
3 2
1 2
{A1, A3}.
Система {A1, A3} - линейно
0
x1, x3 – базисные координаты, x2=x4=0. Найдем опорный план (х1, 0, х3, 0).
Подставим вектор в систему ограничений:
3x1  2 x3  5,
 x1  0,
 

 x3  2.5
 x1  2 x3  5
Х(0)=(0, 0, -2.5, 0) – не план.
3) Рассмотрим систему векторов
независима, т.к.
3 1
1 1
{A1, A4}.
Система {A1, A4} - линейно
20
x1, x4 – базисные координаты, x2=x3=0. Найдем опорный план (х1, 0, 0, х4).
Подставим вектор в систему ограничений:
3x1  x 4  5,
 x1  0,
 

 x1  x 4  5
 x4  5
Х(0)=(0, 0, 0, 5) – вырожденный опорный план.
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи для самостоятельного решения
2.1.Найти какой-либо опорный план задачи линейного программирования
F=x1+9x2-x3+2x4 min
 x1  x 2  4 x3  x 4  3,

 x1  x 2  x3  9 x 4  8,

 x j  0( j  1,4)
В задачах 2.2. – 2.5 найти базисы опорных планов X(0), приведенных в условиях
(в случае, если X(0) - вырожденный опорный план, найти все его базисы)
2.2
x1+2x2 - x3= 4,
2x1-5x2+3x3=-3,
xj 0 (j=1,2,.3)
X(0 =(2,1,0)
2.3
x1+x2-3x3+2x4=1,
x1- x2-3x3+ x4=1,
xj 0 (j=1,2,3,4)
X(0 =(1,0,0,0)
2.4
x1+x2+3x3+ x4=1,
-x1+ x2-x3+2x4=1,
x1+2x2+4x3-x4=2,
xj 0(j=1,2,3,4)
X(0 =(0,1,0,0)
2.5
x1+x2+x3+ x4=0,
x1 -x2+x3-x4=0,
x1+x2-x3+x4=0,
xj 0(j=1,2,3,4)
X(0 =(0,0,0,0)
В задачах 2.6 – 2.9 приведены системы линейно-независимых вектор-столбцов
{As1,…,Asm). Проверить, является ли данная система векторов базисом
некоторого опорного плана и, если является, найти этот опорный план
2.6
x1+ x2 + x3= 1,
2.7
x1+x2+x3 =1,
x1- x2+2x3=-2,
x1- x2+2x3 =2,
xj 0 (j=1,2,.3)
xj 0 (j=1,2,3)
{A1,A2}
{A1,A2}
2.8
x1+x2+x3=1,
2x1- x2-3x3=2,
2.9
xj 0(j=1,2,3)
{A1,A3}
x1+x2+x4+3x5 +4x6=1,
x2+x3+7x5+2x6=1,
x1+ x3x6=1,
xj 0(j=1,2,3,4,5,6)
{A1,A2,A3}
В задачах 2.10-2.17 исследовать опорный план X(0) ЗЛП, приведенных в
условиях, а именно, определить, какой из трех случаев имеет место:
а) план X(0) оптимальный;
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
б) задача неразрешима; целевая функция не ограничена снизу на множестве
планов;
в) имеется возможность улучшить план
2.10
x1-2x2+x3  min
x1- x2 +2 x3= 0,
x1+ x2+5x3=2,
xj 0 (j=1,2,.3)
X(0 =(1,1,0)
2.11
x1-2x2-2x3  min
x1-x2+2x3 =0,
x1+ x2+5x3 =2,
xj 0 (j=1,2,3)
X(0 =(1,1,0)
2.12
x1-2x2-4x3  min
x1-x2-x3=1,
x1+ x2+x3=3,
xj 0(j=1,2,3)
X(0 =(2,1,0)
2.13
x1-x2-x3  min
-2x1+x2+x3 =4,
-x1+2x2-x3 =-1,
xj 0(j=1,2,3)
X(0 =(0,1,3)
2.14
4x1-x2-5x3  min
x2 + x3= 2,
3x1+2 x2-x3=1,
xj 0 (j=1,2,.3)
X(0 =(0,1,1)
2.15
-x1-2x2+5x3  min
x1-3x2+11x3 =-9,
3x1- x2+9x3 =5,
xj 0 (j=1,2,3)
X(0 =(3,4,0)
2.16
-x1-4x2+7x3  min
2x1-2x2+14x3=2,
x1- 2x2+10x3=0,
xj 0(j=1,2,3)
2.17
-x1-3x2+x3 +x4+x5 min
x1-x2+x3+3x4 -3x5=1,
x1 +x2-x3+x4+x5=1,
x1 +x2+x3+5x4-x5=3,
xj 0(j=1,2,3,4,5)
X(0 =(1,1,1,0,0)
X(0 =(2,1,0)
Практическая работа № 3. Симплекс-метод решения задач линейного
программирования
1.3. Решение задачи линейного программирования симплекс-методом
Необходимые теоретические сведения

Каждая угловая
опорному плану.
точка
многогранника
25
решений
соответствует
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»



Существует такая угловая точка, в которой целевая функция достигает
своего экстремального значения, если допустимое множество
ограничено.
Каждому опорному плану соответствует система из m линейно
независимых векторов, содержащаяся в системе {A1,A2,…,An}.
Для отыскания оптимального плана необходимо исследовать только
опорные планы. Верхняя граница количества опорных планов
определяется числом сочетаний
С nm 

n!
,
m!(n  m)!
При больших n и m найти оптимальный план перебором трудно.
Необходимо упорядочить переход от одного плана к другому. Таким
методом является симплекс-метод – метод последовательного
улучшения плана.
Идея симплекс-метода
Симплекс-метод является схемой, позволяющей исходя из известного опорного
плана за конечное число шагов получить оптимальный план. Каждый шаг
заключается в нахождении нового плана, которому соответствует меньшее
значение целевой функции, чем предыдущему. Процесс продолжается до тех
пор, пока полученный план не будет оптимальным. Если задача не обладает
планами, или целевая функция неограничена на многограннике решений, то
симплекс-метод позволяет установить это в процессе решения.
Задачи для самостоятельного решения:
Постановка задачи. Решить с помощью симплекс-метода задачи линейного
программирования
3.1. F(x1,x2,x3,x4)=2x1+x2-x3-x4min при ограничениях
2x1+x2+x3- x4 2,
x1+x2+x3-x4 4,
-4x1 -x2+x3 +x4 2
x1,x2,x3,x40
3.2. F(x1,x2,x3,x4)=10x1-x2+4x3+4x4min при ограничениях
x1+x2+3x3- x4 8,
2x1-4x2+3x3-5x4 6,
5x1 +5x2+2x3 +x4 5
x1,x2,x3,x40
3.3. F(x1,x2,x3,x4)=x1-x2+4x3+x4min при ограничениях
x1+x2+3x3- x4 18,
2x1-4x2+3x3-5x4 16,
x1 +5x2+2x3 +x4 5
x1,x2,x3,x40
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.4. F(x1,x2,x3,x4)=x1+4x2-3x3-x4+9min при ограничениях
2x1-3x2-x3 10,
4x1+x2-5x3+2x4 14,
3x1 +8x3 +7x4 15,
x1,x2,x3,x40
3.5. F(x1,x2,x3,x4)=-x1+x2-2x3+x4min при ограничениях
x1+x2+2x3+3 x4 3,
x2-x3-x4 1,
x1 +x4 5,
x1,x2,x3,x40
3.6. F(x1,x2,x3,x4)=2x1+x2-x3-x4max при ограничениях
2x1+x2+2x3+ x4 7,
x1+x2+x3-x4 4,
-4x1 -x2+x3 +2x4 2,
x1,x2,x3,x40
3.7. F(x1,x2,x3,x4)= -x1-x2-x3-5x4max при ограничениях
x1+2x2 7,
x1+3x2+2x3 6,
x2+3x3 +2x4 8,
x1,x2,x3,x40
3.8. F(x1,x2,x3,x4)= x1-x2+2x3-3x4max при ограничениях
3x1+2x2 20,
x1+3x2+3x3 15,
2 x1+2x2+3x3 +5x4 18,
x1,x2,x3,x40
3.9. F(x1,x2,x3,x4)= -x1-x2-x3-x4min при ограничениях
x1+x2 +x3+3x4 3,
x1+x2-x3 +x4 1,
x1-x2+x3 +x4 1,
x1,x2,x3,x40
3.10. F(x1,x2,x3,x4)= 2x1-2x2+4x3+x4max при ограничениях
x1+x2 +3x3-6x4 8,
2x1-4x2+3x3 -5x4 6,
x1+x2+2x3 +x4 5,
x1,x2,x3,x40
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Практическая работа № 4. Двойственная задача линейного
программирования
1.4. Двойственная задача линейного программирования
Необходимые теоретические сведения
Каждой задаче линейного программирования можно определенным образом
сопоставить другую задачу, называемую двойственной.
Исходная задача:
Двойственная задача:
F=c1x1+c2x2+…+ cnxn  max
Z=b1y1+b2y2+…+ bmym  min
a11x1+a12x2+…+a1nxn  b1
a21x1+a22x2+…+a2nxn  b2
a11y1+a21y2+…+am1ym ≥ c1
a12y1+a22y2+…+am2ym ≥ c2
…
…
am1x1+am2x2+…+amnxn  bm
a1ny1+a2ny2+…+amnym ≥ cn
xj≥ 0, j=1,…,n
yi≥ 0, i=1,…,m
Правила построения двойственной задачи:
1) Если целевая функция задана на max в исходной задаче, то в
двойственной – на min, и наоборот.
2) Матрица коэффициентов А двойственной задачи строится
транспонированием матрицы исходной задачи.
3) Число переменных в двойственной задаче равно числу ограничений в
исходной, а число ограничений равно числу переменных в исходной
задаче.
4) Коэффициенты при неизвестных в целевой функции – это свободные
члены исходной задачи, а столбец свободных членов строится из
коэффициентов целевой функции.
Теорема двойственности. Если из пары двойственных задач одна обладает
оптимальным решением, то и другая имеет оптимальный план, причем min
F=max Z. Если целевая функция одной из задач неограниченна, то и другая
задача не имеет решения.
Экономический смысл двойственной задачи
Z=b1y1+b2y2+…+ bmym  min
a11y1+a21y2+…+am1ym≥c1
a12y1+a22y2+…+am2ym≥c2
…
a1ny1+a2ny2+…+amnym≥cn
yi≥0, i=1,…,m
yi – стоимость единицы i-го вида ресурса,
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
m
b y
i 1
m
i
a
i 1
ij
i
- стоимость всех ресурсов,
y i - стоимость ресурсов на изготовление единицы продукции j-го вида
Задача состоит в том, чтобы найти цену ресурсов, чтобы стоимость затрат была
наименьшей.
Виды моделей двойственных задач
Исходная задача
1) F=(c,x)  min
Ax=A0
x≥0
2) F=(c,x)  max
Ax=A0
x≥0
3) F=(c,x)  min
Ax ≥ A0
x≥0
4) F=(c,x)  max
Ax ≤ A0
x≥0
Двойственная задача
Z=(y,a0)  max
YA≤ c
Z=(y,a0)  min
YA≥ c
Z=(y,a0)  max
YA≤ c
y≥0
Z=(y,a0)  min
YA≥ c
y≥0
Задачи для самостоятельного решения:
Для задач 4.1-4.2 составить им двойственные и найти решение обеих
задач.
4.1. F(x1,x2)= 2x1+7x2max при ограничениях
-2x1+3x2  14,
x1+x2 8,
x1,x20
4.2. F(x1,x2)= -2x1-3x2min при ограничениях
-4x1+2x2 4,
x1+x2 6,
x1,x20
Постановка задачи. Для задач 1.1-1.29 и 4.3–4.5 сформулировать
двойственную. Решить исходную задачу графическим способом. Решить
двойственную задачу с помощью табличного процессора Excel (см.
Приложение 1). Объяснить экономический и геометрический смысл
переменных в обеих задачах.
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4.3. При изготовлении продукции П1 и П2 используется 4 вида сырья S1, S2, S3,
S4. Запасы каждого вида сырья ограничены. Количество единиц сырья,
необходимых для изготовления единицы каждого из видов продукции и доход
от продажи единицы изделия (в у.е.) даны в таблице
Виды
Запасы
Виды продукции
сырья
сырья
П1
П2
S1
20
1
3
S2
15
2
2
S3
14
1
4
S4
12
3
1
Доход
5
3
Требуется составить такой план выпуска продукции видов П1 и П2, при
котором доход от реализации изделий будет максимальным.
4.4. Для сохранения здоровья человек должен потреблять в сутки некоторое
количество питательных веществ. Запасы этих веществ в продуктах П1 и П2 и
стоимость единицы продукта (в у.е.) даны в таблице
Питательные
Норма
Виды продуктов
вещества
П1
П2
жиры
10
1
5
белки
12
3
2
углеводы
16
2
4
вода
10
2
2
витамины
1
1
0
Стоимость
3
2
Определить минимальную стоимость питания из продуктов П1 и П2, при
которой организм получает не менее минимальной суточной нормы
питательных веществ всех видов.
4.5. На изготовление продукции П1 и П2 используется 4 вида сырья S1, S2, S3,
S4.Запасы каждого вида сырья ограничены. Количество единиц сырья,
необходимых для изготовления единицы каждого из видов продукции и доход
от продажи единицы изделия (в у.е.) даны в таблице
Виды
Запасы
Виды продукции
сырья
сырья
П1
П2
S1
20
1
3
S2
15
2
2
S3
14
1
4
S4
12
3
1
Доход
5
3
Требуется составить такой план выпуска продукции видов П1 и П2, при
котором доход от реализации изделий будет максимальным.
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Практическая работа № 5. Решение транспортной задачи линейного
программирования
1.5. Транспортная задача
Необходимые теоретические сведения
Транспортная задача является представителем класса задач линейного
программирования и поэтому обладает всеми качествами линейных
оптимизационных задач, но одновременно она имеет и ряд дополнительных
полезных свойств, которые позволили разработать специальные методы ее
решения.
Постановка транспортной задачи.
Некоторый однородный продукт, сосредоточенный у m поставщиков Ai,
i=1,…,m в количестве ai,, (i=1,…,m) единиц соответственно, необходимо
доставить n потребителям Вj,(j=1,…,n) в количестве bj,(j=1,…,n) единиц.
Известны стоимости перевозок: Cij – стоимость перевозки единицы груза от iго поставщика j-му потребителю.
Необходимо составить план перевозок, имеющий минимальную стоимость,
позволяющий вывести все грузы, полностью удовлетворить все потребности.
Процесс решения транспортной задачи удобно оформлять в виде
последовательности таблиц, структура которых представлена на рис.2.
Строки транспортной таблицы соответствуют пунктам производства (в
последней клетке каждой строки указан объем запаса продукта ai), а столбцы
— пунктам потребления (последняя клетка каждого столбца содержит значение
потребности bj). Все клетки таблицы (кроме тех, которые расположены в
нижней строке и правом столбце) содержат информацию о перевозке из i-го
пункта в j-й: в левом верхнем углу находится цена перевозки единицы
продукта, а в правом нижнем — значение объема перевозимого груза для
данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0),
называют свободными, а ненулевые — занятыми (xi,j>0).
Поставщики
Потребители
Запасы
B
B
….
B
1
2
C11
X11
C21
……
X21
……
….
Cm1
….
Xm2
b2
a1
X2n
a2
Xmn
am
Cmn
……
bn
Рис. 2.
31
X1n
….
……
Cm2
Xm1
C1n
C2n
X22
….
b1
……
X12
C22
A2
Am
Потребности
……
C12
A1
….
n
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Построим математическую модель:
Пусть xij – количество единиц груза, запланированного к перевозке от i-го
поставщика j-му потребителю
m
n
Z   xij cij 
 min
(1) – целевая функция
i 1 j 1
n
x
j 1
ij
 ai , i  1, m
(2)- все грузы вывезены
ij
 b j , j  1, n
(3)- все потребности удовлетворены
m
x
i 1
Опр. 5.
Если суммарные запасы совпадают с суммарным
потребностей, то транспортная задача называется закрытой.
запасом
Теорема. Любая транспортная задача, у которой суммарный объем запасов
совпадает с суммарным объемом потребностей, имеет решение.
Опр. 6. Всякое неотрицательное решение систем уравнений (1)-(3),
определяемое матрицей X=(xij), i=1,…,m, j=1,…,n называется планом
транспортной задачи.
Опр. 7. План x*, при котором функция (1) принимает минимальное значение
называется оптимальным планом транспортной задачи.
Опр. 8. План называется опорным, если в нем невозможно построить цикл по
занятым клеткам.
Опр. 9. План называется невырожденным, если в нем (n+m-1) занятая клетка.
Если занятых клеток меньше, то план называется вырожденным.
По аналогии с другими задачами линейного программирования решение
транспортной задачи начинается с построения допустимого базисного плана.
Методы построения опорного плана транспортной задачи
Метод северо-западного угла. Суть метода состоит в последовательном
распределении всех запасов, имеющихся в первом, втором и т. д. пунктах
производства, по первому, второму и т. д. пунктам потребления. Каждый шаг
распределения сводится к попытке полного исчерпания запасов в очередном
пункте производства или к попытке полного удовлетворения потребностей в
очередном пункте потребления.
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 1. Построение опорного плана методом северо-западного угла.
Пусть условия транспортной задачи заданы таблице 3.
Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение
потребностей первого потребителя B1 за счет запаса поставщика А1.
Для этого сравниваем a1 = 100 с bi =200, a1< b1 меньший из объемов, т. е. 100
ед. записываем в левый нижний угол клетки А1B1. Запасы первого поставщика
полностью израсходованы, по этому остальные клетки первой строки
прочеркиваем.
Потребности В остались неудовлетворенными на 200–100=100 ед. Сравниваем
этот остаток с запасами поставщика А2: так как 100<250, то 100 ед. записываем
в клетку А2 .B1, чем полностью удовлетворяем потребности потребителя B1, а
оставшиеся клетки в первом столбце прочеркиваем.
Таблица 3
Поставщики
А1
А2
А3
А4
Потребности
Потребители
В1
В2
7
100 10
2
100
150 7
8
50 5
Запасы
В3
В4
В5
4
1
4
10
6
11
100 3
50 2
50 16
100
13
11
8
12
200
200
100
2
250
250
100
250
200
300
850
У поставщика А2 осталось 150 ед. груза. Удовлетворяем потребителя B2
за счет оставшегося у поставщика А2 груза. Для этого сравниваем этот остаток
с потребностями потребителя B2: 150<200, записываем 150 ед. в клетку А2B2 и,
так как запасы А2 полностью израсходованы, прочеркиваем остальные клетки
второй строки. Потребности B2 остались неудовлетворенными на 50 ед.
Удовлетворяем их за счет поставщика А3 и переходим к удовлетворению B3 за
счет остатка, имеющегося у поставщика А3, и т. д. Процесс продолжаем до тех
пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На
этом построение первоначального опорного плана заканчивается.
Таким образом, в табл. в правых верхних углах клеток стоят числа,
определяющие стоимость перевозки единицы грузов, а в левых нижних углах
— числа, определяющие план перевозок, так как их сумма по строкам равна
запасам соответствующего поставщика, а сумма по столбцам — потребности
соответствующего потребителя.
x (0)
0
0
0 
100 0


0
0 
100 150 0

- первоначальный план
0
50 100 50 0 


 0

0
0
50
250


33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Проверим, является ли план, построенный в Таблице 3, опорным. Видим,
что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и
в любую другую занятую клетку, двигаясь только по занятым ячейкам,
невозможно. Следовательно, план является опорным. В то же время план
невырожденный, так как содержит точно m + n -1 = 4 + 5 - 1 = 8 занятых
клеток.
Найдем общую стоимость составленного плана как сумму произведений
объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие
стоимости в этих же ячейках:
Z = 100 *10 + 100*2 + 150 *7+ 50 *5 + 100*3 + 50*2 + 50*16+ 250*13 = 6950
(eд.)
Если при составлении опорного плана учитывать стоимость перевозки
единицы груза, то, очевидно, план будет значительно ближе к оптимальному.
Метод минимальной стоимости. Суть метода заключается в том, что из всей
таблицы стоимостей выбирают наименьшую, и в клетку, которая ей
соответствует, помещают меньшее из чисел ai, или bj . Затем, из рассмотрения
исключают либо строку, соответствующую поставщику, запасы которого
полностью израсходованы, либо столбец, соответствующий потребителю,
потребности которого полностью удовлетворены, либо и строку и столбец,
если израсходованы запасы поставщика и удовлетворены потребности
потребителя. Из оставшейся части таблицы стоимостей снова выбирают
наименьшую стоимость, и процесс распределения запасов продолжают, пока
все запасы не будут распределены, а потребности удовлетворены.
Пример 2. Построение опорного плана методом минимальной стоимости.
Таблица 4
Поставщики
А1
А2
А3
А4
Потребности
Потребители
В1
В2
В3
10
200
7
2
50
200
4
7
8
11
150
200
Запасы
В4
100 1
10
11
200 2
50 13
250
3
2
8
12
16
100
4
6
5
100
100
В5
100
250
200
300
850
Составим с помощью этого метода опорный план уже рассмотренной задачи.
Запишем ее условие в таблицу (табл. 4). Выбираем в таблице наименьшую
стоимость (это стоимость, помещенная в клетке A1 , B4 ) так как A1 = b4, 100 ед.
груза помещаем в этой клетке и исключаем из рассмотрения первую строку и
четвертый столбец. В оставшейся таблице стоимостей наименьшей является
стоимость, расположенная в клетке A2 , B1 и в клетке A3 , B5. Заполняем любую
из них, например A2 , B1. Имеем 200 < 250, следовательно, записываем в нее
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
200 и исключаем из рассмотрения столбец B1. В клетку A3 , B5 записываем 200
ед. и исключаем из рассмотрения строку A3 . В оставшейся таблице стоимостей
снова выбираем наименьшую стоимость и продолжаем процесс до тех пор,
пока все запасы не будут распределены, а потребности удовлетворены. В
результате получен план
X = (X14 = 100; X21 = 200; X22 = 50; X35= 200, X42 = 150; X43 = 100; X45 = 50),
остальные значения переменных равны нулю.
x (0)
0
0 100 0 
 0


0
0
0 
 200 50
- первоначальный план

0
0
0
0 200 


 0 150 100 0
50 

План не содержит циклов и состоит из семи положительных перевозок,
следовательно, является вырожденным опорным планом. Определим его
стоимость:
Z = 100*1+200*2+50*7+200*2+150*8+100*12+50*13= 4300 (ед)
Стоимость плана перевозок значительно меньше, следовательно, он ближе к
оптимальному.
Алгоритм метода потенциалов для транспортной задачи
Алгоритм начинается с выбора некоторого допустимого базисного плана
(первоначальный план перевозок, составленный, например, методом северозападного угла). Если данный план не вырожденный, то он содержит m+n-1
ненулевых базисных клеток, и по нему можно так определить потенциалы ui и
vj, чтобы для каждой базисной клетки (т. е. для той, в которой xi,j > 0)
выполнялось условие
vj-ui=ci,j, если xi,j>0, (4)
Переменные ui называют потенциалами пунктов производства, a vj —
потенциалами пунктов потребления.
Для этого составьте систему для заполненных(!) клеток плана перевозок:
vj-ui=ci,j; где ci,j - стоимость перевозки из пункта i в пункт j.
Поскольку система (4) содержит m+n-1 уравнение и m+n неизвестных,
то один из потенциалов можно задать произвольно (например, приравнять v1
или u1 к нулю).
После этого остальные неизвестные vj и ui - определяются однозначно.
Критерий оптимальности.
Для того, чтобы допустимый план транспортной задачи xi,j был
оптимальным, необходимо и достаточно, чтобы нашлись такие потенциалы
ui, vj, для которых
vj-ui=ci,j, если xi,j>0,
vj-ui≤ci,j, если xi,j=0
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вычислите
коэффициенты
изменения
стоимости
(∆i,j)
для
незаполненных(!) клеток плана: ∆i,j =(vj + ui )- ci,j;
Заметьте: если все ∆i,j оказались отрицательными, то полученный план
оптимальный. Если есть хотя бы один положительный элемент ∆i,j, то далее
ведущей (опорной ) клеткой будет клетка [i,j] (при ∆i,j>0).
Для того, чтобы найти новый план перевозок необходимо составить цикл
пересчета. Цикл пересчета представляет собой замкнутую ломаную линию,
состоящую из горизонтальных и вертикальных линий, концы которых лежат в
заполненных клетках. Ломаная начинается и заканчивается в опорной клетке.
Узел в опорной клетке считается положительным, следующий отрицательный, и так далее чередуясь. Берется минимальное по абсолютной
величине значение в отрицательных клетках. Во всех отрицательных клетках
это значение отнимается, в положительных прибавляется. Получили новый
план перевозок. Цикл повторяется до тех, пор пока все ∆i,j не станут
отрицательными, т.е. пока не будет получен оптимальный план.
Задания для самостоятельного решения
Найти первоначальный опорный план двумя методами: методом северозападного угла и методом минимальной стоимости.
5.1.
пункты назначения
B1
B2
B3
B4
Запасы
пункты отправления
A1
A2
A3
Потребности
5.2.
пункты назначения
2
3
2
4
3
2
5
1
4
3
2
6
20
30
30
10
B1
B2
B3
B4
1
5
2
4
2
2
5
1
4
3
2
2
30
40
20
90
Запасы
пункты отправления
A1
A2
A3
Потребности
5.3.
пункты назначения
20
30
30
10
B1
B2
B3
B4
4
2
1
4
3
2
5
2
1
3
2
4
30
40
20
90
Запасы
пункты отправления
A1
A2
A3
Потребности
20
30
30
36
10
30
40
20
90
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5.4.
пункты назначения
B1
B2
B3
B4
2
3
2
4
3
2
5
1
4
3
2
6
Запасы
пункты отправления
A1
A2
A3
Потребности
5.5.
пункты назначения
20
30
30
20
B1
B2
B3
B4
9
3
8
4
3
1
5
10
4
3
1
6
40
40
20
100
Запасы
пункты отправления
A1
A2
A3
Потребности
5.6.
пункты назначения
20
40
30
10
B1
B2
B3
B4
2
3
2
3
4
2
5
4
7
1
7
2
50
40
10
100
Запасы
пункты отправления
A1
A2
A3
Потребности
5.7.
пункты назначения
10
30
30
10
B1
B2
B3
B4
10
3
2
4
3
2
5
1
4
6
1
5
30
30
20
80
Запасы
пункты отправления
A1
A2
A3
Потребности
5.8.
пункты назначения
20
35
30
10
B1
B2
B3
B4
8
3
2
4
6
3
2
1
4
1
6
6
30
40
25
95
Запасы
пункты отправления
A1
A2
A3
Потребности
20
30
30
37
30
30
40
40
110
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решить транспортные задачи методом потенциалов.
5.9. Две шахты снабжают углем 3 электростанции. Известно, что на первой
шахте добывается 300 т угля, на второй – 400 т, причем эти 700 т потребляются
3 электростанциями в количестве 320, 180 и 200 т соответственно. Известны
также стоимости (в руб.) перевозки одной тонны угля с каждой шахты на
каждую электростанцию. Требуется составить такой план перевозок угля, при
котором весь уголь будет вывезен из шахт и доставлен в нужном количестве на
каждую электростанцию, причем стоимость перевозок будет минимальна.
Шахты
Количество
добываемого
угля
1
2
300
400
Потребление угля электростанциями
первой
второй
третьей
320
180
200
Стоимость перевозок
9
12
11
7
10
13
5.10. Матрица данных в транспортной задаче имеет вид
пункты назначения
B1
B2
B3
B4
Запасы
пункты отправления
2
3
2
4
A1
30
3
2
5
1
A2
40
4
3
2
6
A3
20
Потребности
20
30
30
10
90
Определить опорный план транспортной задачи методом северо-западного угла
Определить оптимальный план транспортной задачи методом потенциалов
5.11. Матрица данных в транспортной задаче имеет вид
пункты назначения
B1
B2
B3
B4
2
3
2
4
3
2
5
1
4
3
2
6
Запасы
пункты отправления
A1
A2
A3
Потребности
20
30
30
10
30
40
20
90
Определить опорный план транспортной задачи методом минимального
элемента
Определить оптимальный план транспортной задачи методом потенциалов.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5.12. Матрица данных в транспортной задаче имеет вид
пункты назначения
B1
B2
B3
B4
Запасы
пункты отправления
1
3
2
4
A1
50
5
1
4
2
A2
30
4
6
2
6
A3
20
Потребности
20
30
40
10
100
Определить опорный план транспортной задачи методом северо-западного угла
Определить оптимальный план транспортной задачи методом потенциалов
5.13. Матрица данных в транспортной задаче имеет вид
пункты назначения
B1
B2
B3
B4
Запасы
пункты отправления
2
5
2
4
A1
50
3
2
1
3
A2
40
6
3
2
6
A3
10
Потребности
10
50
20
20
100
Определить опорный план транспортной задачи методом минимального
элемента
Определить оптимальный план транспортной задачи методом потенциалов
5.14. Матрица данных в транспортной задаче имеет вид
пункты назначения
B1
B2
B3
B4
Запасы
пункты отправления
2
3
6
4
A1
20
3
1
5
1
A2
60
3
3
2
2
A3
20
Потребности
20
40
30
10
100
Определить опорный план транспортной задачи методом северо-западного угла
Определить оптимальный план транспортной задачи методом потенциалов
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕМА 2. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Практическая работа № 6. Решение задачи нелинейного программирования
графическим методом
2.1.Графический метод решения задачи нелинейного программирования
Необходимые теоретические сведения
В большинстве инженерных задач построение математической модели не
удается свести к задаче линейного программирования.
Математические модели в задачах проектирования реальных объектов или
технологических процессов должны отражать реальные протекающие в них
физические и, как правило, нелинейные процессы. Переменные этих объектов
или процессов связанны между собой физическими нелинейными законами,
такими, как законы сохранения массы или энергии. Они ограничены
предельными диапазонами, обеспечивающими физическую реализуемость
данного объекта или процесса. В результате, большинство задач
математического программирования, которые встречаются в научноисследовательских проектах и в задачах проектирования – это задачи
нелинейного программирования (НП).
Постановка задачи. Найти условный экстремум
f(x1,x2,…,xn)max (min) при ограничениях
gi (x1,x2,…,xn) =bi (i=1,…,m) графическим способом.
Процесс нахождения решения задачи нелинейного программирования
графическим способом включает следующие этапы:
1°. Нахождение области допустимых решений задачи, определяемую системой
ограничений (если она пуста, то задача не имеет решения).
2°. Построение линий уровня F(x1,х2) = C.
3°. Определение линии уровня наивысшего (наинизшего) уровня или
установление неразрешимости задачи из-за неограниченность целевой
функции сверху (снизу) на множестве допустимых решений.
4°. Нахождение точки области допустимых решений, через которую проходит
линия уровня наивысшего (наинизшего) уровня, и определение в ней значения
целевой функции.
Указанная точка может находиться как на границе области допустимых
решений, так и внутри нее.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример решения задачи
Задача. Найти максимальное значение функции F= x2
ограничениях
 x1  6x1 при
2
2 x1  3 x2  24,
 x  2 x  15,
2
 1
3 x1  2 x2  24,
 x  4,
 2
 x1 , x2  0.
Решение.
Так как целевая функция нелинейная, то имеем задачу нелинейного
программирования. Областью допустимых решений данной задачи является
многоугольник ОАВС (рис. 3). Следовательно, для нахождения ее решения
нужно определить такую точку многоугольника ОАВС, в которой функция F
принимает максимальное значение. Построим линию уровня F =
x2  x1  6x1 =с, где с - некоторая постоянная, и исследуем ее поведение при
2
различных значениях с. При каждом значении с получаем параболу, которая
тем выше отдалена от оси Ох1, чем больше значение с (рис. 3). Значит,
функция F принимает максимальное значение в точке касания одной из
парабол с границей многоугольника ОАВС. В данном случае это точка D
(рис.3), в которой линия уровня F =
многоугольника ОАВС.
x2  x1  6x1 =13 касается стороны АВ
2
Рис. 3.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Координаты точки D можно найти из системы уравнений
 x2  x12  6 x1  13,
 x1  3, x2  4.

 x2  4
Итак, Fmax= 13 при Х=(3, 4).
Задачи для самостоятельного решения
В задачах 6.1 –6.5 найти условный экстремум
6.1.Найти максимальное значение функции F= 3x1+4x2 при условиях
 x12  x 22  25,

 x1 x 2  4,
 x , x  0.
 1 2
6.2. Найти максимальное значение функции F=x1x2 при условиях
6 x1  4 x 2  12,
2 x  3x  24,
 1
2

 3x1  4 x 2  12,
 x1, x 2  0.
6.3. Найти минимальное значение функции F=9(x1-5)2+4(x2-6)2при условиях
3x1  2 x 2  12,
 x  x  6,
 1
2

 x 2  4,
 x1, x 2  0.
6.4.Найти максимальное значение функции F=4x1+3 x2 при условиях
 x12  2 x1  x 22  2 x 2  34  0,

 x1  1,
 x  1.
 2
6.5.Найти максимальное значение функции F=x1x2 при условиях
 x12  2 x1  x 22  2 x 2  14  0,

2 x1  x 2  10,
 x , x  0.
 1 2
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Практическая работа № 7. Метод множителей Лагранжа решения ЗНП.
2.2. Метод множителей Лагранжа
Необходимые теоретические сведения
Метод решения задач на условный экстремум Метод множителей Лагранжа
заключается в сведении этих задач к задачам на безусловный экстремум
вспомогательной функции — т. н. функции Лагранжа.
Для задачи об экстремуме функции f (х1, x2,..., xn) при условиях (уравнениях
связи) φi(x1, x2, ..., xn) = 0, i = 1, 2,..., m, функция Лагранжа имеет вид
Множители y1, y2, ..., ym наз. множителями Лагранжа.
Если величины x1, x2, ..., xn, y1, y2, ..., ym суть решения уравнений,
определяющих стационарные точки функции Лагранжа, а именно, для
дифференцируемых функций являются решениями системы уравнений
,
i = 1, …, n;
,
i = 1, …,m,
то при достаточно общих предположениях x1, x2, ..., xn доставляют экстремум
функции f.
Постановка задачи. В задачах 7.1-7.8 найти условный экстремум
f(x1,x2,…,xn)max (min) при ограничениях
gi (x1,x2,…,xn )=bi (i=1,…,m) методом множителей Лагранжа.
Указания к решению
1. Составить функцию Лагранжа
2. Найти частные производные от функции Лагранжа по переменным xj и i
и приравнять их к 0
3. Решить систему уравнений, найти точки, в которых целевая функция
задачи может иметь экстремум
4. Среди точек, подозрительных на экстремум, найти такие, в которых
достигается экстремум, и вычислить значения функции в этих точках
Задачи для самостоятельного решения
7.1.F(x1, x2) =
x12  x22 при ограничении x1+x2=5
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 x1  x 2  4,

7.2.F(x1, x2 ,x3)= x1x2+x2x3 при ограничениях  x 2  x3  4.
7.3.F (x1, x2) = x1x2 при ограничении x1  x 2  1,
7.4.F(x1, x2 ,x3)=x1-2x2+2x3 при ограничении
7.5. F ( x1 , x2 , x3 ) 
x12  x22  x32  1
x12 x23 x34 при ограничении x1+x2+x3=18
 x1  x 2  x3  4,

7.6. F ( x1 , x2 , x3 )  x  x  x3 при ограничениях 2 x1  3 x 2  12.
2
1
2
2
2 x1 x 2  x 2 x3  12,

7.7. F ( x1 , x2 , x3 )  x1 x2 x3 при ограничениях 2 x1  x 2  8.
 x1  x 2  x3  5,

7.8. F(x1, x2 ,x3)= x1x2x3 при ограничениях  x1 x 2  x 2 x3  x1 x3  8.
В задачах 7.9 – 7.13 составить математическую модель и получить решение
графическим способом или методом множителей Лагранжа.
7.9.На развитие предприятий отрасли на планируемый год выделено 220 млн.
руб. Эти средства могут быть распределены между тремя предприятиями.
Каждый вариант распределения обеспечивает к концу года определенный
доход отрасли. Учитывая возможные варианты распределения капитальных
вложений между предприятиями и получаемый при этом доход, определить
такой вариант распределения капиталовложений, при котором доход отрасли
является максимальным
Предпр
иятие
Размер
капиталовложен
ий (млн.руб.)
Доход
(тыс.руб.)
Размер
капиталовложен
ий (млн.руб.)
Доход
(тыс.руб.)
Размер
капиталовл
ожений
(млн.руб.)
Доход
(тыс.руб.)
1
от 10 до 30
14,3
от 30 до 60
16,2
17,2
2
от 10 до 40
13,5
от 40 до 70
17,8
3
от 10 до 50
18,4
от 50 до 60
19,3
60 и
более
70 и
более
60 и
более
44
18,3
19,4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7.10. На двух предприятиях необходимо изготовить 300 изделий некоторой
продукции. Затраты, связанные с производством x1 изделий на 1 предприятии
равны 8x12, а затраты на x2 изделий на 2 предприятии составляют 12x2+4x22.
Определить, сколько изделий на каждом предприятии следует произвести,
чтобы общие затраты, обусловленные изготовлением необходимой продукции,
были минимальными.
7.11.На двух предприятиях необходимо изготовить 100 изделий некоторой
продукции. Затраты, связанные с производством x1 изделий на 1 предприятии
равны 2x12, а затраты на x2изделий на 2 предприятии составляют 10x2+4x22.
Определить, сколько изделий на каждом предприятии следует произвести,
чтобы общие затраты, обусловленные изготовлением необходимой продукции,
были минимальными
7.12.На двух предприятиях необходимо изготовить 200 изделий некоторой
продукции. Затраты, связанные с производством x1 изделий на 1 предприятии
равны 4x12, а затраты на x2 изделий на 2 предприятии составляют 20x2+6x22.
Определить, сколько изделий на каждом предприятии следует произвести,
чтобы общие затраты, обусловленные изготовлением необходимой продукции,
были минимальными
7.13.На двух предприятиях необходимо изготовить 180 изделий некоторой
продукции. Затраты, связанные с производством x1 изделий на 1 предприятии
равны 4x1+x12, а затраты на x2 изделий на 2 предприятии составляют 8x2+x22.
Определить, сколько изделий на каждом предприятии следует произвести,
чтобы общие затраты, обусловленные изготовлением необходимой продукции,
были минимальными
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ТЕМА 3. ЭЛЕМЕНТЫ ТЕОРИИ МАТРИЧНЫХ ИГР
Практическая работа № 8. Матричные игры и их решение.
Необходимые теоретические сведения
Теория игр – это совокупность математических методов анализа и оценки
конфликтных ситуаций.
Содержание теории игр: установление принципов оптимального поведения в
условиях неопределенности (конфликта), доказательство существования
решений, удовлетворяющих этим принципам, указание алгоритмов
нахождения решений, их реализация.
Моделями теории игр можно описать экономические, правовые, классовые,
военные конфликты, взаимодействие человека с природой.
Все такие модели в теории игр принято называть играми.
Игры можно классифицировать по различным признакам: стратегические и
чисто случайные, бескоалиционные и коалиционные, игры 1, 2, …, n лиц (по
числу игроков), конечные и бесконечные (по числу стратегий), игры в
нормальной форме и динамические, с нулевой суммой («антагонистические») и
с ненулевой суммой.
Рассмотрим простейшую модель – игру, в которой участвуют два игрока,
множество стратегий каждого игрока конечно, а выигрыш одного игрока равен
проигрышу другого (бескоалиционная, конечная, антагонистическая игра двух
лиц). Такую игру (Г) называют матричной. Она определяется тройкой
Г=(X,Y,K), где Х – множество стратегий 1-го игрока, Y – множество стратегий
2-го игрока, K=K(x,y) – функция выигрыша (выигрыш 1-го игрока и
соответственно проигрыш 2-го при условии, что 1-й игрок выбрал стратегию
, а 2-й – стратегию
). Пару (x,y) называют ситуацией в игре Г.
Пусть 1-й игрок имеет всего m стратегий, а 2-й – n стратегий: Х=М={1,2, …,
m}, Y=N={1,2, …, n}. Тогда игра Г полностью определяется заданием матрицы
, где aij=K(i,j) – выигрыш 1-го игрока при условии, что он выбрал
стратегию (т.е. строку) i, а 2-й игрок – стратегию (т.е. столбец) j (эти стратегии
называют чистыми).
Матрица А называется матрицей игры или платежной матрицей.
Пример решения задачи
Пусть матрица игры
. Цель каждого игрока – получить как можно
больший выигрыш. Но 1-му игроку нет смысла выбирать стратегию i=1 в надежде
выиграть 5 ед., так как 2-й игрок, действуя разумно, не станет выбирать стратегию
j=2, чтобы не проиграть максимальную сумму 5 ед. Игрокам удобнее выбрать
«осторожные» стратегии.
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пусть
– платежная матрица игры Г. Если 1-й игрок выбрал
стратегию i, то в худшем случае он выиграет
гарантировать себе выигрыш
или максимин, соответствующая
максиминной.
. Поэтому он всегда может
, обозначим его
стратегия 1-го
– нижняя цена игры,
игрока называется
Второй игрок, выбрав стратегию j, в худшем случае проиграет
, а
значит, может гарантировать себе проигрыш
, обозначим его –
верхняя цена игры, или минимакс, соответствующая стратегия 2-го игрока
называется минимаксной.
Схема:
Например,
Соответствующие стратегии: i0=1 (максиминная), j0=1,2 (минимаксная).
Справедливо неравенство:
.
В игре Г естественно считать оптимальной такую ситуацию (i,j), от которой
ни одному из игроков невыгодно отклоняться.
Ситуация (i*,j*) называется ситуацией равновесия, или седловой точкой, если
для любых
,
выполняется неравенство
.
Соответствующие стратегии i*, j* называются оптимальными чистыми
стратегиями 1-го и 2-го игроков, а число
называется ценой игры.
Элемент
является одновременно минимумом в своей строке и
максимумом в своем столбце.
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ситуация равновесия существует тогда и только тогда, когда
значение и является ценой игры v).
(это
Например,
(2,3)-ситуация равновесия, v=4 – цена игры, i*=2, j*=3 – оптимальные стратегии
1-го и 2-го игроков. Выбрав их, 1-й игрок обеспечит себе выигрыш не менее 4
ед., а 2-й игрок проиграет не более 4 ед. при любом выборе другого игрока.
Наряду с чистыми стратегиями игроков рассматривают также смешанные
стратегии.
Смешанной стратегией для 1-го игрока называется упорядоченная система m
действительных чисел x=(x1, x2, …, xm),
,
, которые можно
рассматривать как относительные частоты (вероятности), с которыми 1-й игрок
выбирает чистые стратегии i=1, 2, …, m.
Аналогично определяется смешанная стратегия для 2-го игрока: y=(y1, y2, …,
yn),
,
.
Множества всех смешанных стратегий 1-го и 2-го игроков будем обозначать
соответственно Sm и Sn.
Чистые стратегии можно рассматривать как частный случай смешанных
стратегий. Например, чистую стратегию j=2 можно рассматривать как
смешанную y=(0,1,0,…,0), чистую стратегию i=1 – как смешанную x=(1,0,…,0).
Пару смешанных стратегий (x,y) называют ситуацией в смешанных стратегиях.
Функция выигрыша K(x,y) в ситуации (x,y) определяется как математическое
ожидание выигрыша 1-го игрока при условии, что 1-й и 2-й игроки выбрали
соответственно стратегии x=(x1, x2, …, xm) и y=(y1, y2, …, yn):
.
Если для некоторых
и
и для всех
и
, то x*, y* называются
выполняется неравенство
оптимальными смешанными стратегиями игроков, число
называется ценой игры, пара (x*, y*) – стратегической седловой точкой, а
тройка x*, y*, v – решением игры.
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Основная теорема теории матричных игр, или теорема о минимаксе. Если
– матрица игры Г и для всех
и
,
то величины
и
существуют и равны между
собой (эта величина и является ценой игры v).
Из теоремы следует, что всякая матричная игра имеет цену; игрок в матричной
игре всегда имеет оптимальную стратегию.
Задачи для самостоятельного решения
3.1. Используя геометрическую интерпретацию,
определяемых следующими матрицами
4

2
1) А= 
0

1

6

4
4) А= 
2

1

3

4
5

6 
5

6
7

8 
2) А=
2 3 1 4

4 2 3 1



5) А=
 3 5 1 4 6


 7 4 9 5 3
найти
3

5
3) А=  1

4
6

решение
игр,
9

4
7

5
3 
3.2. Швейное предприятие планирует к массовому выпуску новую модель
одежды. Спрос на эту модель не может быть точно определен. Можно
предположить, что его величина характеризуется тремя возможными
состояниями (1,2,3). С учетом этих состояний анализируются три возможных
варианта выпуска данной модели (А,Б,В). Каждый из этих вариантов требует
своих затрат и обеспечивает в конечном счете различный эффект. Прибыль
(тыс.руб.), которую получает предприятие при данном объеме выпуска модели
и соответствующем состоянии спроса, определяется матрицей
Требуется найти объем выпуска модели
1 2 3
одежды, обеспечивающий среднюю величину
А 22 22 22
прибыли при любом состоянии спроса.
Б 21 23 23
В 20 21 24
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.3. Обувная фабрика планирует выпуск двух моделей обуви А и В. Спрос на
эти модели не определен, но можно предположить, что он может принимать
одно из двух состояний. В зависимости от этих состояний прибыль
предприятия различна и определяется матрицей
 52 22 
 . Найти оптимальное соотношение между объемами выпуска
22
49


А= 
каждой из моделей, при котором предприятию гарантируется средняя величина
прибыли при любом состоянии спроса.
ТЕМА 4. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
Практическая работа № 9. Решение задач динамического
программирования.
Необходимые теоретические сведения
Динамическое программирование — это вычислительный метод для
решения задач определенной структуры. Возникло и сформировалось в 19501953 гг. благодаря работам Р. Беллмана над динамическими задачами
управления запасами. В упрощенной формулировке динамическое
программирование представляет собой направленный последовательный
перебор вариантов, который обязательно приводит к глобальному максимуму.
Основные необходимые свойства задач, к которым возможно применить этот
принцип:
1. Задача должна допускать интерпретацию как n-шаговый процесс
принятия решений.
2. Задача должна быть определена для любого числа шагов и иметь
структуру, не зависящую от их числа.
3. При рассмотрении k-шаговой задачи должно быть задано некоторое
множество параметров, описывающих состояние системы, от которых
зависят оптимальные значения переменных. Причем это множество не
должно изменяться при увеличении числа шагов.
4. Выбор решения (управления) на k-м шаге не должен оказывать
влияния на предыдущие решения, кроме необходимого пересчета
переменных.
Задача о выборе траектории, задача последовательного принятия решения,
задача об использовании рабочей силы, задача управления запасами —
классические задачи динамического программирования.
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Постановка задачи динамического программирования.
Постановку задачи динамического программирования рассмотрим на примере
инвестирования, связанного с распределением средств между предприятиями.
В результате управления инвестициями система последовательно переводится
из начального состояния S0 В конечное Sn. Предположим, что управление
можно разбить на n шагов и решение принимается последовательно на каждом
шаге, а управление представляет собой совокупность n пошаговых управлений.
На каждом шаге необходимо определить два типа переменных - переменную
состояния системы Sk переменную управления xk . Переменная Sk определяет, в
каких состояниях может оказаться система на рассматриваемом k-м шаге. В
зависимости от состояния S на этом шаге можно применить некоторые
управления, которые характеризуются переменной xk которые удовлетворяют
определенным ограничениям и называются допустимыми. Допустим. Х= (x1 ,
x2 , ..., xk , ..., xn ) - управление, переводящее систему на состояния S0 в
состояние Sn , a Sk - есть состояние системы на k-м шаге управления. Тогда
последовательность состояний системы можно представить в виде графа,
представленного на рис. 4.
x1
S0
x2
xn
S1
Sn-1
Sn
Рис. 4
Применение управляющего воздействия xk на каждом шаге переводит систему
в новое состояние S1 (S, xk) и приносит некоторый результат Wk (S, xk). Для
каждого возможного состояния на каждом шаге среди всех возможных
управлений выбирается оптимальное управление x*k , такое, чтобы результат,
который достигается за шаги с k-го по последний n-й, оказался бы
оптимальным. Числовая характеристика этого результата называется функцией
Беллмана Fk (S) и зависит от номера шага k и состояния системы S. Задача
динамического программирования формулируется следующим образом:
требуется определить такое управление, переводящее систему из начального
состояния S0 в конечное состояние Sn , при котором целевая функция
принимает наибольшее (наименьшее) значение.
Особенности математической модели динамического программирования
1. Задача оптимизации формулируется как конечный многошаговый
процесс управления;
2. Целевая функция (выигрыш) является аддитивной и равна сумме
целевых функций каждого шага:
F   Fk ( S k 1 , xk )  extr
k 1
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.
4.
5.
6.
Выбор управления xk на каждом шаге зависит только от состояния
системы k этому шагу Sk-1, и не влияет на предшествующие шаги (нет
обратной связи);
Состояние системы Sk после каждого шага управления зависит только
от предшествующего состояния системы Sk-1 и этого управляющего
воздействия xh (отсутствие последействия) и может быть записано в
виде уравнения состояния: Sk = fk(Sk-1 , xk), k = 1, n;
На каждом шаге управление xk зависит от конечного числа
управляющих переменных, а состояние системы зависит Sk – от
конечного числа параметров;
Оптимальное управление представляет собой вектор
,
определяемый
последовательностью
оптимальных
пошаговых
управлений: = (x*1 , x*2 , ..., x*k , ..., x*n ), число которых и определяет
количество шагов задачи.
Задачи для самостоятельного решения
9.1.Для увеличения объемов выпуска пользующейся повышенным спросом
продукции, изготовляемой предприятиями, выделены капиталовложения в
объеме S тыс руб Использование i – ым предприятием Хi тыс руб. из
указанных средств обеспечивает прирост выпуска продукции, определяемый
значением нелинейной функции fi(Хi)
а) Найти распределение капиталовложений между предприятиями,
обеспечивающее максимальное увеличение выпуска продукции, если S= 100
тыс.руб., n= 4, а значения Xi и fi(Xi) приведены в таблице.
Объем
капиталовложений
Xi (тыс.руб)
0
20
40
60
80
100
Прирост выпуска продукции fi(Xi) в зависимости от объема
капиталовложений (тыс.руб.)
предприятие
предприятие
предприятие
предприятие
1
2
3
4
0
12
33
44
64
78
0
14
28
38
56
80
0
13
38
47
62
79
0
18
39
48
65
82
Б) Найти распределение капиталовложений между предприятиями,
обеспечивающее максимальное увеличение выпуска продукции, если S= 7000
тыс.руб., n= 3, а значения Xi и fi(Xi) приведены в таблице.
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Объем
капиталовложен
ий Xi (тыс.руб)
0
100
200
300
400
500
600
700
Прирост выпуска продукции fi(Xi) в зависимости от объема
капиталовложений (тыс.руб.)
предприятие 1
предприятие 2
предприятие 3
0
0
0
30
50
40
50
80
50
90
90
110
110
150
120
170
190
180
180
210
220
210
220
240
9.2.В определенный момент времени на предприятии установлено новое
оборудование. Зависимость производительности этого оборудования от
времени его использования предприятием, а также зависимость затрат на
содержание и ремонт оборудования при различном времени его использования
приведены в таблице
Время t, в течение которого используется
оборудование (лет)
0
1
2
3
4
5
80
75
65
60
60
55
Годовой выпуск продукции
R(t)
в
стоимостном
выражении (тыс.руб.)
Ежегодные затраты Z(t),
20
25
30
35
45
55
связанные с содержанием и
ремонтом
оборудования
(тыс. руб.)
Зная, что затраты, связанные с приобретением и установкой нового
оборудования, идентичного с установленным, составляют 40 тыс.руб., а
заменяемое оборудование списывается. Составить такой план замены
оборудования в течение 5 лет, при котором общая прибыль за данный период
времени максимальна.
9.3. Сырье, запас которого равен С единицам, требуется распределить для
выпуска N видов изделий таким образом, чтобы максимизировать общую
прибыль от продажи этих изделий. При этом пусть на изготовление ut единиц
изделий вида t расходуется ft(ut) единиц сырья, а прибыль от продажи ut
единиц изделий вида t составляет Ft(ut) денежных единиц.
f1(u1) =u1, f2(u2)= 2u2, f3(u3)=3u3.
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=4, F3(2)=6; ui <=2, i=1,2,3; c=6
F1(u1)=2u1, F2(u2)=3u2,
F3(0)=0, F3(1)=4, F3(2)=5; ui <=2, i=1,2,3; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=5, F3(2)=8; ui <=2, i=1,2,3; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=2, F3(2)= F3(3)= 5; ui <=3, i=1,2,3; c=5
F1(u1)=2u1, F2(u2)=4u2
F3(0)=0, F3(1)=F3(2)=6; u1 <=3, u2 <=3, u3 <=2; c=6
F1(u1)=2u1, F2(u2)=4u2
F3(0)=0, F3(1)=F3(2)=5.5; u1 <=3, u2 <=3 u3 <=2; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=5, F3(2)=7; ui <=2, i=1,2,3; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1) = F3(2)=6; ui <=2, i=1,2,3; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=3, F3(2)=5; u1 <=3, u2 <=2 u3 <=2; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=4, F3(2)=6; u1 <=2, u2 <=2 u3 <=2; c=6
F1(u1)=2u1, F2(u2)=3u2
F3(0)=0, F3(1)=4, F3(2)=5; u1 <=2, u2 <=3 u3 <=2; c=6
Используемая литература
1.
2.
3.
4.
5.
Акулич И.Л. Математическое программирование в примерах и
задачах: Учеб.пособие.-2-е изд.,испр., и доп..-М.:Высш.шк.,1993.-336
с.:ил.
Замогильнова
Л.В.
Сборник задач
по математическому
программированию.- Шуя, Издательство «Весть» ГОУ ВПО
«ШГПУ», 2005.-42 с.
Кузнецов Ю.Н., Кузубов В.И., Волощенко А.В. Математическое
программирование: Учеб.пособие.-2-е изд.,перераб. и доп. –
М.:Высш.школа,1980.-360 с.
Методические указания к проведению лабораторных работ по
линейному программированию. - Иваново, ИвГУ, 1994.-40 с.
Шамсутдинова Т. М. Задачи линейного программирования//
ИНФО,№8,2002.-с32-39.
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приложение 1
Решение ЗЛП с помощью табличного процессора Excel
Пусть требуется решить следующую задачу линейного программирования
F(x)=3x1-2x2+x3+2x4
x1-x2+3x3+2x4  6,
2x1+x2-x3+4x4  4
xj  0

 min при ограничениях
При решении поставленной задачи в Excel используется надстройка
«Поиск решения». Перед ее использованием необходимо предварительно
ввести на рабочий лист электронной таблицы Excel известные исходные
данные.
Возможный вид исходных данных представлен на рис.1. Блок ячеек
В1:В4 содержит начальный план, в данном случае произвольно взятый набор
(0, 0, 0, 0); ячейка В5 – оптимизируемую (целевую) функцию; блоки А9:А10 и
С9:С10 служат для выражения ограничений, накладываемых на значения
аргументов целевой функции. Остальные ячейки используются для хранения
текста поясняющего характера.
Рис.1. Фрагмент рабочего листа Excel с исходными данными в режиме
просмотра формул
Для задания параметров поиска решения необходимо вызвать
диалоговое окно Поиск решения (рис.2) с помощью команды Сервис, Поиск
решения. В окне Поиск решения следует задать целевую ячейку В5,
содержащую оптимизируемую функцию, вид оптимизации – минимальное
значение, диапазон ячеек, содержащих варьируемые параметры В1:В4 и
ограничения на целевую функцию.
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 2. Установки окна Поиск решения
Для ввода ограничений в окно Поиск решения служит его кнопка
Добавить, позволяющая вызвать диалоговое окно Добавление ограничения
(рис.3).
Рис.3. Окно Добавление ограничения
В данном случае для решения поставленной задачи следует указать
следующие ограничения:
$А$9<=$C$9
$A$10<=$C$10
$B$1:$B4>=0
Найденный в результате выполнения поиска решения оптимальный план
() представлен в диапазоне ячеек В1:В4 на рис.4. При этом целевая функция
приняла значение ; были выполнены все заданные условиями задачи
ограничения.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис.4. Фрагмент рабочего листа Excel с полученными в результате
поиска решения данными
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Приложение 2
Решение транспортной задачи в Excel
Постановка задачи. Имеется n городов. Выехав из одного из них,
коммивояжер должен объехать все и вернуться в исходный город. В каждый
город можно заезжать только один раз, и, следовательно, маршрут
коммивояжера должен образовывать замкнутый цикл без петель (например,
если есть 6 город 1, 2, 3, 4, 5, 6, то 1 - 4 – 2 – 1 и 3 – 5 – 6 – 3 – подциклы
(петли)). Требуется найти кратчайший замкнутый маршрут коммивояжера,
если известна матрица расстояний между городами.
Математическая модель рассматриваемой задачи имеет вид:
F(x)=
n
n
n
i 1
j 1
 c x
ij
ij 
min;
(1)
x
 1i, j=1, 2, ..., n;
(2)
x
 1i, i=1, 2, ..., n;
(3)
ij
i 1
n
ij
j 1
ui  uj  nxij  n  1 , i, j=1, 2, ..., n, i  j; (4)
xij=0 либо 1, i, j=1, 2, ..., n, i  j;
(5)
Здесь переменная xij принимает значение 1, если коммивояжер
переезжает из города i в город j (i, j=1, 2, ..., n, i  j) и 0 в противном случае.
Условие (1) представляет собой оптимизируемую функцию, где с ij – расстояния
между городами (i, j=1, 2, ..., n, i  j), причем в общем случае сij  cji; условие
(2) означает, что коммивояжер выезжает из каждого города только один раз; (3)
– что он въезжает в каждый город только один раз; (4) обеспечивает
замкнутость маршрута и отсутствие петель, где ui и uj – некоторые
вещественные значения (i, j=1, 2, ..., n, i  j).
Пример.
Имеется 6 пунктов. Коммивояжер должен посетить их по одному разу и
вернуться в исходный город. Найти кратчайший маршрут. Расстояния между
городами заданы в виде матрицы чисел:
27
43
16
30
26
7
16
1
30
25
20
13
35
5
0
21
16
25
18
18
12
46
27
48
5
23
5
5
9
5
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для решения поставленной задачи следует разместить на рабочем листе
электронных таблиц Excel заданные исходные данные. Один из возможных
вариантов представлен на рис. 5.
Рис.5. Фрагмент окна Excel с исходными данными для расчетов
Здесь диапазон ячеек В2:G7 содержит исходную матрицу расстояний
между городами, в которой расстояния от города до самого себя приняты
достаточно большими по сравнению с другими расстояниями (например, 1000).
Данный прием замены нулевых расстояний на бесконечные используется в
классическом методе «ветвей и границ» решения задач данного типа с целью
заранее исключить из решения нулевые по расстоянию переходы, которые хотя
и являются наикратчайшими, но недопустимы по смыслу задачи.
Диапазон ячеек B9:G14 содержит начальный (нулевой) план решения
задачи; в ячейках B15:G15 и H9:H14 находятся формулы расчета количества
въездов и выездов из городов (рис.6); в ячейке D23 – искомая целевая функция,
использующая вспомогательные промежуточные расчеты блока D17:D22
(рис.7).
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис.6. Фрагмент окна Excel с формулами расчета количества въездов и
выездов
Рис.7. Фрагмент окна Excel с промежуточными расчетами и целевой
функцией
Для решения данной задачи надо в окне Поиск решения (рис.8) задать
адрес ячейки, содержащей целевую функцию (в данном случае D23), вид
оптимизации (минимальное значение), изменяемые ячейки (B9:G14) и
налагаемые на решение ограничения. Ограничения B15:G15=1 и Н9:Н14=1
соответствуют условиям (2) и (3) поставленной краевой задачи,
В9:Н14=двоичное – условию (5).
Рис.8. Установки окна Поиск решения для транспортной задачи
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Найденный в результате поиска решения план представлен на рис.9.
Рис.9. План, найденный в результате поиска решения
Полученное решение нуждается в дальнейшем анализе на предмет
наличия в нем подциклов (петель). В случае выявления в найденном решении
петель должны быть откорректированы ограничения, накладываемые на
параметры поиска (в частности, добавлены ограничения, аналогичные условию
(4).
Как видно из данного рисунка, в качестве решения задачи предлагается
множество переходов (x14, x21, x35, x42, x56, x63) (ячейки E9, B10, F11, C12, G13,
D14). Таким образом, решение в неупорядоченном виде сводится к переходам
из первого в четвертый город, из второго в первый, из третьего в пятый, из
четвертого во второй, из пятого в шестой и из шестого в третий. При
упорядочении данного решения получаем, что в качестве оптимального плана
решения рассматриваемой задачи найдены две цепочки переходов: 1 – 4 – 2 – 1
и 3 – 5 – 6 – 3, т.е. полученное решение не удовлетворяет условиям задачи
ввиду наличия в нем петель.
Проведем корректировку налагаемых на целевую функцию условий за
счет введения дополнительного ограничения, исключающего наличие в
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
оптимальном плане найденных петель 1 – 4 – 2 – 1 и 3 – 5 – 6 – 3. Так как
найденный план (x14, x21, x35, x42, x56, x63) предполагает равенство
E9+B10+F11+C12+G13+D14=6, то достаточно добавить к имеющимся
ограничениям условие С25<=5 (рис. 10), записав в ячейку С25 формулу
=E9+B10+F11+C12+G13+D14.
Рис.10. Добавление ограничения для исключения петель
После добавления нового ограничения следует провести повторный
поиск решения.
Найденный план (x14, x21, x35, x43, x56, x62 ) представлен на рис.11. Этот
план задает переход 1 – 4 – 3 – 5 – 6 – 2 – 1, не содержащий петель и,
соответственно, удовлетворяющий всем условиям (1) – (5) задачи.
Рис. 11. План без петель, найденный в результате поиска решения
62
Документ
Категория
Без категории
Просмотров
78
Размер файла
1 522 Кб
Теги
1498, операция, исследование
1/--страниц
Пожаловаться на содержимое документа