Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План
чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2.Линейное программирование.
Тема № 2.1. Виды задач линейного программирования.
Занятие №
Учебные и воспитательные цели: изучить основные виды задач линейного программирования, их математические модели.
Время
Место проведения: аудитория.
Учебные вопросы: Задача линейного программирования (ЗЛП). Трудности решения ЗЛП. Классификация задач оптимизации: задача о пищевом рационе, задача о планировании производства, задача о загрузке оборудования, задача о снабжении сырьем.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
| №п/п |
Учебные вопросы |
Время, мин |
Методические указания |
1.
2.
3.
|
Задача линейного программирования (ЗЛП).
Трудности решения ЗЛП.
Классификация задач оптимизации.
|
1. Вводная часть. Организационный момент. План занятия. Основные требования.
2. Основная часть.
1. Задача линейного программирования (ЗЛП).
Термин линейное программирование
появился в Америке в середине 40-х годов (первая американская работа по частной задаче линейного программирования опубликована в 1941 г.). В Советском Союзе исследования в этой области начались ранее. В конце 30-х годов целый ряд существенных результатов по линейному программированию был установлен Л.В. Канторовичем.
Задача линейного программирования – это задача нахождения значений параметров, обеспечивающих экстремум функции при наличии ограничений на аргументы.
Задачи линейного программирования являются самыми простыми и лучше изученными задачами. Для них характерно: показатель эффективности (целевая функция) выражается линейной зависимостью; ограничения на решения – линейные равенства или неравенства.
2. Трудности решения ЗЛП.
Трудности решения задач линейного программирования зависят от: вида зависимости, связывающей целевую функцию с элементами решения; размерности задачи, то есть от количества элементов решения х1, х2,…, xn; вида и количества ограничений на элементы решений.
3. Классификация задач оптимизации.
Задача о рациональном питании (задача о пищевом рационе).
ПОСТАНОВКА ЗАДАЧИ. Ферма производит откорм скота с коммерческой целью. Для простоты допустим, что имеется всего четыре вида продуктов: П1
, П2
, П3
, П4
; стоимость единицы каждого продукта равна соответственно С1
, С2
, С3
, С4
. Из этих продуктов требуется составить пищевой рацион, который должен содержать: белков – не менее b
i
единиц; углеводов – не менее b
2
единиц; жиров – не менее b
3
единиц. Для продуктов П1
, П2
, П3
, П4
содержание белков, углеводов и жиров (в единицах на единицу продукта) известно и задано в таблице, где a
ij
(i=1,2,3,4; j=1,2,3) – какие – то определённые числа; первый индекс указывает номер продукта, второй – номер элемента (белки, углеводы, жиры).
| продукт |
элементы |
| белки |
углеводы |
жиры |
П1
П2
П3
П4
|
A11
A21
A31
A41
|
A12
A22
A32
A42
|
A13
A23
A33
A43
|
Требуется составить такой пищевой рацион (т.е. назначить количества продуктов П1
, П2
, П3
, П4
, входящих в него), чтобы условия по белкам, углеводам и жирам были выполнены и при этом стоимость рациона была минимальна.
МАТЕМАТИЧЕСКУЮ МОДЕЛЬ. Обозначим x
1
, x
2
, x
3
, x
4
количества продуктов П1
, П2
, П3
, П4
, входящих в рацион. Показатель эффективности, который требуется минимизировать, - стоимость рациона (обозначим её L): она линейно зависит от элементов решения x
1
, x
2
, x
3
, x
4
.
Целевая функция:  
Система ограничений:
a
11
x
1
+a
21
x
2
+a
31
x
3
+a
41
x
4
≥b
1
a
12
x
1
+a
22
x
2
+a
32
x
3
+a
42
x
4
≥b
2
a
13
x
1
+a
23
x
2
+a
32
x
3
+a
43
x
4
≥b
3
Эти линейные неравенства представляют собой ограничения, накладываемые на элементы решения x
1
, x
2
, x
3
, x
4
.
Таким образом, поставленная задача сводится к следующей: найти такие неотрицательные значения переменных
x
1
,
x
2
,
x
3
,
x
4
, чтобы они удовлетворяли ограничениям – неравенствам и одновременно обращали в минимум линейную функцию этих переменных:
Задача о планировании производства.
ПОСТАНОВКА ЗАДАЧИ. Предприятие производит изделия трёх видов: U1
, U2
, U3
. По каждому виду изделия предприятию спущен план, по которому оно обязано выпустить не мене b
1
единиц изделия U1
, не мене b
2
единиц изделия U2
и не мене b
3
единиц изделия U3
. План может быть перевыполнен, но в определённых границах; условия спроса ограничивают количества произведённых единиц каждого типа: не более соответственно b
1
, b
2
, b
3
единиц. На изготовление изделий идёт какое-то сырьё; всего имеется четыре вида сырья: s
1
, s
2
, s
3
, s
4
, причём запасы ограничены числами g
1
, g
2
, g
3
, g
4
единиц каждого вида сырья. Теперь надо узнать какое количество сырья каждого вида идёт на изготовление каждого вида изделий. Обозначим a
ij
количество единиц сырья вида s
i
(I= 1, 2, 3, 4), потребное на изготовление одной единицы изделия Uj
(j= 1, 2, 3). Первый индекс у числа a
ij
– вид изделия, второй – вид сырья. Значения a
ij
сведены в таблицу (матрицу).
Сырьё
|
Изделия
|
| U1
|
U2
|
U3
|
S1
S2
S3
S4
|
a11
a12
a13
a14
|
a21
a22
a23
a24
|
a31
a32
a33
a34
|
При реализации одно изделие U1
приносит предприятию прибыль c
1
, U2
– прибыль c
2
, U3
– прибыль c
3
. Требуется так спланировать производство (сколько каких изделий производить), чтобы план был выполнен или перевыполнен (но при отсутствии «затоваривания»), а суммарная прибыль обращалась в максимум.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Элементами решения будут x
1
, x
2
, x
3
– количества единиц изделий U1
, U2
, U3
, которые мы произведём. Обязательность выполнения планового задания запишется в виде трёх ограничений – неравенств: x
1
³b
1
, x
2
³b
2
, x
3
³b
3
.
Отсутствие изделий продукции (затоваривания) даёт нам ещё три ограничения – неравенства: x
1
£b
1
, x
2
£b
2
, x
3
£b
3
.
Целевая функция: L=c
1
x
1
+c
2
x
2
+c
3
x
3
→ max.
Система ограничений:
a
11
x
1
+a
21
x
2
+a
31
x
3
£¡
1
.
a
12
x
1
+a
22
x
2
+a
32
x
3
£¡
2
.
a
13
x
1
+a
23
x
2
+a
33
x
3
£¡
3
.
a
14
x
1
+a
24
x
2
+a
34
x
3
£¡
4
.
Задача о загрузки оборудования.
ПОСТАНОВКА ЗАДАЧИ. Ткацкая фабрика располагает двумя видами станков, из них N1 станков типа 1 и N2 станков типа 2. Станки могут производить три вида тканей: T1, T2, T3, но с разной производительностью. Данные a
ij
производительности станков в таблице (первый индекс – тип станка, второй – вид ткани).
Каждый метр ткани вида T1 приносит фабрике доход c
1
, вида Т2 – доход с
2
, Т3 – доход с
3
.
| Тип станка |
Вид ткани |
| Т1 |
Т2 |
Т3 |
1
2
|
а11
а21
|
а12
а22
|
а13
а23
|
Фабрике предписан план согласно которому она должна производить в месяц не менее b
1
метров ткани Т1, b
2
метров ткани Т2, b
3
метров ткани Т3; количество метров каждого вида ткани не должно превышать соответственно b
1
, b
2
, b
3
метров. Кроме того, все без исключения станки должны быть загружены. Требуется так распределить загрузку станков производством тканей Т1, Т2, Т3, чтобы суммарный месячный доход был максимален.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Введём букву x с двумя индексами (первый – тип станка, второй – вид ткани). Всего будет шесть элементов решения: x
11
x
12
x
13
x
21
x
22
x
23
.
Здесь x
11
– количество станков типа 1, занятых изготовлением ткани Т1, x
12
– количество станков типа 1, занятых изготовлением ткани Т2 и т.д.
Запишем суммарный доход от производства всех видов тканей. Суммарное количество метров ткани Т1, произведённое всеми станками, будет равно a11
x11
+a21
x21
и принесёт доход c1
(a11
x11
+a21
x21
).
Целеваяфункция: L=c
1
(a
11
x
11
+a
21
x
21
)+c
2
(a
12
x
12
+a
22
x
22
)+c
3
(a
13
x
13
+a
23
x
23
)  → max.
Система ограничений:
Обеспечим выполнения плана ограничениями по минимальным параметрам:
a
11
x
11
+a
21
x
21
³b
1
,
a
12
x
12
+a
22
x
22
³b
2
,
a
13
x
13
+a
23
x
23
³b
3
,
После этого ограничим выполнение плана по максимальным параметрам:
a
11
x
11
+a
21
x
21
£b
1
,
a
12
x
12
+a
22
x
22
£b
2
,
a
13
x
13
+a
23
x
23
£b
3
,
Теперь запишем ограничения, связанные с наличием оборудования и его полной загрузкой. Суммарное количество станков типа 1, занятых изготовлением всех тканей, должно быть равно N1; типа 2 – N2.
x
11
+x
12
+x
13
=N1,
x
21
+x
22
+x
23
=N2,
Задача о снабжении сырьём.
ПОСТАНОВКА ЗАДАЧИ. Имеется три промышленных предприятия: П1
, П2
, П3
, требующих снабжения определённым видом сырья. Потребности в сырье каждого предприятия равны соответственно a
1
, a
2
, a
3
единиц. Имеются пять сырьевых баз, расположенных от предприятий на каких – то расстояниях и связанных с ними путями сообщения с разными тарифами. Единица сырья, получаемая предприятием Пi
c базы Бj
,
обходится предприятию в с
ij
рублей (первый индекс – номер предприятия, второй – номер базы).
| Предприятия |
Базы |
| Б1
|
Б2
|
Б3
|
Б4
|
Б5
|
П1
П2
П3
|
С11
С21
С31
|
С12
С22
С32
|
С13
С23
С33
|
С14
С24
С34
|
С15
С25
С35
|
Возможности снабжения сырьём с каждой базы ограничены её производственной мощностью: базы Б1
, Б2
, Б3
, Б4
, Б5
могут дать не более b
1
, b
2
, b
3
, b
4
, b
5
единиц сырья. Требуется составить такой план снабжения предприятий сырьём (с какой базы, куда и какое количество сырья везти), чтобы потребности предприятий были обеспечены при минимальных расходах на сырьё.
МАТЕМАТИЧЕСКАЯ МОДЕЛЬ. Обозначим x
ij
количества сырья с j – ой базы. Всего план будет состоять из 15 элементов решения: x
11
x
12
x
13
x
14
x
15
x
21
x
22
x
23
x
24
x
25
x31
x
32
x
33
x
34
x
35.
Целевая функция:
Система ограничений:
x
11
+x
12
+x
13
+x
14
+x
15
=a
1
,
x
21
+x
22
+x
23
+x
24
+x
25
=a
2
,
x
31
+x
32
+x
33
+x
34
+x
35
=a
3
,
x
11
+x
21
+x
31
£b
1
,
x
12
+x
22
+x
32
£b
2
,
x
13
+x
23
+x
33
£b
3
, (4.3.)
x
14
+x
24
+x
34
£b
4
,
x
15
+x
25
+x
35
£b
5
,
|
