Принятие управленческих решений на основе линейного программирования

 

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

В задаче линейного программирования требуется найти экстремум (максимум или минимум) линейной целевой функции f(X):

f(X) = c₁x₁ + c₂x₂ + … + c_nx_n ® max (min)

при ограничениях (условиях):

 

 

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n {£, =, ³} b₁;

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n {£, =, ³} b₂;

……………………………………………

a_m1x₁ + a_m2x₂ + … + a_mnx_n {£, =, ³} b_m;

x_j ³ 0; j = 1, n,

где x_j – управляющие переменные (решения задачи); a_j, b_j, c_j – заданные постоянные величины. Ограничения определяют область допустимых решений. В указанной системе уравнений общее число неизвестных N = n + m, где n – число основных неизвестных x_j; m – число уравнений.

· Если число неизвестных N меньше числа уравнений m, то система решения не имеет и является несовместной.

· Линейная система, в которой число неизвестных N равно числу уравнений m, имеет одно решение.

· Если в системе число неизвестных N больше числа уравнений m, то такая система имеет бесчисленное множество решений.

Системы уравнений из n неизвестных удобно решать с использованием элементов теории матриц, в частности метода Крамера.

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

 

Задача 2.1

 

Главная цель этой задачи – научиться строить математические модели, позволяющие обеспечить правильное её решение.

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

Для изготовления единицы продукции вида А требуется а кг сырьевого материала, для изготовления единицы продукции В – b кг сырья. Для изготовление единицы продукции вида А требуется с часов рабочего времени; единицы продукции В – d часов рабочего времени. Прибыль от сбыта единицы продукции вида А – составляет е рублей; единицы продукции вида В – f рублей.

Сколько единиц продукции вида А и В должна изготовить фирма, если на складе имеется в наличии q кг сырья, а рабочего времени на изготовление товара даётся h часов.

Решить задачу, построив её математическую модель.

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

Исходные данные представлены в табл. 2.

Таблица 2

Исходные данные для решения задачи 2.1

 

Вариант	Исходные данные
a	b	c	d	e	f	g	h

Решение

 

Рассмотрим конкретный пример построения математической модели.

Фирма изготовляет два вида краски: для внутренних (Е) и наружных (F) работ. Для производства красок используются два исход­ных продукта – А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т соответственно. Расходы А и В на 1 т соответствующих красок приведены в табл. 3.

Изучение рынка сбыта показало, что суточный спрос на краску F никогда не превышает спроса на краску E более чем на 1 т. Кроме того, установлено, что спрос на краску F никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны 3 тыс. долл. для кра­ски E, 2 тыс. долл. для краски F.

Таблица 3

Расходы красок

Исходный продукт	Расход исходных продуктов (в тоннах) на тонну краски	Максимально возможный запас, т
Краска E	Краска F
А В

 

Какое количество краски каждого вида должна производить фаб­рика, чтобы доход от реализации продукции был максимальным?

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

Нахождение переменных. В задаче требуется определить объёмы производ­ства каждого вида краски, поэтому переменными в модели являются x_E – суточный объём производства краски Е; х_F – суточный объём производства краски F.

Определение целевой функции. Стоимость 1 т краски Е равна 3 тыс. долл., суточный доход от её продажи составит 3x_E тыс. долл. Доход от реализации х_F тонн краски F составит 2х_F тыс. долл. в сутки. При допущении независимости объёмов сбыта каждой из красок общий доход z равен сумме двух слагаемых – доходов от продажи краски Е и F. Математическая формулировка целевой функции: опреде­лить значения x_E и х_F, позволяющие получить максимальную величину общего дохода.

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

 

Расход исходного продукта для производства обоих видов краски

£

Максимально возможный запас данного исходного продукта

Это приводит к следующим двум ограничениям (см. условие задачи):

x_E + 2х_F £ 6 (для А), 2x_E + х_F £ 8 (для В).

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

Превышение спроса на краску F относительно спроса на краску Е

£

1 тонна / сутки

(Спрос на краску F) £ 2 тонны / сутки

Математически эти ограничения записываются следующим образом:

х_F – x_E £ 1 (соотношение величин спроса на краску F и краску Е),

х_F £ 2 (максимальная величина спроса на краску F).

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

x_E ³ 0 (объём производства краски Е),

х_F ³ 0 (объём производства краски F).

Итак, математическая модель записывается следующим образом. Определить суточные объёмы производства краски Е и краски F, при которых достигается максимальное значение целевой функции

z =3x_E + 2х_F ® max

при ограничениях

x_E + 2х_F £ 6;

2x_E + х_F £ 8;

– x_E + х_F £ 1;

х_F £ 2;

x_E ³ 0, х_F ³ 0.

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

Задача 2.2

 

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

Задание выбирается из табл. 4 по предпоследней цифре шифра зачётной книжки.

Таблица 4

Исходные данные для решения задачи 2.2

 

Вариант	Задание
Найти	Функция	Ограничения
	max	L = x1 + 3x2	x1 + 4x2 ³ 4; x1 + x2 £ 6; x1 ³ 1; x2 £ 2
	min	L = x1 – x2	x1 + x2 £ 7; x1 + 2x2 ³ 4; 3x1 + 2x2 ³ 9; x1 ³ 1
	max	L = 3x1 – 4x2	x1 – 2x2 £ 6; x1 + 2x2 ³ 0; x1 + x2 £ 8; x1 £ 6
	max	L = –x1 + 2x2	x1 – 8x2 £ 10; x1 + x2 ³ 1; x1 + x2 £ 8; x2 £ 1
	max	L = 8x1 – 2x2	3x1 + 4x2 ³ 18; 3x1 – x2 ³ 3; x1 + 2x2 £ 8; x2 ³ 2
	min	L = –2x1 – x2	x1 + x2 ³ 2; 3x1 + x2 £ 6; x1 – 0,5x2 ³ 0; x1 £ 3
	max	L = x1 + 2x2	x1 + x2 £ 3; 2x1 + 3x2 £ 6; –x1 + x2 £ 1; x2 £ 1
	max	L = 10x1 + x2	3x1 + 2x2 £ 6; 3x1 – 3x2 £ 6; x1 ³ 1; x2 £ 3
	max	L = 3x1 – 6x2	x1 + x2 ³ 3; 3x1 + x2 £ 15; x1 – x2 ³ 0; x2 £ 1
	min	L = 12x1 + 4x2	x1 + 4x2 ³ 8; 2x1 + 3x2 £ 12; x1 £ 6; x2 £ 1

Пример решения

 

В качестве примера рассмотрим графическое решение математической модели, полученной в задаче 1. Требуется по­строить область допустимых решений, в которой одновременно удовлетворяются все ограничения модели. Искомая область решений показана на рис. 3.

Задачу можно решить графически, так как модель содержит только две пере­менные. В случае трёх перемен­ных графическое решение задач становится менее наглядным, а при большем числе переменных – даже невозможным.

Условия неотрицатель­ности переменных x_E ³ 0 и х_F ³ 0 ограничивают область их допусти­мых значений первым квадрантом, представляющим собой часть плоскости, расположенную над осью x_E и правее оси х_F.

 

Ограничения: 1) xE + 2хF £ 6; 2) 2xE + хF £ 8; 3) – xE + хF £ 1; 4) хF £ 2; 5) xE ³ 0; 6) хF ³ 0.

Рис. 1 Построение области допустимых решений и

нахождение оптимального решения

 

Другие границы пространства решений изображены на плоскости x_E х_F прямыми линиями, построенными по уравнениям, которые получаются при замене знака £ на знак = в остальных ограничениях. Области, в которых выполняются соответствующие ограничения в виде неравенств, указываются стрелками, направ­ленными в сторону допустимых значений переменных. Полученный многоугольник ABCDEF является областью допустимых решений.

Оптимальное решение находится, если выяснить, в каком направлении возрастает целевая функция модели z = 3x_E + 2х_F. Эта операция осуществ­ляется следующим образом (рис. 3).

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

Чтобы найти оптимальное решение, следует перемещать прямую, характеризующую доход, в направлении возрастания целевой функ­ции до тех пор, пока она не сместится в область недопустимых решений. На рис. 3. видно, что оптимальному решению соответст­вует точка С. Так как точка С является точкой пересечения прямых (1) и (2), значения x_E и х_F в этой точке определяются решением системы двух уравнений:

x_E + 2х_F £ 6; 2x_E + х_F £ 8.

Решение даёт следующий результат: x_E = 3,33; х_F = 1,33. Это обозначает, что для получения максимального дохода суточный объём производства краски Е должен составлять 3,33 т, краски F – 1,3 т.

 

ЗАДАНИЕ 3

 

СЕТЕВОЕ ПЛАНИРОВАНИЕ

 

Современное сетевое планирование начинается с разбиения программы работ по выполнению какого-либо проекта на этапы (операции, мероприятия). Оценивается продол­жительность этапов работ и строится сетевая модель (график) последовательности их выполнения. Построение такой модели позволяет проанализировать все этапы и внести улучшения в структуру модели до начала её реализации. Строится календарный график, определяющий начало и окончание каждого этапа проекта, а также взаимосвязи с другими этапами. Календарный график выявляет критические этапы, которым надо уделять особое внима­ние, чтобы закончить все виды работ в установленный срок. Что касается некритических этапов, то календарный план поз­воляет определить резервы времени, которые можно выгодно использовать при задержке выполнения проекта или эффектив­ном применении как трудовых, так и финансовых ресурсов.

Сетевая модель – графическое изображение плана выпол­нения комплекса действий (проекта), состоящего из нитей (работ, операций) и узлов (событий), которые отражают логическую взаимосвязь всех работ (операций). В основе сетевого моделирования лежит изображе­ние планируемого комплекса работ (операций) в виде графа.

Граф – схе­ма, состоящая из точек (вершин), соединённых линиями. Линии (отрезки), соединяющие вершины, называются рёбрами (дугами) графа. Ориентированным называется такой граф, на котором стрелкой указаны направления всех его рёбер (дуг), что позволяет определить, какая из двух его вершин является начальной, а какая – конечной.

Сетевая модель – это ориентированный граф без конту­ров. Контур означает такой путь, у которого начальная вершина совпадает с конеч­ной. В сетевом моделировании используются следующие понятия – работа, событие, путь, критический путь.

Работа – это активный процесс, требующий затрат ресур­сов, либо пассивный (ожидание), приводящий к достижению намеченного результата. Фиктивная работа – это связь между результатами работ (событиями), не требующая затрат времени и ресурсов.

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

Путь – это любая непрерывная последовательность (цепь) работ и событий.

Критический путь – это путь, не имеющий резервов и включающий самые напряжённые работы комплекса. Работы, расположенные на критическом пути, называют критически­ми. Все остальные работы являются некритическими (нена­пряжёнными) и обладают резервами времени, которые позво­ляют передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ.

 

Задача 3.1

 

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

1) подготовить техническое задание на переобо­рудование цеха – a ₁ дн.;

2) разработать мероприятия по технике безопасности – a ₂ дн.;

3) подобрать кадры – a ₃ дн.;

4) заказать и поставить необходимое оборудование – a ₄ дн.;

5) заказать и поставить электрооборудование – a ₅ дн.;

6) установить оборудование – a ₆ дн.;

7) установить электрооборудование – a ₇ дн.;

8) обучить персонал – a ₈ дн.;

9) испытать и сдать в эксплуатацию линии – a ₉ дн.

Необходимо составить график работ и определить критический путь.

Исходные данные для решения задачи представлены в табл. 5. Номер варианта определяется по последней цифре номера зачётной книжки.

Таблица 5

Исходные данные для решения задачи 3.1

 

Продолжительность работ	Вариант
a1
a2
a3
a4
a5
a6
a7
a8
a9

 

Пример решения

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

1) подготовить техническое задание на переоборудование участка производства нового вида продукции – 30 дн.;

2) заказать и поставить новое оборудование – 60 дн.;

3) заказать и поставить новое электрооборудование – 50 дн.;

4) демонтировать старое и установить новое оборудование – 90 дн.;

5) демонтировать старое и установить новое электроборудование – 80 дн.;

6) переобучить персонал – 30 дн.;

7) испытать и сдать в эксплуатацию оборудование для производства новой продукции – 20 дн.

 

1. Составим график проведения работ по переоборудованию производства:

 

На проведение переоборудования необходимо

30 + 60 + 50 + 90 + 80 + 30 + 20 = 360 дн.

2. Порядок проведения работ можно оптимизировать, выполняя некоторые работы параллельно. Для этого составляется граф работ по переоборудованию (рис. 1).

 

 

Рис. 2 Граф работ по переоборудованию

 

На этом графе обозначены следующие этапы работ:

0 ® 1 – подготовка технического задания;

1 ® 2 – заказ и поставка нового оборудования;

1 ® 3 – заказ и поставка нового электрооборудования;

2 ® 4 – установка нового оборудования;

3 ® 4 – установка нового электрооборудования;

1 ® 4 – переобучение персонала;

4 ® 5 – сдача в эксплуатацию новой линии.

Граф на рис. 1 позволяет выделить три пути реализации работ и уточнить время их реализации:

· путь (0 ® 1), (1 ® 2), (2 ® 4), (4 ® 5) – 200 дн.;

· путь (0 ® 1), (1 ® 3), (3 ® 4), (4 ® 5) – 180 дн.;

· путь (0 ® 1), (1 ® 4), (4 ® 5) – 80дн.

Критическим путём графика является путь, на котором на­ходятся работы (0 ® 1), (1 ® 2), (2 ® 4), (4 ® 5) продолжительностью

30 + 60 + 90 + 20 = 200 дн.

Срок выполнения работ уменьшился на 360 – 200 = 160 дн.

 

Задача 3.2

 

Транспортному предприятию требуется перевезти груз из пункта 1 в пункт 14. На рис. 3 представлен граф, имитирующий сеть дорог и показывающий стоимость перевозки единицы груза между отдельными пунктами.

 

 

Рис. 3 Сеть дорог

 

Определите маршрут доставки груза, которому соответствуют наименьшие затраты.

Исходные данные для решения задачи представлены в табл. 6. Номер варианта определяется по последней цифре номера зачётной книжки.

 

Таблица 6

Исходные данные для решения задачи 3.2

 

Стоимость перевозки	Вариант
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21
a22
a23
a24

 

 

Пример решения

Определите маршрут доставки груза, которому соответствуют наименьшие затраты по графу на рис. 3.

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

 

Введем обозначения:

d_ij – расстояние на сети между смежными узлами i и j;

U_j – кратчайшее расстояние между узлами i и j, U ₁ = 0. Значение U_j рассчитывается по зависимости

 

 

 

 

{ U_i + d_ij }.

 

Из формулы следует, что кратчайшее расстояние U_j до уз­ла j можно вычислить лишь после того, как определено крат­чайшее расстояние до каждого предыдущего узла i, соединён­ного дугой с узлом j. Процедура завершается, когда получено U_i последнего звена.

Определим кратчайшее расстояние между узлами 1 и 7 графа, представленного на рис. 4.

 

Рис. 4 Сеть дорог транспортной сети

 

Находим минимальные расстояния:

U ₁ = 0;

U ₂ = U ₁ + d ₁₂ = 0 + 2 = 2;

U ₃ = U ₁ + d ₁₃ = 0 + 4 = 4;

U ₄ = min{ U ₁ + d ₁₄; U ₂ + d ₂₄; U ₃ + d ₃₄} =

= min{0 + 10; 2 + 11; 4 + 3} = 7;

U ₅ = min{ U ₂ + d ₂₅; U ₄ + d ₄₅} = min{2 + 5; 7 + 8} = 7;

U ₆ = min{ U ₃ + d₃₆; U ₄ + d ₄₆} = min{4 + 1; 7 + 7} = 5,

U ₇ = min{ U ₅ + d₅₇; U ₆ + d₆₇} = min{7 + 6; 5 + 9} = 13.

Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут: 1 ® 2 ® 5 ® 7.

 

ЗАДАНИЕ 4