Файл: Практикум Челябинск 2019.pdf

22
Ресурсы
Норма затрат ресурсов на 1 кг блюда
1 2
3 4
Затраты труда на производство, чел.- час.
3,8 5
3,6 2,6
Затраты труда на доставку, чел.-час.
2,1 2,2 2,15 2,8
Накладные расходы, руб.
8,4 8,5 6,4 10
Товарооборот, руб.
55 67 53 52
Доход, руб.
20,5 20 15,4 25,8
Вариант 15
Косметическая фирма выпускает три типа румян – жидкие, перламутровые и матовые
– с использованием одинаковых смесеобразующих машин и видов работ. Главному бухгалтеру фирмы было поручено разработать для компании план производства на неделю.
Информация о ценах продаж и стоимости 100 л товара, приведена в таблице (евро).
Издержки производства товаров на 100 л
Румяна
Жидкие
Перламутровые
Матовые
Стоимость сырья
12,95 29,44 17,66
Стоимость трудозатрат
35,32 42,39 28,26
Стоимость приготовления смеси
37,68 23,55 42,39
Другие издержки
14,13 17,66 11,77
Цена продажи за 100 л
141,29 148,35 129,52
Стоимость 1 чел.-ч составляет 3,53 евро, а стоимость 1 ч приготовления смеси – 4,71 евро. Фонд рабочего времени ограничен 8000 чел.-ч в неделю, а ограничение на фонд работы смесеобразующих машин 5900 ч в неделю.
В соответствии с контрактными соглашениями компания должна производить 25000 л матовых румян в неделю, не более 35000 л жидких румян и не более 29000 л перламутровых румян в неделю.
Определите объемы производства румян в неделю, при которых достигается максимальное значение получаемой за неделю прибыли.
Вариант 16
Бумажная фабрика обладает запасами сухого сырья и наполнителя для производства пяти типов бумаги. Размеры запасов каждой группы сырья, нормативы его расходов на каждый тип бумаги и прибыль от реализации
1 т каждого типа бумаги заданы в таблице.
Определить размеры годовой выработки каждого типа бумаги, обеспечивающие максимальную общую прибыль от ее реализации при условии, что планом предусмотрен обязательный выпуск не менее, чем
8000 т газетной бумаги и 3000 т обойной бумаги.

23
Тип сырья
Тип бумаги
Запасы, тыс. т
Типографская Газетная Обойная Пачечная Оберточная
Целлюлоза 0,335 0,28 0,27 0,16 0,22 24
Древесная масса
0,61 0,8 0,65 0,77 0,75 44
Макулатура
0,13 0,07 0,09 0,4
Каолин
0,75 0,09 0,12 0,08 15
Прибыль за
1 т, руб.
25,4 218,2 175,5 315 255
1.2. Графический метод решения задач линейного
программирования с помощью программы Microsoft Office Excel
КРАТКАЯ СПРАВКА
Графический метод основан на геометрической интерпретации задачи линейного программирования и применяется для решения задачи с двумя переменными, заданными в неканонической форме, и многими переменными в канонической форме при условии, что они содержат не более двух свободных переменных.
C геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Каждое из неравенств системы ограничений задачи определяет полуплоскость соответственно с граничными прямыми:
a
i1
x
1
+ a
i2
x
2
= b
i
(i = 1,…, m); х
1
= 0; х
2
= 0.
Множество точек пересечения данных полуплоскостей

выпуклое.
Областью допустимых решений является выпуклое множество, которое называется многоугольником решений.
Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы заменой знаков неравенства знаками равенства.
В общем случае областью допустимых решений системы неравенств может быть: выпуклый многоугольник; выпуклая многоугольная неограниченная область; луч; отрезок; единственная точка или пустая область. В последнем случае говорят, что ограничения не совместны.

24
Для построения данной области необходимо начертить граничные прямые по уравнениям системы ограничений, в которых неравенства заменяются равенствами. Воспользуемся возможностями программы MS
Office Excel.
На одной диаграмме следует построить 5 графиков линейных функций
(рис. 1.2.1):
   
,
f
,
x
f
,
x
,
,
,
f
,
x
,
,
,
f
350 1
1 1
100 8
0 4
0 8
0 365 5
0 8
0 5
0 400 4
1 3
1 2
1 1









где в качестве зависимой переменной f с соответствующим индексом используется вторая переменная данной задачи (x
2
).
В качестве пятой функции следует использовать целевую линейную функцию (1.5), задав начальное максимальное значение, например, равным нулю:
1 5
14 16 14 0
x
f


Рис. 1.2.1. Экранная форма в режиме просмотра формул
Для построения графиков необходимо воспользоваться мастером диаграмм (Вставка / Точечная) (рис. 1.2.2).
Рис. 1.2.2. Вставка / Точечная

25
Результат построения графиков показан на рисунке 1.2.3.
Рис. 1.2.3. Результат построения графиков функций ограничений и целевой функции
Для того, чтобы определить, какая полуплоскость удовлетворяет неравенству, выбираем любую точку, не принадлежащую прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат.
Подставим координаты точки (0;0) в неравенство (1) системы ограничений (1.4):
400 0
400 0
5 0
0 8
0






,
,
, так как координаты точки (0;0) удовлетворяют этому неравенству, то решением неравенства является полуплоскость, содержащая точку (0;0), т.е. полуплоскость, расположенная ниже прямой (f
1
).
Подставим координаты точки (0;0) в неравенство (2) системы ограничений (1.4):
365 0
365 0
8 0
0 4
0






,
,
, так как координаты точки (0;0) удовлетворяют этому неравенству, то решением неравенства является полуплоскость, содержащая точку (0;0), т.е. полуплоскость, расположенная ниже прямой (f
2
).
Подставим координаты точки (0;0) в неравенство (3) системы ограничений (1.4):
100 0
100 0
1 0
1






, так как координаты точки (0;0) удовлетворяют этому неравенству, то решением неравенства является полуплоскость, содержащая точку (0;0), т.е. полуплоскость, расположенная выше прямой (f
3
).

26
Подставим координаты точки (0;0) в неравенство (4) системы ограничений (1.4):
350 0
350 0
1




, так как координаты точки (0;0) удовлетворяют этому неравенству, то решением неравенства является полуплоскость, содержащая точку (0;0), т.е. полуплоскость, расположенная ниже прямой (f
4
).
Рассмотрим неравенства: х
1

0 и х
2

0 (неотрицательные значения переменных х
1
и х
2
). Они определяют первый квадрант плоскости x
1
0x
2
Таким образом, OABDEF

область допустимых решений (рис. 1.2.4).
Рис. 1.2.4. Область допустимых решений
На рисунке 1.2.4. показана линия нулевого уровня L
0
, которая задается уравнением
0 14 16 2
1


x
x
(прямая f
5
, проходящая через начало координат).
Целевая функция F(X) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение F. Задача определения максимума функции F(X) сводится к нахождению в допустимой области точки, через которую проходит прямая из семейства F = const, и которая соответствует наибольшему значению F.
Для нахождения оптимального значения целевой функции F(X) необходимо линию нулевого уровня L
0
передвигать параллельно самой себе в направлении вектора 0М (координаты точки М = (16; 14)) до точки ее последней встречи с вершиной многоугольника

OABDEF, которая и является точкой экстремума.
Оптимальный план задачи – точка D, которая, является пересечением двух прямых f
1
и f
2
(рис. 1.2.5).

27
Рис. 1.2.5. Оптимальный план задачи – точка D
Для нахождения количественных значений переменных, обеспечивающих максимальное значение целевой функции, воспользуемся встроенным инструментом анализа программы MS Office Excel, который называется Подбор параметра.
Для этого (рис. 1.2.6.):

выделим ячейки под значения переменных x
1
, x
2
(в нашем примере
B23:C23);

в ячейку C23 введем формулу для вычисления x
2
(
1 2
5 0
8 0
5 0
400
x
,
,
,
x


):
=$F$8/$C$8-$B$8/$C$8*B23;

в ячейку В24 введем формулу


1 1
8 0
4 0
8 0
365 5
0 8
0 5
0 400
x
,
,
,
x
,
,
,




, которая соответствует разности первых двух ограничений:
=F8/C8-B8/C8*B23-(F9/C9-B9/C9*B23);

в ячейку В25 введем формулу, которая необходима для расчета оптимального значения целевой функции:
=B4*B23+C4*C23;

выполним команду Данные / Анализ «что-если» / Подбор параметра…
В результате выполнения этой команды откроется диалоговое окно
Подбор параметра.
В поле Установить в ячейке: следует ввести адрес ячейки B24, в которой содержится формула разности первых двух ограничений.
В поле Значение: следует ввести 0.
В поле Изменяя значение ячейки: следует ввести адрес ячейки, которая будет содержать искомое значение (рис. 1.2.7). ОК.

28
Рис. 1.2.6. Дополнительные данные для нахождения оптимального решения
Рис. 1.2.7. Данные / Анализ «что-если» / Подбор параметра
В результате этого будут найдены оптимальные значения переменных исходной задачи и соответствующее им максимальное значение целевой функции (рис. 1.2.8): x
1
= 312,5; x
2
= 300; F(X) = 9200.
Анализ полученных результатов решения задачи двумя методами (с использованием надстройки Поиск решения и графическим) показывает их полное совпадение.
Рис. 1.2.8. Результат решения задачи

29
Варианты заданий для самостоятельной работы
Найти графическим методом решение следующих задач линейного программирования.
Вариант 1
F(X)=4x
1
+3x
2

max,
x
1
+2x
2

4,
2x
1
-x
2

9,
5x
1
+3x
2

32,
4x
1
+7x
2

27,
x
1
, x
2

0.
Вариант 2
F(X)=3,5x
1

3x
2

max,
x
1

4x
2

4,
3x
1
+2x
2

6,

x
1
+x
2

1,
x
1
+2x
2

3,
x
1
, x
2

0.
Вариант 3
F(X)=3x
1
+4x
2

max,

2x
1
+4x
2

1,
4x
1
+6x
2

12,
6x
1
+3x
2

9,
2x
1
+x
2

1,6,
2x
1

4x
2

2,
x
1
, x
2

0.
Вариант 4
F(X)=1,4x
1
+2x
2

max,
x
1
+x
2

4,
4x
1
+2x
2

4,
2,3x
1
+5x
2

4,
x
1

3,
x
2

3,
x
1
, x
2

0.
Вариант 5
F(X)=1,2x
1
+x
2

max,

4,6x
1
+x
2

1,
9,78x
1

3x
2

6,
2x
1
+x
2

8,

x
1
+x
2

7,
2x
1
+2x
2

2,
x
1
, x
2

0.
Вариант 6
F(X)=2,54x
1
+1,78x
2

max,
6,7x
1

x
2

4,
4,4x
1
+2x
2

3,
3x
1

x
2

6,
8x
1
+1,5x
2

7,
x
1
, x
2

0.
Вариант 7
F(X)=x
1
+x
2

max,

4x
1
+x
2

2,5,
2x
1

3x
2

3,89,
2x
1
+x
2

8,7,
6x
1

4x
2

4,56,
x
1
, x
2

0.
Вариант 8
F(X)=7x
1
+7,5x
2

max,
2x
1
+0,25x
2

10,
0,5x
1
+2x
2

10,
x
1

6,8,
x
2

5,
x
1
, x
2

0
Вариант 9
F(X)=x
1
+5x
2

min,
1,5x
1

2x
2

2,5,

2x
1

3x
2


4,

2x
1
+x
2

2,
x
1
, x
2

0.
Вариант 10 F(X)=3x
1
+x
2

max,

1,6 x
1
+x
2

1,9,
2,2x
1
+3x
2

15,

2x
1
+x
2

4,
x
1
, x
2

0.
Вариант 11 F(X)=2,7x
1

3,6x
2

min,
3x
1
+ 2x
2
≥ 4,
x
1
– 0,5x
2
≤ 2,
x
1
+2,5x
2

5,
x
1
, x
2

0.
Вариант 12 F(X)=

2,3x
1

x
2

min,
2x
1
+ 4x
2

15,

4x
1
+2x
2

8,
x
1
+ 3x
2

9,
6x
1
+ 5x
2
=30, x
1
, x
2

0.

30
Вариант 13 F(X)=5x
1

4x
2

min,
3x
1
+ 2x
2
≥ 6,
2x
1

3x
2
≥

4,
x
1
– x
2

3,
4x
1
+ 7x
2
=14,
x
1
, x
2

0.
Вариант 14 F(X)=5x
1
+x
2

min,
x
1
+ 7x
2
≥ 19,
5x
1
+2x
2
≥ 10,

2x
1
+x
2

4,
7x
1
+ x
2
≥ 7,
2x
1
+5x
2
≥ 17,
2x
1

2,
x
2

7,
x
1
, x
2

0.
Вариант 15 F(X)=5x
1
+3x
2

max,
2x
1
+ 2x
2
≥ 6,
2x
1
– 2x
2
≥

6,
x
1
+2x
2

4,
4x
1
+3 x
2
=12,
x
1
, x
2

0.
Вариант 16 F(X)=3,45x
1
+4,8x
2

max,
x
1
+ 2x
2
≤ 4,

2x
1

2x
2

2,
2x
1
+4x
2
≥ 8,
x
1
+ 2x
2
≤ 6,
4x
1

2x
2
≤ 4,
x
1
, x
2

0.
1.3. Двойственная задача линейного программирования
КРАТКАЯ СПРАВКА
Произвольную задачу линейного программирования можно определенным образом сопоставить с другой задачей линейного программирования, называемой двойственной (или сопряженной).
Первоначальная задача является исходной.
Исходная и двойственная задачи тесно связаны между собой и образуют единую двойственную пару.
Для исходной задачи, представленной в симметричной форме записи (1.2), где b
i
(i=1…m) обозначает запас ресурса S
i
; a
ij
– число единиц ресурса S
i
, потребляемого при производстве единицы продукции P
j
(j=1…n); c
j
– прибыль
(выручка) от реализации единицы продукции P
j
(или цена продукции P
j
), алгоритм составления математической модели двойственной задачи будет следующий:
1. Каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную y
i
.
2. Составляем целевую функцию, коэффициентами которой являются свободные члены системы ограничений исходной задачи.
3. Составляем систему ограничений, коэффициенты системы ограничений образуют транспонированную матрицу коэффициентов системы ограничений исходной задачи.
4. Знаки неравенств меняются на противоположные.
5. Свободными членами системы ограничений являются коэффициенты целевой функции исходной задачи.
6. Все переменные двойственной задачи неотрицательные.
7. Если исходная задача была на максимум, то двойственная становится задачей на минимум, и наоборот: