МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Белгородский государственный технологический университет им. В. Г. Шухова

Экономико-математическое моделирование производственных систем

Методические указания к выполнению лабораторных работ для студентов направления 080100 Экономика

Белгород

2014

2

Лабораторная работа № 1 Классические методы решения задач линейного программирования

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

Содержание

Изучаются вопросы:

1.Задача линейного программирования. Общий вид. Основные понятия и определения.

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

Выполняется вариант задания.

Указания

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

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

U = f(Х) ® max; Х Î W,

(1)

где Х = (х1, х2, ..., хn); W - область допустимых значений переменных х1, х2, ..., хn; f(Х) - целевая функция.

Для того чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т. е. указать Х0 Î W такое, что f(Х0) ³ f(Х) при любом Х Î W, или для случая минимизации- f(Х0) £ f(Х) при любом Х Î W. Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. Методы решения оптимизационных задач

зависят как от вида целевой функцииf(Х), так	и от	строения
допустимого множества W. Если целевая функция в задаче является
функцией n переменных, то методы решения	называют	методами
математического программирования.

3

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

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

план, на котором достигается максимум или минимум функцииF,

называется оптимальным планом задачи.

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

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

В общем случаезадача оптимального распределения ресурсов

формулируется следующим образом. Предприятие распоряжается ресурсами различных типов. Среди таких ресурсов могут быть материально-вещественные, энергетические, трудовые, технические, финансовые и другие. Пусть в общем виде на предприятии для анализа используются m видов ресурсов. Пронумеруем все виды ресурсов числами от 1 до m, буквой i будем обозначать номер вида ресурса. Таким образом, i удовлетворяет неравенству1 £ i £ m. Заметим, что ресурсы разных видов могут измеряться в различных единицах(тоннах, кубометрах, человеко-часах, рублях, штуках и др.).

В течение планового периода предприятие обладает некоторыми доступными объемами ресурса каждого вида. Объем ресурса i-го вида обозначим посредством bi.

Из этих ресурсов предприятие способно изготавливать различную

продукцию. Обозначим			буквой n	общее	число	видов продукции,
которые	может	выпустить предприятие			из	имеющихся ресурсов.
Занумеруем все виды продукции числами от					1 до n. Буквой j будем
обозначать	номер	вида	продукции,	так что	выполняется неравенство

1 £ j £ n. Обозначим через cj цену, по которой предприятие реализует каждую единицу продукции j-го вида. Производство продукции требует затрат ресурсов. Объем затрат зависит от вида ресурса, вида продукции

4

и количества единиц продукции. Обозначим посредством aij норму затрат ресурса i-го вида на производство продукции j-го вида.

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

Построим математическую модель задачи. Сначала введем переменные. Посредством xj обозначим искомый объем выпуска продукции j-го вида. Математическую модель можно теперь записать в следующей форме:

F = c1x1 + c2x2 + … + cnxn ® max

ìa11x1 + a12 x2

+ ... + a1n xn

£ b1

ïa

21

x

+ a

22

x

2

+ ... + a

2n

x

n

£ b

ï

1

2

í..................................................

ïam1x1 + am2 x2 + ... + amn xn £ bm

ïx

³

0, x

2

³

0,..., x

n

³ 0

î 1

Верхняя строка записи говорит о максимизациицелевой функции.

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

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

максимального

значения

целевой функции

nот переменных

при

условии,

что

значения

этих

переменных

подчинены

системе

ограничений, имеющих форму неравенств.

Всякий

набор

значений

переменных(x1, x2,

...,

xn)

называется

пла ном

задачи. Те

планы,

которые

удовлетворяют

системе

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

называются

допустимым и

пла нам.

и

Оптимал ьным

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

который дает наибольшее значение целевой функции среди всех ее

значений

на допустимых планах. Само это наибольшее значение

целевой

функции,

т. е. значение

целевой

функции

на

оптимальном

плане, называется оптимумом задачи.

Решить задачу производственного планирования- это найти

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

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

Симплекс-метод является основным в линейном программировании.

Решение

задачи

начинается

с

рассмотрений

одной

из

вершин

многогранника условий. Если исследуемая вершина не соответствует

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

функции

цели при решении задачи на максимум

и

уменьшая

при

решении

задачи

на

минимум. Таким

образом,

переход

от

одной

5

вершины к другой улучшает значение функции цели. Так как число вершин многогранника ограничено, то за конечное число шагов

гарантируется

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

значения

или установление

того факта, что задача неразрешима.

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

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

вканонической

форме.

Система

ограничений

здесь

-

система

линейных уравнений,

которой

количество неизвестных больше количества уравнений. Если ранг

системы равен r, то мы можем выбрать r неизвестных,

которые выразим

через остальные неизвестные. Для определенности предположим, что

выбраны первые, идущие подряд, неизвестные x1, x2, …, xr. Тогда наша

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

ì x1 = b1 + a1g +1xg +1 +K+ a1n xn ,

ïx

2

= b + a

2g +1

x

+K

+ a

2n

x

n

,

ï

2

g +1

í

KKKKKKKKKKKK

ï

ï x

r

= b + a

rg +1

x

+K+ a

rn

x

n

.

î

r

g +1

К такому

виду

можно

привести

любую

совместную систему,

например, методом Гаусса. Правда, не всегда можно выражать через остальные первые r неизвестных (мы это сделали для определенности записи). Однако такие r неизвестных обязательно найдутся. Эти неизвестные (переменные) называются базисными, остальные

свободными.

Придавая определенные значения свободным переменным, и вычисляя значения базисных (выраженных через свободные), мы будем получать различные решения нашей системы ограничений. Таким образом, можно получить любое ее решение. Нас будут интересовать особые решения, получаемые в случае, когда свободные переменные равны нулю. Такие решения называются базисными, их столько же, сколько различных базисных видов у данной системы ограничений. Базисное решение называется допустимым базисным решением или опорным решением, если в нем значения переменных неотрицательны. Если в качестве базисных взяты переменныеx1, x2, …, xr, то решение {b1, b2, …, br, 0, …, 0} будет опорным при условии, что b1, b2, …, br ≥ 0.

Симплекс-метод основан на теореме, которая называется

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

6

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

Симплекс-метод	представляет	собой	некоторую	процедуру
направленного	перебора опорных	решений. Исходя	из некоторого,

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

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

Итак, симплексный метод вносит определенный порядок как при нахождении первого (исходного) базисного решения, так и при переходе

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

решением поступают так же, пока не находят решение, которое является оптимальным.

Если первое найденное базисное решение окажетсянедопустимым, то с помощью симплексного метода осуществляется переход к другим базисным решениям, которые приближают нас к области допустимых решений, пока на каком-то шаге решения, либо базисное решение

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

Таким образом, применение симплексного метода распадается на два

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

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

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

7

Порядок работы с симплекс таблицей

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

Алгоритм перехода к следующей таблице такой:

-просматривается последняя строка (индексная) таблицы и среди коэффициентов этой строки(исключая столбец свободных членов) выбирается наименьшее отрицательное число при отысканииmax, либо наибольшее положительное при задачи наmin. Если такового нет, то исходное базисное решение является оптимальным и данная таблица является последней;

-просматривается столбец таблицы, отвечающий выбранному отрицательному коэффициенту в последней строке- ключевой столбец

(j = k), и в этом столбце выбираются положительные коэффициенты.

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

-среди выбранных коэффициентов столбца выбирается тот, для

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

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

-строится новая таблица, содержащая новые названия базисных переменных: строка разрешающего элемента делится на этот элемент

	и	полученная			строка записывается в		новую таблицу на то			же место
	¢		arj	, 1 £ j	£ n; в новой таблице все элементы ключевого столбца
	arj	=
			ark
	равны 0, кроме разрезающего, он всегда равен 1; столбец, у которого в
	ключевой строке имеется 0, в новой таблице будет таким же; строка, у
	которой в ключевом столбце имеется 0, в новой таблице будет такой же;
	в	остальные			клетки	новой	таблицы	записывается			результат
							¢		aij × ark - arj	× aik
	преобразования				элементов	старой	таблицыaij	=			,
									ark

1 £ i £ m, 1 £ j £ n.

В результате получают новую симплекс-таблицу, отвечающую новому базисному решению.

Теперь следует просмотреть строку целевой функции, если в ней нет отрицательных значений (в задачи на нахождение максимального

8

значения), то значит, что оптимальное решение получено. В

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

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

Таблица 1

		Нормы затрат ресурсов на		Запасы
	Ресурс	единицу продукции
				ресурсов
		Продукт А	Продукт В
	Электроэнергия	3	7	29
	Сырье	3	1	18
	Оборудование	1	6	23
	Цена единицы продукции	15	10

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

			Решение:
1. Обозначим через x1		и x2	количество продукции A и B,		которую
планируется	произвести	в	планируемом	периоде. Тогда	общая

стоимость выпущенной продукции составит F = c1x1 + c2x2 = 15x1 + 10x2. Необходимо найти такие значенияx1 и x2, чтобы величина F была максимальной, т.е. F ® max.

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

необходимо	израсходовать a11x1 =	3x1	единиц		электроэнергии,	а на
изготовление	продукции В - a12x2	=	7x2	единиц. Поскольку		запас
электроэнергии не превышает b1 =		29	единиц,		то величины x1	и x2
должны удовлетворять неравенству3x1			+ 7x2	£ 29. Аналогично можно

получить неравенство ресурса сырье - 3x1 + x2 £ 18, а также для ресурса оборудование - x1 + 6x2 £ 23. Кроме того, величины x1, x2 не могут быть отрицательными, т.е. x1 ³ 0 и x2 ³ 0.

Таким образом, задача заключается в нахождении точки максимума функции F среди точек с координатами(x1; x2), которые удовлетворяют указанным неравенствам.

9

Запишем сформулированную задачу линейного программирования следующим образом:

F = 15x1 + 10x2 ® max,

ìï3x1 + 7x2 £ 29, í 3x1 + x2 £ 18,

ïî x1 + 6x2 £ 23, x1, x2 ³ 0.

2. Чтобы привести модель задачи к каноническому виду, необходимо систему ограничений-неравенств привести к системе ограниченийравенств. Для этого к левой части каждого неравенства прибавим

добавочные неотрицательные			переменные х3, x4,					x5. Эти добавочные
переменные в условиях данной задачи имеют конкретное экономическое
содержание, т.е. объем		остатков					ресурса	каждого	вида	после
выполнения плана выпуска продукции.
Задача линейного программирования в канонической форме имеет
вид:	F = 15x1 + 10x2 ® max,
	ì3x		+ 7x		2	+ x	= 29,
	ï	1				3
	í	3x1 + x2 + x4 =18,
	ï x + 6x			2		+ x	= 23,
	î	1				5
Так	как система		x1, x2 ³ 0.
		ограничений состоит из трех независимых
уравнений с пятью переменными, то							число	базисных	переменных
должно равняться трем, а число свободных – двум.
Для	решения задачи	симплексным методом прежде всего нужно
найти любое базисное решение.

В условиях данной задачи оно может быть найдено без труда . Для этого достаточно принять за базисные добавочные переменныех3, х4, х5.

Так как коэффициенты при этих переменных образуют единичную

матрицу, то	отпадает	необходимость			вычислять	определитель
(определитель единичной матрицы равен 1, т.е. отличен от нуля).
В этом случае системы ограничений примет вид:
	ìx	= 29 - 3x	- 7x
	ï 3	1		2
	íx4 = 18 - 3x1 - x2
	ïx	= 23 - x - 6x		2
	î 5	1

Положив свободные переменные х1, х2, равными нулю, получим первое базисное решение(0; 0; 29; 18; 23), которое оказалось допустимым.

		10
Переходим сразу к этапу поиска оптимального решения задачи.
I шаг.	Базисные переменные х3, х4,		х5. В столбец Свободные		члены
заносим	значения базисных переменных в базисном				решении. В
остальные	столбцы	записываем	значения	коэффициентов		при

переменных в системе ограничений ЗЛП. Затем заполнив таблицу, находим разрешающий элемент (рис. 1).

Рис. 1. Модель заполнения симплекс-таблицы

Базисное решение F = 0

(0; 0; 29; 18; 23).

Просматриваем последнюю строку таблицы и среди коэффициентов

этой

строки (исключая

столбец

свободных

членов) выбираем

наименьшее отрицательное число. Для нашего примера – это столбец

переменной x1. Среди коэффициентов столбца x1 выбираем тот, для

которого

абсолютная

величина

отношения

соответствующего

свободного члена (находящегося в столбце свободных членов) к этому

элементу

минимальна (столбец

H).

Для

нашего

примера– это

коэффициент строки x4.

x

= minì

29

;

18

;

23

ü = min{9,67; 6; 23}= 6 .

1

í

3 1

ý

î 3

þ

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

II шаг. Базисные переменные х3, х1, х5. Составляем новую симплекстаблицу. На рис. 2 представлена модель перерасчета коэффициентов симплекс-таблицы на II шаге, результаты вычисления коэффициентов на рис. 3.

11

Рис. 2. Общая модель перерасчета коэффициентов симплекс-таблицы шаг II

Рис. 3. Результат расчета коэффициентов симплекс-таблицы

Базисное решение F = 90 (6; 0; 11; 0; 17).

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

решения повторяем		алгоритм					работы с симплекс-таблицы . снова
Находим разрешающий элемент:
ì11			6		17	ü	= min{1,83;18;3}= 1,83 .
x2 = miní		;		;		ý
			0,33		5,67
î 6						þ

III шаг. Базисные переменные х2, х1, х5. Выполняем перерасчет коэффициентов симплекс-таблицы (рис. 4).

Рис. 4. Симплекс-таблица на III шаге

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

столбцам Базисные переменные и Свободные члены: Fmax = 99,17; х1 = 5,39;

х2 = 1,83; х3 = 0; х4 = 0; х5 = 6,61.

Т.е. для получения наибольшего дохода, равного 99,17 денежных единиц, предприятие должно выпустить 5,39 единиц продукции вида А и 1,83 единицы продукции В. При этом ресурсы Электроэнергия и Сырье будут использованы полностью, а 6,61 единиц ресурса Оборудования останутся неизрасходованными.

				12
				ЗАДАНИЯ
				Вариант 1
	Для выпуска двух видов продукции						требуются	затраты	, сырья
рабочего		времени	и	оборудования. Нормы			затрат	ресурсов	на
производство единицы продукции каждого вида, прибыль на единицу
продукции каждого вида, а также запасы ресурсов, которые могут быть
использованы предприятием, приведены в табл. 2.								Таблица 2
					Нормы затрат ресурсов на			Запасы
		Ресурс			единицу продукции
								ресурсов
					Продукт 1		Продукт 2
	Сырье				3		5	60
	Рабочее время				22		14	250
	Оборудование				10		14	128
	Прибыль на единицу продукции				30		25

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

Вариант 2

Цех выпускает два вида деталей – А и Б. Каждая деталь обрабатывается тремя станками. Организация производства в цехе характеризуется следующими данными(табл. 3). Составить план загрузки станков, обеспечивающий цеху получение максимальной прибыли.

Таблица 3

		Длительность обработки		Запасы
	Станок	детали, мин
				ресурсов
		Деталь А	Деталь Б
	Станок 1	12	10	220
	Станок 2	15	18	370
	Станок 3	6	4	100
	Отпускная цена за одну деталь	30	32

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

Вариант 3

Цех выпускает два вида продукции – А и В, используя при этом последовательно три станка. Данные о технологическом процессе указаны с табл. 4. Составить план выпуска продукции, обеспечивающий предприятию наибольшую прибыль.

		13
				Таблица 4
		Трудоемкость на одну		Фонд
	Станок	единицу продукции
				времени, ч
		Деталь А	Деталь В
	Станок 1	3	3	150
	Станок 2	2	6	180
	Станок 3	1	2	80
	Прибыль на единицу продукции	2	3

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

Вариант 4

На заводе используется сталь трех марокA, B и C, запасы которых соответственно 10, 16 и 12 единиц. Завод выпускает два вида изделий. Для изделия № 1 требуется по одной единице стали всех марок. Для изделия № 2 требуется две единицы стали маркиB , одна единица - марки С и не требуется сталь марки А. От реализации единицы изделия № 1 завод получает три усл. ден. ед. прибыли, изделия № 2 - две усл. ден. ед. (табл. 5). Составить план выпуска продукции, дающий наибольшую прибыль.

			Таблица 5
Ресурсы	Нормы расхода ресурса		Общее количество
	на 1 ед. изделия		ресурса
	Изделие № 1	Изделие № 2
Сталь марки А	1	0	10
Сталь марки В	1	2	16
Сталь марки С	1	1	12
Прибыль	3	2

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

Вариант 5

Для изготовления двух видов изделийA и B, используется токарное, фрезерное и сварочное оборудование. Затраты времени на обработку одного изделия указаны в табл. 6. В таблице также указан общий фонд рабочего времени, а также прибыль от реализации одного изделия

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

14

				Таблица 6
Тип	Затраты времени на обработку изделия,			Общий фонд
		станко-ч		рабочего времени
оборудования
	A		B	(ч)
Фрезерное	2		4	120
Токарное	1		8	280
Сварочное	7		4	240
Прибыль	10		14

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

Вариант 6

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

				Таблица 7
		Нормы затрат		Общее
Ресурс	на одно изделие			количество
	стол		шкаф	ресурсов
Древесина:
1-й вид	0,2		0,1	40
2-й вид	0,1		0,3	60
Трудоемкость (чел-ч.)	1,2		1,5	371,4
Прибыль от реализации	6		8
единицы изделия (усл. ден. ед.)

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

Вариант 7

На звероферме могут выращивать черно-бурых лисиц и песцов. Для обеспечения нормальных условий их выращивания используется три

вида кормов.	Количество	корма	каждого	вида, которое	должны
ежедневно получать лисицы и песцы , приведено в табл. 8. Также в
таблице указаны общее количество корма каждого вида, которое может
быть использовано зверофермой, и прибыль				от реализации одной
шкурки лисицы и песца.
Определить	сколько	лисиц	и песцов	следует	выращивать на

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

15

				Таблица 8
	Ежедневное количество единиц			Общее
Вид корма		корма		количество
	лисица		песец	корма
I	2		3	180
II	4		1	240
III	6		7	426
Прибыль от реализации одной	16		12
шкурки (усл. ден.ед.)

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

		Вариант 8
Компания специализируется на			выпуске	хоккейных	клюшек	и
наборов	шахмат. Каждая	клюшка	приносит	компании	прибыль	в
размере 2 ден. ед., а каждый шахматный набор - в размере 4 ден. ед. На
изготовление одной клюшки требуется 4 ч работы на участке A и 2 ч
работы на участке B. Шахматный набор изготавливается с затратами6
часов на	участкеA, 6 ч на	участке B и 1 ч на		участке C. Доступная

производственная мощность участкаA составляет 120 н-ч в день, участка В - 72 н-ч и участка С - 10 н-ч. Сколько клюшек и шахматных наборов должна выпускать компания ежедневно, чтобы получать максимальную прибыль?

			Таблица 9
	Затраты времени на единицу		Доступный
Производственные участки	продукции, н-ч		фонд времени,
	клюшка	набор шахмат	н-час
А	4	6	120
В	2	6	72
С	-	1	10
Прибыль на единицу продукции	2	4

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

Вариант 9

Фабрика изготовляет два вида красок: для внутренних и наружных работ. Продукция обоих видов поступает в оптовую продажу.

	Для производства красок используются три исходных продукта А, В
и	С.	Максимально возможные	суточные запасы	этих продуктов
составляют 56, 80 и 117 т соответственно. Расходы продуктов А, В и С
на	1	т соответствующих красок	и максимально	возможный запас

16

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

				Таблица 10
		Расход продуктов		Суточные
	Вид исходного продукта	на 1 т красок		запасы
		краска для	краска для	исходных
		наружных работ	внутренних работ	продуктов
	А	1	2	56
	В	2	1	80
	С	3	1	117
	Оптовые цены 1 т красок	3	2

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

Вариант 10

Мастерская имеет в своем распоряжении определенное количество производственных ресурсов: трудовые, денежные средства, сырье, оборудование, производственные площади и . т.пДля получения оптимального плана рассмотрите использование ресурсов трех видов- трудовые, сырье и оборудование, которые имеются в количестве соответственно 60, 28 и 42 единицы. Мастерская выпускает ковры двух видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида(о нормах расхода производственных ресурсов), и доходах, получаемых предприятием от реализации единицы каждого вида товаров, приведена в табл. 11.

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

Таблица 11

	Нормы расхода ресурсов на единицу			Наличие
Ресурс		изделия
				ресурсов
	Ковер А		Ковер В
Труд	4		2	60
Сырье	1		1	28
Оборудование	3		1	42
Цена	14		10

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

17

Контрольные вопросы

1.Задача линейного программирования: основные понятия, общий вид, типы задач.

2.Дайте определения математической модели, плана, допустимого плана, оптимума, области допустимых решений.

3.Дайте определения базисных и свободных переменных, решений оптимальных и допустимых.

4.Как заполнить симплекс-таблицу?

5.	Объясните	алгоритм перехода	от одной симплекс-таблицы к
другой.
6.	Назовите	этапы нахождения	оптимального плана симплекс-
методом.

18

Лабораторная работа № 2 Теория двойственности. Решение задач линейного

программирования в MS Excel, анализ полученных результатов

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

Содержание

Изучаются вопросы:

1.Элементы теории двойственности в задачах линейного программирования.

2.Решение задачи линейного программирования в Microsoft Excel.

Выполняется вариант задания.

Указания

Элементы теории двойственности в задачах линейного программирования

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

F = c1x1 + c2x2 + … + cnxn ® max,

ìa11x1 + a12 x2 + ... + a1n xn £ b1,

ïa

x

+ a

22

x

2

+ ... + a

2n

x

n

£ b

,

ï

21

1

2

ï

í..........

..........

..........

..........

..........

ïa

m1

x

+ a

m2

x

2

+ ... + a

mn

x

n

£ b

,

ï

1

m

ïx

³ 0, x

2

³

0,..., x

n

³ 0.

î 1

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

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

19

Z = b1y1 + b2y2 + … + bmym ® min,

ìa11 y1 + a12 y2 + ... + a1m ym ³ c1,

ïa

21

y

+ a

22

y

2

+ ...

+ a

2m

y

m

³ c

2

,

ï

1

ï

í...............................................

ïa

n1

y

+ a

n2

y

2

+ ...

+ a

nm

y

m

£ c

m

,

ï

1

ïy ³ 0, y

2

³ 0,..., y

m

³ 0.

î 1

Каждая

из

задач

двойственной

пары

фактически

является

самостоятельной задачей линейного программирования и может быть

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

методом оптимального плана одной из задач

находится

решение

и

другой задачи.

Двойственная задача по отношению к исходной составляется

согласно следующим правилам:

1) целевая функция исходной задачи формулируется на максимум, а

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

на максимум все неравенства в функциональных ограничениях имеют

вид £, а в задаче на минимум - вид ³;

æ a

a

K a

ö

ç

11

12

1n

÷

2)

матрица А = ç a21

a22

K a2n ÷ , составленная

из

коэффициентов

ç

M

M

M M

÷

ç

am2

÷

èam1

K amn ø

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

æ a11

a21 K am1

ö

матрица А

Т

=

ça

a

22

K a

m2

÷

ç

12

÷ , в двойственной задаче получаются друг

ç

M

M

M

M

÷

ça

a

2 n

K a

mn

÷

è

1n

ø

из друга транспонированием;

3)

число

переменных

в

двойственной

задаче

равно

числу

функциональных ограничений исходной задачи, а число ограничений в

системе двойственной задачи - числу переменных в исходной задаче;

4)

коэффициентами

при

неизвестных

в

целевой

функции

двойственной задачи являются свободные члены в системе ограничений

исходной задачи, а правыми частями в ограничениях двойственной

задачи - коэффициенты при неизвестных в целевой функции исходной

задачи;

5) каждому ограничению одной задачи соответствует переменная

другой задачи: номер переменной совпадает с номером ограничения;

при

этом

ограничению, записанному

в

виде

неравенства£,

соответствует переменная, связанная условием неотрицательности. Если

20

функциональное ограничение исходной задачи является равенством, то

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

содержатся в двух следующих теоремах.

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

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оптимальных решениях совпадают: Fmax = Zmin.

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

3.В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.

4.Обе из рассматриваемых задач имеют пустые допустимые множества.

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

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

неравенств	в системе	ограничений): хn+1, хn+2, …, хn+i, ..., хn+m, где
1 £ i £ m	означает	номер неравенства, в которое была введена

добавочная переменная хn+i.

Система ограничений двойственной задачи состоит изn неравенств,

в которых	имеютсяm	переменных. При	решении	этой задачи
симплексным	методом	необходимо	ввестиn	добавочных

неотрицательных переменных: уm+1, ym+2, …, уm+j, …, ym+n, где 1 £ j £ n означает номер неравенства системы ограничений двойственной задачи, в которое была введена добавочная переменная уm+j.

Установим следующее соответствие между переменными исходной и

двойственной задачи:
x1	x2	…	xj	…	xn	xn+1	xn+2	…	xn+i	…	xn+m
b	b		b		b	b	b		b		b
ym+1	ym+2	…	ym+j	…	ym+n	y1	y2	…	yi	…	ym

			21
Иными	словами, каждой		первоначальной переменной исходной
задачи xj (1 £ j £ n) ставится в соответствие добавочная переменная уm+j,
введенная в j-е неравенство двойственной задачи, а каждой добавочной
переменной xn+i исходной задачи (1 £ i £ m), введенной в i-е неравенство
исходной задачи, ставится в соответствие первоначальная переменнаяyi
двойственной задачи.
Вторая	теорема	двойственности. Компоненты			оптимального
решения задачи линейного программирования равны абсолютным
величинам	коэффициентов		при	соответствующих	переменных	в

выражении линейной формы двойственной ей задачи при достижении ею оптимума.

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

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

Теорема об оценках. Значения переменныхуi в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов bi системы ограничений-неравенств прямой задачи на величину Fmax , т. е.

yi = ¶Fmax .

¶bi

Эта теорема показывает еще одну связь между переменными прямой и двойственной задач. Поясним это подробнее.

Пусть (х1, х2, …, хj, …, xn) - оптимальное решение прямой задачи, а (у1, у2, …, уi, …, уm) - оптимальное решение двойственной задачи. Оптимальные значения целевых функцийF и Z достигаются при подстановке компонент оптимального решения в их первоначальные выражения, т. е.

Fmax = c1x1 + … + cjxj + … + cnxn,

Zmin = b1y1 + … + biyi + … + bmym.

На основании первой теоремы двойственности(Fmax = Zmin) можно записать

c1x1 + … + cjxj + … + cnxn = b1y1 + … + biyi + … + bmym.

Отсюда следует, что

Fmax = b1y1 + … + biyi + … + bmym.

Поставим вопрос, как изменится величинаFmax, если в исходной задаче увеличить свободный членbi, в i-м ограничении-неравенстве на величину Dbi (1 £ i £ m). Величина Fmax, рассматриваемая теперь как

22

функция переменных b1, …, bi, …, bm, получит приращение DFmax. Частные производные этой функции по любому из этих аргументов имеют вид

¶Fmax = yi .

¶bi

Учитывая, что функция Fmax линейная, получим DFmax = yiDbi.

Пример. Рассмотрим экономическую интерпретацию двойственной задачи на примере (см. лабораторную работу №1) выше.

F = 15x1 + 10x2 ® max,

ìï3x1 + 7x2 £ 29, í 3x1 + x2 £ 18,

ïî x1 + 6x2 £ 23,

		x1, x2 ³ 0.
Пусть	некая	организация	решила	закупить	все	ресурсы
рассматриваемого		предприятия. При	этом	необходимо	установить
оптимальную	цену	на приобретаемые	ресурсы1, у2, у3, исходя из

следующих объективных условий:

1)покупающая организация старается минимизировать общую стоимость ресурсов;

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

Согласно первому условию общая стоимость сырья выразится

величиной Z = 29у1 + 18у2 + 23у3 ® min.

Согласно второму требованию вводятся ограничения: на единицу
продукции А	расходуются	три	единицы	первого	ресурса

(Электроэнергия) ценой у1, три единицы второго ресурса (Сырье) ценой у2, одна единица третьего ресурса (Оборудование) ценой у3. Стоимость всех ресурсов, расходуемых на производство единицы первого вида продукции, равна 3у1 + 3у2 + у3 и должна составлять не менее 15 единиц, т. е.

3у1 + 3у2 + у3 ³ 15.

В результате аналогичных рассуждений относительно производства продукции В получаем неравенство:

7у1 + у2 + 6у3 ³ 10.

По экономическому смыслу цены неотрицательные: y1, y2, y3 ³ 0. Получили симметричную пару взаимодвойственных задач.

23

F = 15x1 + 10x2 ® max,

Z = 29у1 + 18у2 + 23у3 ® min,

ì3x

+ 7x

2

£

29,

ì3y

+ 3 y

2

+ y

3

³ 15,

ï

1

+ x

£

18,

í

1

+ y

³ 10,

í

3x

2

7 y

2

+ 6 y

1

î

1

3

ï x + 6x

2

£

23,

y1, y2, y3 ³ 0.

î

1

x1, x2 ³ 0;

Так как прямая задача решена симплекс-методом, опираясь на

теоремы запишем решение двойственной задачи.

Задача

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

имеет

конечный

оптимум,

тогда двойственная к ней также имеет конечный оптимум . При этом

Fmax = 99,17, тогда Zmin = 99,17.

между

переменными

исходной

и

Установим

соответствие

двойственной задачи:

x1

x2

x3

x4

x5

b

b

b

b

b

y4

y5

y1

y2

y3

В

результате

решения

данной

задачи

симплексным

методом

получено следующее решение (0,83; 4,17; 0; 0; 0), которое записываем

из строки F таблицы оптимального решения..

Компоненты у1, у2, у3

оптимального

решения

двойственной

задачи

оценивают добавочные переменные х3, х4, х5 прямой задачи.

Равенство

нулю

переменнойу3, в

оптимальном

решении

свидетельствует о том, что переменная х5

положительна в оптимальном

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

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

обращает его в строгое равенство. Переменные у1, у2 положительны, а

соответствующие им

переменные прямой

задачих3, х4

равны нулю в

оптимальном

решении

прямой

задачи. Подстановка

компонент

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

обращает их в строгие равенства.

Экономический смысл этого обстоятельства состоит в , томчто

ресурса Оборудования в задаче имеется с излишком и этим ресурсом не

особенно дорожат, поэтому устанавливают для него нулевую оценку. А

ресурсы

Электроэнергия

и Сырье

являются

дефицитным(целиком

расходуются),

поэтому

эти

виды

оценивают

некоторыми

положительными оценками (у1 = 0,83, у2 = 4,17).

Как оценить единицу ресурса каждого вида в зависимости от того

дохода, который приносит предприятию реализация продукцииА и В?

Речь идет не о стоимости ресурса при его приобретении предприятием.

В задаче

нас

интересует относительная

стоимость

ресурса с

точки

зрения получения максимального дохода при изменении его запасов.

24

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

роста	максимального		дохода	при	увеличении, например		запаса
Электроэнергии или Сырья.
Согласно выводу из теоремы об оценках DFmax = yi×Dbi.
В	этой	формулеуi	-	компонента		оптимального	решения

двойственной задачи, которые выступают как условные цены единицы i-го вида ресурса. Поэтому переменные двойственной задачи часто называют объективно обусловленными оценками.

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

DFmax = y3×Db3 = 0 × 1 = 0,

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

Увеличим на 1 единицу запас Электроэнергии. Тогда

DFmax = y1×Db1 = 0,83 × 1 = 0,83.

Увеличив на одну единицу запас ресурса Сырье, получим

DFmax = y2×Db2 = 4,17 × 1 = 4,17.

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

видов изделий выгодные для предприятия			с экономической точки
зрения.				Таблица 12
	Объективно	Затраты ресурсов на единицу
Ресурс	обусловленные оценки		продукции
	ресурсов	Продукт С		Продукт D
Электроэнергия	0,83	6		4
Сырье	4,17	3		2
Оборудование	0	3		4
Цена единицу продукции		15		14

Решим эту задачу на основании свойства двойственных оценок : в оптимальный план задачи на получение максимума дохода может быть

					m
включен	лишь	тот	вариант, для	которого	величинаåaij yi ,
					i =1

покрывается установленной ценой сj. Таким образом, характеристикой того или иного варианта служит разность

25

m

D j = åaij yi - c j , i =1

при этом если, Dj £ 0, то вариант выгоден; если. Dj > 0, то невыгоден. Для продукта С:

DС = 0,83 ∙ 6 + 4,17 ∙ 3 + 0 ∙ 3 – 15 = 17,49 – 15 = 2,49

Поскольку DС = 2,49 > 0, то делаем вывод, что продукт С невыгодно включать в план, так как затраты на его изготовление не покрываются получаемой прибылью.

Аналогично оценим прибыль продукта D:

DD = 0,83 ∙ 4 + 4.17 ∙ 2 + 0 ∙ 4 – 14 = 11,66 – 14 = -2,34.

Поскольку DD = -2,34 > 0, то делаем вывод, что продукт D невыгодно включать в план, так как затраты на его изготовление покрываются получаемой прибылью.

Решение задачи линейного программирования в Microsoft Excel

Для решения рассматриваемой задачи с помощью программыMS Excel необходимо выполнить следующие действия.

1. Осуществляем ввод данных в таблицуExcel согласно схеме, представленной на рис. 5.

Рис. 5. Заполнение схемы для решения задачи

Для переменных задачи x1 и x2 отведены ячейки B3 и C3. Эти ячейки называются рабочими или изменяемыми ячейками. В изменяемые ячейки значения не заносятся, в результате решения задачи в этих ячейках будет отражено оптимальное значение переменной.

В ячейку D4 необходимо ввести формулу для вычисления целевой

функции задачи (дохода) F = 15x1	+ 10x2. Формула в алфавите языка
Excel имеет вид: =B4*B3+C4*C3.	ресурса Электроэнергия составляет
Израсходованное количество
3x1 + 7x2. В ячейку D7 (расход	электроэнергии) вводится	формула
=B7*$B$3+C7*$C$3.
Аналогично вводятся формулы расхода остальных		ресурсов, а
именно Сырья и Оборудования. В ячейку D8 (расход сырья)		вводится

26

формула =B8*$B$3+C8*$C$3. В ячейку D9 (расход оборудования) вводится

формула =B9*$B$3+C9*$C$3.

В результате страница примет вид:

Рис. 6. Вид страницы с добавленными формулами

2. На вкладке Данные выбираем команду Поиск решения (если команда отсутствует в окне параметровExcel выберете Надстройки ® Перейти и установите Поиск решения) (рис. 7).

Рис. 7. Окно средства Поиск решения

В появившемся окне нужно оптимизировать целевую функцию в ячейке D4 до Максимум, изменяя ячейки переменных B3:C3. Выберите

метод решения: Поиск решения линейных задач симплекс-методом.

3. Чтобы ввести ограничения задачи, нажать кнопку Добавить. В появившемся диалоговом окне слева ввести адресD7 (израсходованное количество Электроэнергии), затем выбрать знак ≤ и в правой части количество этого ресурса, равное 29 (или адрес ячейки E7). После ввода нажать кнопку Добавить и аналогично ввести второе и третье ограничения, а также условие положительности изменяемых ячеек.

27

Рис. 8. Добавление ограничения

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

(рис. 9).

Рис. 9. Результат добавления ограничений

5. Для решения задачи в окнеПоиск решения нажать кнопку Найти решение. Если решение найдено, появляется окно (рис. 10).

Рис. 10. Результаты Поиска решения

7. Для просмотра результатов выбираем тип отчетаРезультаты и нажимаем кнопку ОК. В рабочей книге появится лист Отчет по

28

результатам, который состоит из трех таблиц (рис. 11): в таблице 1 приводятся сведения о целевой функции, в таблице 2 приводятся значения переменных задачи, а в таблице 3 показаны результаты поиска для ограничений задачи.

Рис. 11. Отчет по результатам решения задачи

Из этих таблиц видно, что в оптимальном решении:

-максимальный доход ($D$4) равен 99,17;

-объем выпуска продукта А ($B$3) равен 5,39;

-объем выпуска продукта В ($С$3) равен 1,83;

-расход ресурса Электроэнергия ($D$7) равен 29, статус ресурса

связанный, разница (остаток ресурса) 0;

-расход ресурса Сырье ($D$8) равен 18, статус ресурса связанный, разница (остаток ресурса) 0;

-расход ресурса Оборудование ($D$9) равен 16,39, статус ресурса

не связанный, разница (остаток ресурса) 6,611.

Первоначальная таблица рабочей книги заполняется результатами, полученными при решении (рис. 12).

Рис. 12. Результат поиска решения

29

8. Если в окне для просмотра результатов выбрать тип отчета Устойчивость, нажимаем кнопку ОК. В рабочей книге появится листОтчет

по	устойчивости, который	позволяет	проанализировать	изменение
параметров задачи (рис. 13).

Рис. 13. Отчет по устойчивости решения задачи

Отчет состоит из двух таблиц: в таблице 1 приводятся сведения о

чувствительности	решения к изменению	коэффициентов целевой
функции (cj), в	таблице 2 приводятся сведения	о чувствительности

решения задачи к изменению запасов сырья (bi).

Чувствительности решения к изменению коэффициентов целевой

функции. Отчет позволяет определить допустимые диапазоны изменения
коэффициентов		в	целевой	функции(рассматривая		каждый	из
коэффициентов отдельно) и их влияние на оптимальность полученного
ранее решения.	В	таблице отчетацелевой			коэффициент соответствует
коэффициенту	cj,	допустимое		увеличение ( Dc(j+) ) – максимально
возможное увеличение			коэффициентаcj,		а допустимое	уменьшение

( Dc(j-) ) - максимально возможное уменьшение коэффициента cj.

Для первого коэффициента целевой функции получен следующий диапазон изменения с1:

с1 = {c1 - Dc1(-) ; c1 + Dc1(+) }= {15 -10,71;15 +15}= {4,29;30}.

Для второго коэффициента целевой функции с2:

с2 = {c2 - Dc2(-) ; c2 + Dc2(+) }= {10 - 5;10 + 25}= {5;35}.

Таким образом, найденный оптимальный план выпуска продукции не будет меняться при изменении цены на единицу продукцииА в диапазоне от 4,29 до 30 денежных единиц и цены на единицу продукции В в диапазоне от 5 до 35 денежных единиц.

30

Чувствительности решения задачи к изменению запасов ресурсов

целесообразно проводить для связанных ресурсов(для примера Электроэнергия и Сырье). Отчет по устойчивости определяет интервалы изменения каждого из свободных членов системы ограничений(bi) исходной задачи линейного программирования, в которых оптимальный план двойственной задачи не меняется.

Свойство двойственных оценок утверждает, что изменение значений

величины b приводит к увеличению или уменьшениюF и это

i max

изменение определяется величиной yi.

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

отражает

значение

свободных

членов

системы

ограниченийbi,

допустимое

увеличение ( Db(+) )

–

максимально

возможное увеличение

i

коэффициента bi,

а

допустимое

уменьшение ( Db(-) )

-

максимально

возможное уменьшение коэффициента bi.

i

следующий

диапазон

Для

ресурса

Электроэнергия

получен

изменения b1:

;b + Db(+) }= {29 -11; 29 + 7}= {18;36}.

b1

= {b - Db(-)

1

1

1

1

Данный интервал позволяет определить величину изменения дохода

при изменении ресурса, т.е.

DF (-)

= Db(-)

× y

= 11 × 0,833 = 9,163 денежных единиц;

1

i

DF (+)

= Db(+)

× y

= 7 × 0,833 = 5,831 денежных единиц.

1

i

ресурсаЭлектроэнергия

При

изменении

запасов

в

пределах от

18 до 36 единиц значение целевой функции принимает значения от

90,01 (99,17 – 9,16) до 105 (99,17 + 5,83) денежных единиц.

Для ресурса Сырье получен следующий диапазон изменения b2: b2 = {b2 - Db2(-) ; b2 + Db2(+) }= {18 -10,82;18 +11}= {7,18; 29}.

Данный интервал позволяет определить величину изменения дохода при изменении ресурса, т.е.

DF (-) = Db1(-) × yi = 10,82 × 4,17 = 45,12 денежных единиц;

DF (+)	= Db(+) × y	i	= 11 × 4,17 = 45,87 денежных единиц.
	1				ресурсаСырье в пределах от
При	изменении			запасов

7,18 до 29 единиц значение целевой функции принимает значения от

54,05 (99,17 – 45,12) до 145,04 (99,17 + 45,87) денежных единиц.

31

ЗАДАНИЯ

Вариант 1

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 13
	Ресурс	Затраты ресурсов на единицу продукции
		Продукт С	Продукт D
	Электроэнергия	4	8
	Сырье	18	28
	Оборудование	10	18
	Цена единицы продукции	29	32

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 2

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 14
	Ресурс	Длительность обработки детали, мин
		Деталь С	Деталь D
	Станок 1	11	14
	Станок 2	15	20
	Станок 3	7	5
	Цена единицы продукции	31	35

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 3

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

Решить задачу линейного программирования в MS Excel и выполнить полный анализ полученных результатов.

32

			Таблица 15
	Ресурс	Трудоемкость обработки детали
		Деталь С	Деталь D
	Станок 1	4	4
	Станок 2	3	8
	Станок 3	1	3
	Прибыль	2	5

Вариант 4

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 16
	Ресурсы	Нормы расхода ресурса на 1 ед. изделия
		Изделие № 3	Изделие № 4
	Сталь марки А	1,2	2
	Сталь марки В	0	1
	Сталь марки С	1	1
	Прибыль	3	5

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 5

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 17
	Ресурсы	Затраты времени на обработку изделия, станко-ч
		С	D
	Фрезерное	3	2
	Токарное	2	3
	Сварочное	1	2
	Прибыль	9	9

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 6

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

33

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

			Таблица 18
	Ресурсы	Нормы затрат на одно изделие
		комод	стул
	Древесина:
	1-й вид	0,1	0,1
	2-й вид	0,4	0,1
	Трудоемкость (чел-ч.)	1,4	1,1
	Прибыль	9	4

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 7

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 19
	Вид корма	Ежедневное количество единиц корма
		бобер	кролик
	I	2	0
	II	3	2
	III	4	5
	Прибыль	14	10

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 8

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 20
	Производственные участки	Затраты времени на единицу продукции, н-ч
		лыжи	деревянный массажер
	А	5	3
	В	3	4
	С	0	1
	Прибыль	2	3

34

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 9

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

		Таблица 21
	Расход продуктов
Вид исходного продукта	на 1 т красок
	краска по дереву	краска по металлу
А	2	2
В	1	2
С	1	3
Оптовые цены	3	3

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

Вариант 10

В соответствии с данными варианта лабораторной работы 1,№ необходимо сформулировать экономико-математическую модель задачи двойственную к исходной и найти решение двойственной задачи.

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

			Таблица 22
	Ресурс	Нормы расхода ресурсов на единицу изделия
		Ковер С	Ковер D
	Труд	5	1
	Сырье	2	1
	Оборудование	4	2
	Цена	16	9

Решить задачу линейного программирования MSв Excel и выполнить полный анализ полученных результатов.

35

Контрольные вопросы

1.Раскройте основные понятия двойственного анализа.

2.Сформулируйте правила составления двойственной задачи.

3.Дайте определения теорем двойственного анализа.

4.Как с помощью двойственных оценок задачи линейного программирования оценить целесообразность включения в план новых изделий?

5. Назовите основные этапы решения задачи линейного программирования с помощью Microsoft Excel.

6.Какие таблицы составляют отчет о результатах решения задачи линейного программирования?

7.Как выполнить анализ чувствительности решения к изменению коэффициентов целевой функции?

8.Как выполнить анализ чувствительности решения задачи к изменению запасов сырья?

36

Лабораторная работа № 3

Использование Microsoft Excel для решения транспортной задачи

Цель	работы: приобретение практических	навыков	применения
методов	линейного программирования для	решения	транспортной
задачи.
	Содержание

Изучаются вопросы:

1.Транспортная задача. Общий вид. Основные понятия и определения.

2.Решение транспортной задачи в Microsoft Excel.

Выполняется вариант задания.

					Указания
	Рассмотрим		транспортную			задачу		по	критерию		стоимости,
которую можно сформулировать следующим образом.
	В m пунктах отправления A1, A2, …, Am, которые в дальнейшем будем
называть		поставщиками,			сосредоточено			определенное		количество
единиц		некоторого			однородного		продукта, которое			обозначим
аi (i = 1, 2, ..., m). Данный продукт потребляется в n пунктах B1, B2, …,
Bn,	которые		будем	называть		потребителями; объем				потребления
обозначим bj (j = = 1, 2, ..., n). Известны расходы на перевозку единицы
продукта		из пункта Аi		в	пункт Вj,	которые		равны cij и		приведены в
матрице транспортных расходов С = (cij).
	Требуется составить такой план прикрепления потребителей к
поставщикам, т.е. план перевозок, при котором весь продукт вывозится
из	пунктов Аi		в пункты Вj в соответствии					с	потребностью		и общая
величина транспортных издержек будет минимальной.

Обозначим количество продукта, перевозимого из пункта Аi в пункт Вj, через xij. Совокупность всех переменных xij для краткости обозначим

X , тогда целевая функция задачи будет иметь вид

		m	n
f (	X	)= å åcij xij ® min ,							(1)
		i =1 j =1
а ограничения выглядят следующим образом:
		m
		åxij	= b j ;	j =		1, n		;	(2)
		i=1
		n
		åxij	= ai ;	i =	1, m		;		(3)
		i=1

xij ³ 0.

37

Условия (2) означают полное удовлетворение спроса во всех пунктах потребления; условия (3) определяют полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи(1) -

(3) является условие баланса:

m	n
åai	= åb j .	(4)
i =1	j =1
Транспортная задача, в	которой имеет	место равенство(4),

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

специальные, менее громоздкие методы ее решения.
Для	решения	транспортной	задачи	по	критерию	стоимости

используем инструмент Excel Поиск решений.

Для запуска этого инструмента нужно выбрать На вкладкеДанные выбираем команду Поиск решения (если команда отсутствует в окне параметров Excel выберете Надстройки ® Перейти и установите Поиск

решения).

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

Пример. Имеется четыре пункта производства продукции(Завод 1, Завод 2, Завод 3, Завод 4). Заводы способны ежемесячно произвести продукцию, которая необходима для строящихся объектов, в размере 800, 400, 600 и 500 тыс. т продукции соответственно. Существует три пункта потребления этой продукции: Объект 1, Объект 2, Объект 3.

Ежемесячные потребности этих пунктов в продукции составляют соответственно 1100, 700, 500 тыс. т. Стоимость перевозок (в рублях за тыс. т) автомобильным транспортом известна и приведена в табл. 23.

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

2. Для работы Объекта 3 обязательно необходима продукция Завода 1 в объеме не менее 50 тыс. т и для Объекта 2 – продукция Завода 3 в объеме не менее 30 тыс. т. Каковы транспортные затраты нового плана?

	38
	Строящиеся объекты			Таблица 23
Пункт назначения				Объем
Пункт отправления	Объект 1	Объект 2	Объект 3	производства
Завод 1	3,9	4,2	2,7	800
Завод 2	5	6	4,1	400
Завод 3	6,4	7,1	4,1	600
Завод 4	7,4	9,4	8,3	500
Ежемесячные потребности объектов	1100	700	500	2300

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

4.При утверждении нового плана выяснилось, что из-за ремонта дороги затраты на переводку к Объекту 1 увеличились на 0,8 руб./тыс. т с каждого завода. На сколько при этом возрастут транспортные расходы?

Решение:

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

Составим

экономико-математическую

модель

задачи. Пусть xij –

количество

строительных

материалов

в

тысячах

тонн, перевозимого с

i-го завода изготовителя наj-й строящийся объект. Ограничения,

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

будут двух видов: по

перевозке

всего

количества строительных

материалов

и

готового

к

перевозке

на

каждом. Тогдазаводе,

математическая модель задачи записывается в следующем виде:

Z = 3,9x11 + 4,2х12 + 2,7х13 + 5х21 + 6х22 + 4,1х23 + 6,4х31 + 7,1х32 +

+ 4,1х33 + 7,4х41 + 9,4х42 + 8,3х43 ® min

ìx11 + x12 + x13 = 800

ïx

+ x

22

+ x

23

= 400

ï 21

+ x

+ x

ïx

= 600

ï 31

32

33

ïx41 + x42 + x43 = 500

1100 .

íx

+ x

21

+ x

+ x

41

=

ï 11

31

ï

+ x22 + x32 + x42 = 700

ïx12

x

+ x

23

+ x

+ x

43

= 500

ï 13

33

ïx

³ 0

î ij

39

Набор значений переменныхxij – это и есть план перевозок. Поскольку переменные имеют по два индекса, план удобнее записывать не в виде вектора, а в виде матрицы (или гистограммы):

æ x11	x12	x13	ö
ç x21	x22	x23	÷
X = ç x	x	x	÷ .
ç 31	32	33	÷
ç	x42	x43	÷
è x41			ø

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

Целевая функция задачи представляет собой сумму произведений стоимостей перевозки 1 т груза на объем перевозки для каждой пары поставщика-потребителя, т.е. общую суммарную стоимость всех перевозок, соответствующих плану Х. Эту суммарную стоимость следует минимизировать при условии, что будут выполнены все ограничения.

Ограничения на перевозки можно разбить на две группы . Первая группа - это верхние четыре неравенства. В каждое из них входят переменные с одним и тем же первым индекс, ом различными вторыми индексами, т. е. переменные, соответствующие одному и тому же пункту производства, но различным пунктам потребления. Каждое из этих неравенств говорит о том, что суммарный объем всех грузов, вывозимых из одного и того же пункта производства в разные пункты потребления, равен количеству продукции, которое может быть произведено в данном пункте производства. Вторая группа - это следующие три равенства. В каждое из них входят переменные с одним и тем же вторым индексом, но разными первыми индексами. Эти переменные соответствуют одному пункту потребления, но разным пунктам производства. Такое равенство утверждает, что объем всего груза, который свозится из разных пунктов производства в один и тот

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

Для	решения поставленной задачи инструментомПоиск решения
создадим модель, представленную на рис. 14.
Для	запуска инструмента Поиск решения необходимо на вкладке

Данные выбирать команду Поиск решения (если команда отсутствует, то в окне параметров Excel выберете Надстройки ® Перейти и установите

Поиск решения).

40

Рис. 14. Модель транспортной задачи

В окне установите следующие параметры:

оптимизировать целевую функцию в ячейке $B$14 до Минимум; изменяя ячейки переменных $B$8:$D$11;

метод решения: Поиск решения линейных задач симплекс-методом.

список ограничений (вводится с помощью кнопки Добавить):

$E$8:$E$11=$F$8:$F$11; $B$12:$D$12<=$B$13:$D$13; $B$8:$D$11>=0.

Окно Поиска решения с заполненными параметрами представлено на рис. 15.

Рис. 15. Окно Параметры поиска решения

Результат решения задачи приведен в табл. 24.

41

Таблица 24

Затраты на перевозку,

Объект 1

Объект 2

Объект 3

руб./тыс. т.

Завод 1

3,9

4,2

2,7

Завод 2

5

6

4,1

Завод 3

6,4

7,1

4,1

Завод 4

7,4

9,4

8,3

Объем перевозок,

Объект 1

Объект 2

Объект 3

Объем

Объем

тыс. т

перевозок

производства

Завод 1

100

700

0

800

800

Завод 2

400

0

0

400

400

Завод 3

100

0

500

600

600

Завод 4

500

0

0

500

500

Факт. Спрос

1100

700

500

Потребление (спрос)

1100

700

500

Целевая функция

11720

Разработанный

оптимальный

план

обеспечивает

минимальные

затраты

на

транспортировку

продукции

из

четырех

пунктов

производства в три пункта потребления. На основании решения

транспортной

задачи

определены

поставки

каждого

завода

на

строящиеся

объекты,

производственные

программы

по

заводам

изготовителям

и

резервы

производственных

мощност. Всей

предприятия свои мощности используют полностью. Обеспечение

строящихся объектов происходит в полном объеме.

В результате решения задачи предложен следующий план перевозок

продукции с заводов на пункты потребления:

æ100

700

0

ö

ç

0

0

÷

ç400

÷

матрица перевозок: X = ç

100

0

500

÷ ;

ç

÷

ç

500

0

0

÷

è

ø

гистограмма плана транспортировки (рис. 16); гистограмма затрат на транспортировку (рис. 17).

Минимальные затраты на транспортировку всех грузов составят 11720 тыс. руб. (табл. 24). Затраты на заводах изготовителях и при транспортировке на строящиеся объекты составят (рис. 17)

сЗавода 1 – 3300 тыс. руб.;

сЗавода 2 – 2000 тыс. руб.;

сЗавода 3 – 2690 тыс. руб.;

сЗавода 4 – 3700 тыс. руб.

42

Рис. 16. Гистограмма плана транспортировки грузов

Рис. 17. Гистограмма затрат на перевозку

2. Дополнительные условия задачи требуют поставки груза с Завода 1 на Объект 3 груза в объеме не менее 50 тыс. т. и с Завода 3 на Объект 2 – не менее 30 тыс. т.

Чтобы добавить данные условия в подготовленную модель задачи,

необходимо вызвать надстройкуПоиск		решения и добавить два
ограничения:
$D$8 >= 50	$C$10 >= 30.

и найти новое решение (кнопка Найти решение). Новый план перевозок представлен в табл. 25.

43

Таблица 25

Затраты на перевозку,		Объект 1	Объект 2	Объект 3
руб./тыс. т.
Завод 1	3,9		4,2	2,7
Завод 2	5		6	4,1
Завод 3	6,4		7,1	4,1
Завод 4	7,4		9,4	8,3
Объем перевозок,		Объект 1	Объект 2	Объект 3	Объем	Объем
тыс. т					перевозок	производства
Завод 1		80	670	50	800	800
Завод 2	400		0	0	400	400
Завод 3	120		30	450	600	600
Завод 4	500		0	0	500	500
Факт. Спрос		1100	700	500
Потребление (спрос)	1100		700	500
Целевая функция	11787

После решения выполнить план поставок с учетом требований по строящимся объектам получена следующая матрица перевозок

æ 80		670	50	ö
ç		0	0	÷
ç400				÷
X = ç	120	30	450	÷	,
ç				÷
ç	500	0	0	÷
è				ø

а затраты на перевозку возросли на11787 – 11720 = 67 тыс. руб. после решения выполнить план поставок с учетом требований по строящимся объектам.

3. Если необходимо доставка груза с каждого завода на каждый строящийся объект в объеме 50 тыс. т добавим в окно Поиска решения (рис. 15) условие

$B$8:$D$11 >= 50.

В результате новая матрица перевозок

æ200		550	50	ö
ç		50	50	÷
ç300				÷
X = ç	200	50	350	÷
ç				÷
ç	400	50	50	÷
è				ø

аитоговые затраты на перевозку составят 12145 тыс. руб.

4.Для ответа на3 вопрос сначала изменим цены перевозки на Объект 1 на 0,8 руб./тыс. т. и позволим Excel пересчитать текущие издержки. Получаем общие издержки в 12667 тыс. руб., что выше, чем в последнем плане перевозок.

44

ЗАДАНИЯ

Вариант 1

На оптовом складе имеется три холодильника (А1, А2, А3), вмещающих мороженную рыбу в количествах320 т, 280 т, 250 т соответственно. Необходимо доставить рыбу в пять магазинов(В1, В2, В3, В4, В5) в количествах 140 т, 110 т, 230 т, 220 т, 150 т соответственно.

Стоимости перевозки 1 т	рыбы	из холодильника			в магазин заданы
в табл. 26.						Таблица 26
Стоимость перевозок, тыс. руб.
Пункт назначения				Магазины
Пункт отправления	В1	В2		В3	В4		В5
А1	20	23		20	15		24
А2	29	15		16	19		29
А3	6	11		10	9		8

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

2.Перевозка рыбы со складаА2 в магазин В2 невозможна в связи с ремонтом моста. Как изменяться транспортные издержки?

3.	Для	эффективной работы магазина			необходимо как	минимум
5 т доставки рыбы с каждого холодильника. Выполните расчет нового
плана перевозок и определите итоговые транспортные затраты.
4. В летний период стоимость перевозок возрастает на 1 тыс. руб. по
всем объектам. На сколько при этом возрастут суммарные транспортные
расходы?
				Вариант 2
Четыре			предприятия	данного	экономического	района	для
производства продукции используют некоторое сырье. Спрос на сырье
каждого из			предприятий	соответственно	составляет: 120, 50, 190 и
110	усл.	ед.	Сырье сосредоточено в		трех местах. Предложения

поставщиков сырья равны: 160, 140 и 170 усл. ед. Стоимость перевозки единицы сырья известны и заданы в табл. 27.

Таблица 27

Тарифы перевозок, усл. руб.

Пункт назначения			Предприятия
Пункт отправления	Предприятие 1		Предприятие 2		Предприятие 3		Предприятие 4
Поставщик 1	7		8		1		2
Поставщик 2	4		5		9		8
Поставщик 3	9		2		3		6
1. Составьте	план	перевозок, при		котором		общая стоимость

перевозок минимальна.

45

2.Необходимо обеспечить поставку сырья Поставщикаот 1 на Предприятие 2 в объеме не менее10 усл. ед. Как изменяться транспортные издержки?

3.На каждое предприятие сырье необходимо завозить от каждого поставщика в объеме не менее5 усл. ед. Каковы транспортные затраты нового плана?

4.В связи с ремонтом дороги перевозка по прямому маршруту от

Поставщика 3 на Предприятие 2 и Предприятие 4 невозможна. Объездной

маршрут увеличивает тариф перевозок на 2 тыс. руб. На сколько при этом возрастут транспортные расходы?

Вариант 3

Имеются три склада, из которых необходимо вывезти муку в четыре торговые точки. Стоимость перевозки 1 т муки, запасы муки на складах и требуемые объемы продаж в торговых точках представлены в табл. 28.

Исходные данные					Таблица 28
Пункт назначения		Торговые точки			Объем
Пункт отправления	Т1	Т2	Т3	Т4	запаса муки
Склад 1	2	3	4	3	90
Склад 2	5	3	1	2	30
Склад 3	2	1	1	4	40
Ежемесячные потребности объектов	70	30	20	40

1.Определить оптимальный план снабжения, при котором спрос на муку удовлетворяется с минимальными затратами на перевозку.

2.В связи с ремонтом моста перевозка муки со Склада 1 в Торговую точку Т1 невозможна. Как изменяться транспортные издержки?

3.	Для эффективной работы торговой точки		необходимо как
минимум по 2 т доставки муки с каждого склада. Каковы транспортные
затраты нового плана?
4.	Ремонт дороги увеличивает стоимость перевозок на1 усл. д.е. для
торговой		точки 3. Т На сколько при этом возрастут	суммарные
транспортные расходы?

Вариант 4

На складах имеются запасы продукции в количествах90, 400, 110 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 140, 300, 160 т соответственно. Расходы по перевозке 1 т продукции представлены в табл. 29.

1.Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной.

2.В связи с ремонтом моста перевозка продукции со Склада 1 Потребителю В3 невозможна. Как изменяться транспортные издержки?

46

Расходы по перевозке 1 т продукции, усл. ед.				Таблица 29
Пункт назначения		Потребители
Пункт отправления	В1	В2		В3
Склад 1	2	5		2
Склад 2	4	1		5
Склад 3	6	6		8

3.Каждый потребитель заключил договор на минимальный объем доставки продукции с каждого склада, который составляет 4 т. Каковы транспортные затраты нового плана?

4.Стоимость перевозок соСклада 3 во все торговые точки уменьшилась на 1 усл. д.е. Как изменятся суммарные транспортные расходы?

Вариант 5

У поставщиков A1, A2, A3, находится соответственно 500, 400, 700 единиц однотипной продукции, которая должна быть доставлена потребителям B1, B2, B3, B4 в количестве 400, 200, 400, 600 единиц соответственно. Стоимость доставки единицы продукции от поставщика к потребителю приведена в табл. 30.

Стоимость доставки единицы продукции, ден. ед.				Таблица 30
Пункт назначения		Потребители
Пункт отправления	В1	В2	В3		В4
А1	14	18	13		7
А2	11	11	9		8
А3	12	17	11		16

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

2.Для работы Потребителю В2 обязательно необходима продукция Поставщика 1 и Поставщика 3 в объеме не менее 50 тыс. т. Каковы транспортные затраты нового плана?

3.Минимальный объем доставки от каждого поставщика каждому потребителю должен составлять10 единиц продукции. Каковы транспортные затраты нового плана?

4.Из-за ремонта дороги стоимость перевозок сПункта отправления А1 Потребителю 3 увеличилась до18 усл. д.е. Как изменятся суммарные транспортные расходы?

47

Вариант 6

Запасные части для предприятий железнодорожного транспорта

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

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

		Исходные данные					Таблица 31
	Пункт назначения			Пункт потребления			Объем, т
Пункт отправления			П1	П2	П3	П4
	Завод 1		3	5	4	7	520
	Завод 2		10	11	9	12	350
	Завод 3		8	5	6	4	730
Потребности объектов, т			436	320	490	354
	1. Требуется найти оптимальное решение доставки запасных частей
от	производителя	к	потребителям, инимизирующее				стоимость
доставки.
	2. Потребитель 1 заключил договор на поставку запасных частей с
Заводом 2 в объеме равном 40 т и Заводом 3					в объеме – 30 т. Сколько

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

3. Пусть минимальный объем доставки с каждого завода каждому потребителю должен составлять не менее30 т запасных частей. Каковы транспортные затраты нового плана?

4. В связи с ремонтом дороги затраты Потребителю 3 возросли на 2 тыс. руб. Как изменятся суммарные транспортные расходы?

Вариант 7

На складах 1, 2, 3 имеются запасы продукции в количествах 180, 300, 120 т соответственно. Потребители В1, В2, B3 должны получить эту продукцию в количествах 110, 350, 140 т соответственно. Расходы по перевозке 1 т продукции представлены в табл. 32.

Расходы по перевозке 1 т продукции, усл. ед.				Таблица 32
Пункт назначения		Потребители
Пункт отправления	В1	В2		В3
Склад 1	2	5		2
Склад 2	7	7		13
Склад 3	3	6		8

48

1.Найти такой вариант прикрепления поставщиков к потребителям, при котором сумма затрат на перевозки была бы минимальной.

2.В связи с ремонтом моста доставка продукцииСкладасо 1 Потребителю 3 невозможна. Каковы транспортные затраты нового плана?

3.Минимальный объем доставки с каждого склада каждому потребителю должен составлять не менее 30 т продукции. Каковы будут транспортные затраты для данного плана перевозок?

4. Стоимость перевозок со Склада 3 всем поставщикам уменьшилась на 1 усл. д. е. Как изменятся суммарные транспортные расходы?

Вариант 8

Фирма по доставке цветов имеет четыре постоянных клиента. Цветы поставляются из четырех складов, где запас цветов составляет 10, 20, 10, 30 т соответственно. Фирма получила заказ от клиентов : клиент А – 13 т, клиент В – 18 т, клиент С – 20 т, клиент D – 19 т. Удельные затраты на поставку цветов от склада каждому клиенту представлены в табл. 33.

Удельные затраты на поставку цветов, усл. ед.				Таблица 33
Пункт назначения		Клиенты
Пункт отправления	Клиент А	Клиент В	Клиент С	Клиент D
Склад 1	1,22	5,91	8,41	4,12
Склад 2	2,13	0,36	3,63	9,08
Склад 3	0,85	3,45	3,47	5,36
Склад 4	1,24	7,87	2,24	2,69

1.Определить объем поставки из каждого склада каждому клиенту так, чтобы минимизировать суммарные затраты.

2.Менеджер по поставкам получил указание о том, что со Склада 2 поставка цветов Клиенту В может составлять не более 15 т. Каковы транспортные затраты нового плана?

3.Пусть для эффективной работы каждого клиента и склада необходима доставка и отправка не менее 2 т цветов. Каковы будут транспортные затраты для данного плана перевозок?

4.В связи с ремонтом дороги транспортные затраты для Клиента С возросли на 0,5 усл. ед. Как изменятся суммарные транспортные расходы?

Вариант 9

Однородный груз сосредоточен у 3 поставщиков в объемах 60, 120 и 100 т продукции. Данный груз необходимо доставить4 потребителям в объемах 20, 110, 40 и 110 т соответственно. Известна стоимость перевозки единицы груза от каждого поставщика каждому потребителю

(табл. 34).

49

Стоимость перевозки единицы груза, усл. ден. ед.						Таблица 34
Пункт назначения			Потребители
Пункт отправления	Потребитель 1	Потребитель 2		Потребитель 3	Потребитель 4
Поставщик 1	1	2		5		3
Поставщик 2	1	6		5		2
Поставщик 3	6	3		7		4

1. Требуется составить такой план перевозок, при котором запасы

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

2.В связи с ремонтом дороги поставка груза от Поставщика 2 до Потребителя 4 стала невозможной. Каковы транспортные затраты нового плана?

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

4.В связи с ремонтом моста транспортные затраты для Поставщика 1 возросли на 2 усл. ед. Как изменятся суммарные транспортные расходы?

Вариант 10

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

	Исходные данные задачи					Таблица 35
	Пункт назначения		Пункт потребления			Объем, т
	Пункт отправления	П1	П2	П3	П4
	Склад 1	40	51	82	66	127
	Склад 2	70	35	72	25	152
	Склад 3	27	40	40	52	225
	Склад 4	55	8	52	12	175
	Потребности объектов, т	134	108	248	189

1. Требуется определить, в каком объеме необходимо поставлять минеральные удобрения со складов потребителям с минимальными суммарными транспортными расходами.

2. Потребитель 2 заключил договор	на	поставку удобрений	со
Складом 2 в объеме равном 30 т и Складом 3	в объеме – 20 т. Сколько
составят при выполнении данного договора		суммарные затраты	на

50

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

3.Предположим, что минимальный объем доставки со склада потребителю должен составлять не менее 11 т удобрений. Каковы будут транспортные затраты для данного плана перевозок?

4.Склад 4 был перенесен на новые площади и затраты на перевозку

для каждого поставщика снизились на3 д.е. Как изменятся суммарные транспортные расходы?

Контрольные вопросы

1.Дайте определение классической транспортной задачи.

2.Какова математическая запись целевой функции и ограничений классической транспортной задачи?

3.В чем отличие закрытой транспортной задачи от открытой?

4.Когда транспортная задача не имеет решений?

5. Назовите основные этапы решения транспортных задач и раскройте их смысл.

6.Каким образом формируется транспортная модель в электронной таблице Excel?

7.Этапы решения транспортной задачи в Excel.