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

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Лабораторный практикум

Москва

Издательство «ФЛИНТА»

2018

УДК 004.9
ББК  32.97

И88

И88 
Исследование операций [Электронный ресурс] : лабораторный 

практикум / Ю.А. Леонов, Е.А. Леонов, Л.Б. Филиппова, Р.А. Филиппов. —
М. : ФЛИНТА, 2018. — 94 с.

ISBN 978-5-9765-4016-3

Содержатся 
восемь 
лабораторных 
работ 
по 
дисциплине 

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

Лабораторный практикум предназначен для студентов очной 

формы обучения по специальности 10.05.04 – «Информационноаналитические системы безопасности» и направлениям подготовки: 
09.03.02 – «Информационные системы и технологии», 27.03.05 –
«Инноватика».

УДК 004.9
ББК  32.97

ISBN 978-5-9765-4016-3
© Коллектив авторов, 2018
© Издательство «ФЛИНТА», 2018

ПРЕДИСЛОВИЕ

Лабораторный 
практикум 
состоит 
из 
восьми
работ
по 

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

Лабораторные работы способствуют более глубокому изучению

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

Лабораторный практикум предназначен для студентов очной 

формы обучения по специальности 10.05.04 – «Информационноаналитические системы безопасности» и направлениям подготовки: 
09.03.02 – «Информационные системы и технологии», 27.03.05 –
«Инноватика».

ЛАБОРАТОРНАЯ РАБОТА №1

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

ГРАФИЧЕСКИМ МЕТОДОМ

Цель работы

Цель лабораторной работы –
приобретение практических 

навыков решения задач линейного программирования графическим 
методом.

Продолжительность лабораторной работы – 3 ч.

Общие сведения

Введение в линейное программирование

Линейное программирование – это математическая дисциплина, 

которая рассматривает методы решения экстремальных задач на 
множествах
n-мерного
векторного 
пространства, 
задаваемых 

системами линейных уравнений и неравенств.

Исследование свойств общей системы линейных неравенств 

ведется с XIX в., а первая оптимизационная задача с линейной целевой 
функцией и линейными ограничениями была сформулирована в ЗО-е 
годы XX в. Одним из первых зарубежных ученых, заложивших основы 
линейного программирования, является Джон фон Нейман, широко 
известный математик и физик, доказавший основную теорему о 
матричных играх. Среди отечественных ученых большой вклад в 
теорию линейной оптимизации внесли лауреат Нобелевской премии 
Л.В. Канторович, Н.Н Моисеев, Е.Г. Гольштейн, Д.Б. Юдин и многие 
другие. 

Линейное программирование традиционно считается одним из 

разделов 
исследования 
операций, 
который 
изучает 
методы 

нахождения условного экстремума функций многих переменных. 

В классическом математическом анализе исследуется общая 

постановка задачи определения условного экстремума, однако в связи 
с 
развитием 
промышленного 
производства, 
транспорта, 

агропромышленного комплекса, банковского сектора традиционных 
результатов 
математического 
анализа
оказалось 
недостаточно. 

Потребности практики и развитие вычислительной техники привели к 
необходимости определения оптимальных решений при анализе 

сложных экономических систем. Главным инструментом для решения 
таких 
задач 
является 
математическое 
моделирование, 
т.е. 

формализованное описание изучаемого процесса и исследование его с 
помощью математического аппарата. 

Искусство математического моделирования состоит в том, чтобы 

учесть, как можно более широкий спектр факторов, влияющих на 
поведение объекта, используя при этом по возможности несложные 
соотношения. Именно в связи с этим процесс моделирования часто 
носит многоэтапный характер. Сначала строится относительно 
простая модель, затем проводится ее исследование, позволяющее 
понять, какие из интегрирующих свойств объекта не улавливаются 
данной формальной схемой, после чего за счет усложнения модели 
обеспечивается большая ее адекватность реальности. При этом во 
многих случаях первым приближением к действительности является 
модель, 
в 
которой 
все 
зависимости 
между 
переменными, 

характеризующими 
состояние 
объекта, 
являются 
линейными. 

Практика показывает, что значительное количество экономических 
процессов достаточно полно описывается линейными моделями, а,
следовательно, 
линейное 
программирование 
как 
аппарат, 

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

Постановка задачи линейного программирования

Общей (стандартной) задачей линейного программирования 

называется задача нахождения минимума линейной целевой функции 
(линейной формы) вида:

𝑓(𝑥) = ∑ 𝑐𝑗𝑥𝑗 = 𝑐1𝑥1 + 𝑐2𝑥2+. . . +𝑐𝑛𝑥𝑛

𝑛

𝑗=1

(1)

Задача, в которой фигурируют ограничения в форме неравенств, 

называется основной задачей линейного программирования (ОЗЛП)

∑ 𝑎𝑖𝑗𝑥𝑗 ≥ 𝑏𝑖   (𝑖 = 1, 2, … , 𝑛)

𝑛

𝑗=1

𝑥𝑗 ≥ 0  (𝑗 = 1, 2, … , 𝑛)

(2)

Задача линейного программирования будет иметь канонический 

вид, если в основной задаче вместо первой системы неравенств имеет 
место система уравнений с ограничениями в форме равенства:

∑
𝑎𝑖𝑗𝑥𝑗 = 𝑏𝑖

𝑛
𝑗=1
(i = 1, 2, … , m).
(3)

Основную задачу можно свести к канонической путём введения 

дополнительных переменных.

Задачи линейного программирования наиболее общего вида 

(задачи 
со 
смешанными 
ограничениями: 
равенствами 
и 

неравенствами, наличием переменных, свободных от ограничений) 
могут быть приведены к эквивалентным (имеющим то же множество 
решений) заменами переменных и заменой равенств на пару 
неравенств.

Легко заметить, что задачу нахождения максимума можно 

заменить задачей нахождения минимума, взяв коэффициенты с 
обратным знаком.

Пример выполнения задачи

Предприятие располагает запасами сырья трех видов s1, s2, s3 в 

количествах b1, b2, b3. Из этого сырья может быть изготовлено два вида 
изделий P1, P2.

Дано: aij – количество единиц si-го вида сырья, идущего на 

изготовление единицы Pj-го вида изделия, cj – доход, получаемый от 
реализации одной единицы каждого вида изделия (табл. 1).

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

котором доход предприятия от реализации всей продукции был 
максимальным.

Таблица 1

Исходные данные

Вид сырья 

(si)

Запас 

сырья (bi)

Расход сырья на изделие

(aij)

P1
P2

s1
36
4
9

s2
11
2
1

s3
5
1
0

Для построения математической модели введем следующие 

обозначения: x1 – количество единиц изделий вида P1, x2 – количество 
единиц изделий вида P2, которые может выпускать предприятие.

Исходя из условия задачи, составим систему линейных 

ограничений:

{

4𝑥1 + 9𝑥2 ≤ 36
2𝑥1 + 𝑥2 ≤ 11

𝑥1 ≤ 5

𝑥1 ≥ 0, 𝑥2 ≥ 0.

Условия неотрицательности для переменных x1 и x2 установлены 

исходя из физического смысла.

Целевая функция для данной задачи имеет вид:

𝐹 = 3𝑥1 + 4𝑥2.

Построим графики линейных ограничений и целевой функции 

(рис. 1).

Из графика видно, что оптимальным решение является точка C, 

которая образована пересечением двух прямых:

4𝑥1 + 9𝑥2 = 36
2𝑥1 + 𝑥2 = 11.

С помощью метода Крамера найдем совместное решение двух 

уравнений (точку пересечения С).

∆= |4
9

2
1| = −14,
∆1= |36
9

11
1| = −63,
∆2= |4
36

2
11| = −28;

𝑥1 = 63

14 = 4 1

2 ,
𝑥2 = 28

14 = 2 .

Следовательно:

𝑋опт = (4 1

2 , 2).

Рис. 1. Графическое решение задачи

Индивидуальные задания

Для выполнения лабораторной работы необходимо решить 

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

Выполнение задания можно разделить на следующие этапы:
1. Составить систему линейных ограничений и определить 

целевую функцию (табл. 2).

2. С помощью программного инструментария (Excel, Mathcad и 

т.п.) построить графики линейных функций и показать графически 
область допустимых решений.

3. Построить график целевой функции и нормали к ней.

4. Выделить графически оптимальное решение.
5. Найти 
значение 
оптимального 
решения. 
Для 
этого 

необходимо решить систему уравнений двух линейных функций, 
образующих оптимальное решение.

6. Составить отчет, в котором необходимо указать основные 

этапы работы. Помимо освещения этапов работы указать: цель работы, 
исходные данные, скриншоты графиков функций, заключение и 
список литературы.

Таблица 2

Вариант
Задание
Вариант
Задание

1

𝐹 = 7𝑥1 + 6𝑥2 → 𝑚𝑎𝑥;

2𝑥1 + 5𝑥2 ≥ 10,
5𝑥1 + 2𝑥2 ≥ 10,

𝑥1 ≤ 6,
𝑥2 ≤ 5,

𝑥1, 𝑥2 ≥ 0.

2

𝐹 = 𝑥1 + 𝑥2 → 𝑚𝑖𝑛;

3𝑥1 + 𝑥2 ≥ 8,
𝑥1 + 2𝑥2 ≥ 6,
𝑥1 − 𝑥2 ≤ 3,
𝑥1, 𝑥2 ≥ 0.

3

𝐹 = 3𝑥1 − 2𝑥2 → 𝑚𝑎𝑥;

2𝑥1 + 𝑥2 ≤ 11,

−3𝑥1 + 2𝑥2 ≥ 10,
3𝑥1 + 3𝑥2 ≥ 20,

𝑥1, 𝑥2 ≥ 0.

4

𝐹 = 𝑥1 + 3𝑥2 → 𝑚𝑎𝑥;

−𝑥1 + 𝑥2 ≤ 3,
4𝑥1 + 3𝑥2 ≤ 20,

𝑥1, 𝑥2 ≥ 0.

5

𝐹 = 5𝑥1 − 3𝑥2 → 𝑚𝑖𝑛;

3𝑥1 − 2𝑥2 ≥ 6,
2𝑥1 + 3𝑥2 ≥ −6,

𝑥1 − 𝑥2 ≤ 4,

4𝑥1 + 7𝑥2 ≤ 28,

𝑥1, 𝑥2 ≥ 0.

6

𝐹 = 2𝑥1 + 𝑥2 → 𝑚𝑎𝑥;

𝑥1 − 𝑥2 ≥ 4,
𝑥1 + 𝑥2 ≥ 10,
4𝑥1 − 𝑥2 ≤ 12,
7𝑥1 + 𝑥2 ≤ 7,

𝑥1, 𝑥2 ≥ 0.

7

𝐹 = 𝑥1 + 2𝑥2 → 𝑚𝑎𝑥;

−3𝑥1 + 2𝑥2 ≤ 11,
3𝑥1 + 4𝑥2 ≤ 10,
2𝑥1 + 𝑥2 ≤ 14,

𝑥1, 𝑥2 ≥ 0.

8

𝐹 = 2𝑥1 + 2𝑥2 → 𝑚𝑎𝑥;

3𝑥1 − 2𝑥2 ≥ −6,

𝑥1 + 𝑥2 ≥ 3,

𝑥1 ≤ 3,
𝑥2 ≤ 5,

𝑥1, 𝑥2 ≥ 0.

Продолжение табл. 2

Вариант
Задание
Вариант
Задание

9

𝐹 = 7𝑥1 − 2𝑥2 → 𝑚𝑎𝑥;

5𝑥1 − 2𝑥2 ≤ 3,

𝑥1 + 𝑥2 ≥ 1,

−3𝑥1 + 𝑥2 ≤ 3,
2𝑥1 + 𝑥2 ≤ 4,

𝑥1, 𝑥2 ≥ 0.

10

𝐹 = 2𝑥1 − 4𝑥2 → 𝑚𝑎𝑥;

8𝑥1 − 5𝑥2 ≤ 16,
𝑥1 + 3𝑥2 ≥ 2,
2𝑥1 + 7𝑥2 ≤ 9

𝑥1, 𝑥2 ≥ 0.

,

11

𝐹 = 2𝑥1 + 𝑥2 → 𝑚𝑎𝑥;

𝑥1 − 2𝑥2 ≤ 4,

5𝑥1 + 2𝑥2 ≥ 10,
4𝑥1 − 3𝑥2 ≤ 12,
7𝑥1 + 4𝑥2 ≤ 28,

𝑥1, 𝑥2 ≥ 0.

12

𝐹 = −3𝑥1 + 6𝑥2 → 𝑚𝑖𝑛;

5𝑥1 − 2𝑥2 ≤ 4,
𝑥1 − 2𝑥2 ≥ −4,

𝑥1 + 𝑥2 ≥ 4,
𝑥1, 𝑥2 ≥ 0.

13

𝐹 = 2𝑥1 + 2𝑥2 → 𝑚𝑎𝑥;

3𝑥1 − 2𝑥2 ≥ −6,

𝑥1 + 𝑥2 ≥ 3,

𝑥1 ≤ 3,
𝑥2 ≤ 5,

𝑥1, 𝑥2 ≥ 0.

14

𝐹 = 3𝑥1 + 3𝑥2 → 𝑚𝑎𝑥;

𝑥1 + 𝑥2 ≤ 8,

3𝑥1 + 7𝑥2 ≤ 21,

𝑥1 + 2𝑥2 ≥ 6,
0 ≤ 𝑥1 ≤ 1,
0 ≤ 𝑥2 ≤ 1.

15

𝐹 = 2𝑥1 − 4𝑥2 → 𝑚𝑎𝑥;

8𝑥1 − 5𝑥2 ≤ 16,
𝑥1 + 3𝑥2 ≥ 2,
2𝑥1 + 7𝑥2 ≤ 9

𝑥1, 𝑥2 ≥ 0.

,
16

𝐹 = 𝑥1 + 𝑥2 → 𝑚𝑎𝑥;

𝑥1 + 𝑥2 ≥ 1,

−5𝑥1 + 𝑥2 ≤ 0,
−𝑥1 + 5𝑥2 ≥ 0,

𝑥1 + 𝑥2 ≤ 6,

𝑥1, 𝑥2 ≥ 0.

17

𝐹 = 𝑥1 + 2𝑥2 → 𝑚𝑎𝑥;

5𝑥1 − 2𝑥2 ≤ 4,
𝑥1 − 2𝑥2 ≥ −4,

𝑥1 + 𝑥2 ≥ 4,
𝑥1, 𝑥2 ≥ 0.

18

𝐹 = 𝑥1 + 𝑥2 → 𝑚𝑎𝑥;

5𝑥1 − 2𝑥2 ≤ 7,
−𝑥1 + 𝑥2 ≤ 5,
𝑥1 + 𝑥2 ≤ 6,
𝑥1, 𝑥2 ≥ 0.