Линейное программирование. Практикум

ШЕВЧЕНКО А.С.

ЛИНЕЙНОЕ 

ПРОГРАММИРОВАНИЕ

ПРАКТИКУМ

Учебное пособие

Москва

ИНФРА-М

2018

УДК 004.42(075.32)
ББК 32.973я723

Ш37

Шевченко А.С.

Ш37
Линейное 
программирование. 
Практикум
: 
учеб.

пособие / А.С. Шевченко. — М. : ИНФРА-М, 2018. — 295 с.

ISBN 978-5-16-107341-4 (online)
Учебное пособие содержит практические и тестовые задания по 

основным темам раздела «Линейное программирование». Задания и 
тесты могут быть использованы для самостоятельной подготовки к 
экзамену, так и для проверки знаний студентов в ходе учебного процесса. Также в пособии представлены решения задач линейного программирования с использованием САПР Mathcad Prime.

Пособие предназначено для студентов среднего профессиональ
ного образования.

УДК 004.42(075.32)

ББК 32.973я723

ISBN 978-5-16-107341-4 (online)
© Шевченко А.С., 2018

ФЗ № 
436-ФЗ

Издание не подлежит маркировке 
в соответствии с п. 1 ч. 2 ст. 1

СОДЕРЖАНИЕ

ПРЕДИСЛОВИЕ .......................................................................................5
ТЕМА 1: ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ 
ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ .............................7

Тест
................................................................................................... 20

ТЕМА 2: ОБЩАЯ ЗАДАЧА ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ......................................................................27

2.1
Переход от произвольной формы ЗЛП к канонической форме
................................................................................................... 27

2.2
Переход от канонической формы ЗЛП к симметричной 

форме ................................................................................................... 29
Тест
................................................................................................... 33

ТЕМА 3: МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ......................................................................41

3.1
Графический 
метод 
решения 
задач 
линейного 

программирования ............................................................................... 41

3.1.1
Графический метод решение ЗЛП с двумя переменными
........................................................................................... 41

3.1.2
Графическое решение ЗЛП, записанных в канонической 

форме при условии, что n−m=2 ...................................................... 49
Тест
........................................................................................... 56

3.2
Симплекс-метод 
решения 
задач 
линейного 

программирования ............................................................................... 63

Тест
........................................................................................... 74

ТЕМА 4: ТЕОРИЯ ДВОЙСТВЕННОСТИ .........................................80

4.1.
Правила составления двойственных задач............................ 80

4.2.
Нахождение решения двойственных задач........................... 86

Тест
................................................................................................... 99

ТЕМА 5: ТРАНСПОРТНАЯ ЗАДАЧА ..............................................109

5.1.
Нахождение первоначального опорного решения ..............109

5.2.
Метод потенциалов ................................................................117

Тест
..................................................................................................128

ТЕМА 6: ЗАДАЧА О НАЗНАЧЕНИЯХ ............................................139

Тест
..................................................................................................147

ТЕМА 7: ЗАДАЧА ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ....................................................................151

7.1.
Графическое решение задачи целочисленного линейного 

программирования ..............................................................................151
7.2.
Метод отсечения. Метод Гомори.........................................153

Тест
..................................................................................................159

ТЕМА 8: РЕШЕНИЕ ЗАДАЧ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ В САПР MATHCAD PRIME ...............165

8.1 Введение в САПР MATHCAD PRIME........................................165

8.2 Решение задач линейного программирования ...........................174

ОТВЕТЫ.................................................................................................192

На задания............................................................................................192
На тесты ...............................................................................................203

ЛИТЕРАТУРА .......................................................................................206

ПРЕДИСЛОВИЕ

Учебное пособие предназначено для студентов среднего про
фессионального образования, обучающихся по специальностям «Информационные системы по отраслям», «Земельно-имущественные отношения».

В данном пособии все задания и тесты сгруппированы по темам: 

«Построение математических моделей задач линейного программирования», «Общая задача линейного программирования», «Графический 
метод решения задач линейного программирования», «Симплексный 
метод решения задач линейного программирования», «Двойственный 
задачи линейного программирования», «Транспортная задача линейного программирования», «Задача о назначениях», «Задачи целочисленного линейного программирования», «Решение задач линейного 
программирования с использованием САПР Mathcad Prime».

Более того, в пособии показано как можно решать задачи ли
нейного программирования с использованием системы автоматизированного проектирования Mathcad Prime.

В результате успешного выполнения практических заданий и 

тестов по линейному программированию студент должен 

знать:
−
основные понятия теории линейного программирования 

(ЛП);

−
постановку задач ЛП, примеры экономических задач;

−
методы ЛП, применяемые для решения прикладных эконо
мических задач; 

−
понятие двойственности в ЛП, теоремы двойственности;

−
алгоритмы решения транспортных задач (ТЗ) и задач о 

назначениях;

−
алгоритм Гомори для решения задач целочисленного про
граммирования;

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

−
решать типовые оптимизационные задачи и производить

оценку качества полученных решений;

−
решать задачи ЛП графическим и симплексным методами;

−
решать ТЗ методом потенциалов;

−
решать задачи о назначениях венгерским методом;

−
решать целочисленные задачи ЛП методом Гомори;

−
осуществлять переход от одной формы записи задачи ЛП к 

другой;

владеть: 
− навыками системного анализа содержания математического 

материала на основе изученного теоретического материала;

− навыками поиска информации, необходимой для ответа на 

поставленные вопросы;

− навыками практической работы по решению оптимизацион
ных задач.

− навыками решения задач линейного программирования с ис
пользованием САПР Mathcad Prime.

ТЕМА 1: ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ 

ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Задание. Составьте математические модели задач 1.1 – 1.30.
1.1. Некоторая организация выпускает два вида продукции. 

Прибыль от реализации единицы продукции 
1P составляет 4 д.е., а от 

единицы продукции 
2P – 5 д.е. Вся необходимая информация (данные 

о запасах и количестве ресурсов, которые необходимы для изготовления единицы продукции) содержится в таблице 1.1. Необходимо определить такой план производства продукции, чтобы прибыль от ее реализации была максимальной.

Таблица 1.1 – Исходные данные

Виды 

ресурсов

Запасы 
ресурсов

Число единиц ресурса,

которые затрачиваются на изготов
ление единицы продукции

1P
2P

1S
30
2
5

2
S
28
3
3

3
S
17
2

4
S
33
5

Решение: Введем обозначения. Пусть:

1x – количество производимой продукции
1P ,

2x – количество производимой продукции
2P ,

Т.о., математическая модель данной задачи будет иметь сле
дующий вид:



1
2
1
2
,
4
5
max,
Z x x
x
x




1
2

1
2

2

1

1
2

2
5
30,

3
3
28,

          2
17,

       5
33,

0,
0.

x
x

x
x

x

x

x
x


















■

1.2. Стоимость 1 кг корма вида I – 6 рубля, а вида II – 8 рублей. 

Используя данные таблицы 1.2, необходимо составить такой рацион 
питания, чтобы стоимость его была минимальной и содержание каждого вида питательных веществ было не менее установленного предела.

Таблица 1.2 – Исходные данные

Виды питатель
ных веществ

Необходимый ми
нимум питательных 

веществ

Число единиц питательного вещества в 

1кг корма
I
II

1S
31
5
2

2
S
30
6
3

3
S
34
7
4

Решение: Введем обозначения. 
Пусть:

1x – количество потребления корма вида I,

2x – количество потребления корма вида II,

Математическая модель данной задачи будет иметь следую
щий вид:

1
2
1
2
( ,
)
6
8
min
Z x x
x
x



,

1
2

1
2

1
2

1
2

5
2
31,

6
3
30,

7
4
34,

0,
0.

x
x

x
x

x
x

x
x
















■

1.3. Винный завод производит две марки сухого вина: «Хорошее 

настроение» и «Букет алых роз». Оптовые цены, по которым реализуется готовая продукция, соответственно 350 и 300 рублей за литр. Для 
изготовления этих вин необходимы ингредиенты (белое, розовое и 
красное сухие вина), которые закупаются в Грузии. Стоимость этих
вин составляет соответственно 360, 250 и 150 рублей за литр. На винный завод ежедневно поставляется 3000 литров белого, 4500 литров
розового и 2200 литров красного вина.

Вино «Хорошее настроение» должно содержать не менее 50% 

белого вина и не более 30% красного. Вино «Букет алых роз» должно 
содержать не более 60% красного и не менее 25% белого.

Необходимо определить оптимальный рецепты смешения ин

гредиентов для производства вин «Хорошее настроение» и «Букет 
алых роз», обеспечивающие заводу максимальную прибыль.

Решение: Введем обозначения. 
Пусть 
ijx
– количество j-го ингредиента (j = 1, 2, 3), который 

входит в i-ю смесь (i = 1, 2).

Составим целевую функцию:















11
12
13
21
22
23
11
12
13

21
22
23

(
,
,
,
,
,
)
350
360
350
250
350 150

                              
300
360
300
250
300 150
max.

Z x
x
x
x
x
x
x
x
x

x
x
x

















Ограничения на поставки ингредиентов:

11
21

12
22

31
23

3000,
4500,
2200.

x
x

x
x

x
x










Ограничения, которые отражают условия на содержание ингре
диентов в смеси:













11
11
12
13

13
11
12
13

13
21
22
23

13
21
22
23

0.5
,

0.3
,

0.6
,

0.25
.

x
x
x
x

x
x
x
x

x
x
x
x

x
x
x
x

















А также, необходимо учесть условие на неотрицательность пе
ременных:

0,
1,2, 
1,3.
ijx
i
j




■

1.4. Фирма Mars производит ежедневно не менее 950 кг пище
вой добавки – смеси овсяной и черемуховой муки. Состав смеси представлен в таблице 1.3. Диетологи требуют, чтобы в пищевой добавке 
было не менее 42% белка и не более 17% клетчатки. 

Таблица 1.3 – Исходные данные

Мука
Белок
Клетчатка
Стоимость
(в руб. за кг)
(в кг на кг муки)

Овсяная
0.08
0.03
40

Черемуховая
0.5
0.07
80

Необходимо определить такую рецептуру смеси, которая бы 

имела минимальную стоимость и учитывала требования диетологов.

Решение: Введем обозначения. 
Пусть:

1x – количество (в кг.) овсяной муки, 

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

Математическая модель следующая:










1
2
1
2

1
2

1
2
1
2

1
2
1
2

1
2

,
40
80
min,

950,

0.08
0.5
0.42
,

0.03
0.07
0.17
,

0, 
0.

F x x
x
x

x
x

x
x
x
x

x
x
x
x

x
x























■

1.5. Имеются две шахты, которые обеспечивают углём три элек
тростанции. Известны расстояния от каждой шахты до каждой электростанции, запасы угля на каждой шахте, а также потребности в угле 
каждой электростанции. Вся необходимая информация содержится в 
таблице 1.4. 

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

Таблица 1.4 – Исходные данные

Количество угля на 

шахтах, 
тыс. т

Потребности в угле электростанциями, 

тыс. т

170
110
160

120
30
40
0

11
x
12
x
13
x

320

20
50
15

21
x
22
x
23
x

Решение: Введём обозначения. 
Пусть:
0 (
1,2; 
1,3) 
ijx
i
j



– количество угля, которое плани
руется перевозить от i-ой шахты до j-ой электростанции.

Данная транспортная задачи является закрытой, т. к. объём ре
сурсов равен объёму потребностей: 120+320=170+110+160.

Математическая модель данной задачи будет иметь следую
щий вид:

11
12
13
21
22
23
11
12
13
21
22
23
(
,
,
,
,
,
)
30
40
0
20
50
15
min
Z x
x
x
x
x
x
x
x
x
x
x
x







,

11
12
13

21
22
23

120,

320,

x
x
x

x
x
x











11
21

12
22

13
23

170,

110,

160,

x
x

x
x

x
x















0, 
1,2, 
1,3 .
ijx
i
j




■

1.6. Из партии листовой стали необходимо нарезать четыре вида 

различных заготовок в количестве 240, 200, 120, 140 штук. Лист стали 
может быть раскроен четырьмя способами. В таблице 1.5. содержится 
необходимая информация: выход заготовок в штуках разных видов 

, 
1,4, 
1,4
ija
i
j


, площадь отходов 
,  
1,4
jс
j 
при раскрое одного 

листа стали по j-му способу раскроя. 

Какое количество листов стали необходимо раскроить тем или 

иным способом, чтобы отходы были минимальными?

Таблица 1.5 – Исходные данные

Виды 

заготовок

План-задание по количеству заготовок 

(
ib )

Выход заготовок (шт.) разных 

видов из карт раскроя (
ij
a )

1
2
3
4

1
240
1
4
0
1

2
200
1
0
4
0

3
120
1
0
0
3

4
140
1
1
0
3

Площадь отходов, 
2
м
(
jс )
1.4
0.1
2.1
0.1

Решение: Введем обозначение. 
Пусть:
,  
1,4
jx
j 
– количество листов стали, которые необхо
димо раскроить по одному из способов j. 

Математическая модель данной задачи будет иметь следую
щий вид:



1
2
3
4
1
2
3
4
,
,
,
1.4
0.1
2.1
0.1
min,
Z x x x x
x
x
x
x










1
2
3
4

1
2
3
4

1
2
3
4

1
2
3
4

4
0
240,

0
4
0
200,

0
0
3
120,

0
3
140,

x
x
x
x

x
x
x
x

x
x
x
x

x
x
x
x
























1
2
3
4
0,
0,
0,
0
x
x
x
x




.

■

1.7. На распил поступает 190 бревен длиной 6 м. Необходимо 

изготовить брусья длиной 1.2 м, 3 м и 5 м в соотношении 2:1:3.

Определите такой план распила бревен, чтобы обеспечить мак
симальное число комплектов.

Решение: Определим все возможные способы распила бревен, 

указав соответствующее число получающихся при этом брусьев и 
остаток (см. таблица 1.6).

Таблица 1.6 – Исходные данные
Способ 

распила бревен

Число получающихся брусьев
Остаток
1.2 м
3 м
5 м

1
5
0
0
0

2
2
1
0
0.6

3
0
2
0
0

4
0
0
1
1

Введем обозначение. Пусть 
ix – число бревен распиливаемых i
м способом, 
1,4
i 
, х – число комплектов брусьев.

Математическая модель задачи будет иметь следующий вид:

1
2
3
4
( ,
,
,
,
)
max,
Z x x x x x
x



1
2
3
4

1
2

2
3

4

190,

         5
2
2 ,

        
2
,

                  
3 ,

x
x
x
x

x
x
x

x
x
x

x
x

















0, 
1,4
ix
i


.

■

1.8. Завод может производить за месяц 325 моторов типа А или 846 

моторов типа В. Определите, сколько моторов каждого типа нужно производить заводу, чтобы достичь максимум товарной продукции, если 
известно, что спрос на моторы типа В превышает в три раза спрос на моторы типа А?

1.9. Фирма «Мир мебели» производит три вида изделия А, В, С,

на изготовление которых используется три различных вида материала. 
Каждый вид материала может быть использован в количестве не 
большем 24, 35, 43 ус.ед., соответственно. Вся необходимая информация представлена в таблице 1.7. 

Необходимо определить план производства изделий, при кото
ром достигается максимальная прибыль фирмы.

Таблица 1.7 – Исходные данные

Виды 

материала

Нормы расхода материалов на одно 

изделие
Запас материала
А
В
С

I
5
5
3
24

II
3
6
–
35

III
–
8
2
43

Цена одного 
изделия, д.е.
100
200
300

1.10. Предприятие имеет четыре производственных цеха, кото
рые изготавливают два вида изделий. Вся необходимая информация
приведена в таблице 1.8. Прибыль от продажи единицы первого изделия составляет 15 д.е., а от единицы второго изделия – 18 д.е. Определите план производства изделий, обеспечивающий предприятию максимальную прибыль.

Таблица 1.8 – Исходные данные

Цеха

Нормы времени на изготов
ление единицы изделий
Производственные
мощности цехов, час
I
II

1
4
4
23

2
3
5
18

3
6
0
26

4
0
7
32

1.11. Небольшая фирма изготавливает два вида продукции А и 

В. Объем сбыта продукции вида А составляет не менее 70% общего 
объема реализации продукции обоих видов. Для изготовления продукции А и В используется одно и то же сырье, суточный запас которого 
ограничен величиной 200 единиц. Расход сырья на единицу продукции 
А составляет 5 ед., а на единицу продукции В – 7 ед. Цены на продукцию А и В составляют 35 и 46 д.е., соответственно. Определите оптимальный план изготовления продукции А и В. 

1.12. Предприятие выпускает детали двух видов: А, В. Для этого 

Предприятие использует литье, которое подвергается токарной обработке, сверлению и шлифованию. Производительность станочного 
парка предприятия по обработке деталей А и В приведена в таблице 1.9.