Основные виды экономических задач, сводящихся к ЗЛП

Задача о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Будем обозначать эту продукцию . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно ; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации
, т.е. — вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции >j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров  нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.
Так как - цена реализации единицы j-й продукции, цена реализованных единиц будет равна , а общий объем реализации .
Это выражение — целевая функция, которую нужно максимизировать.
Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-горесурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц:

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

(1.33)

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

(1.34)
(1.35)

Так как переменные входят в функцию  и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (1.33)-(1.35) – задача линейного программирования.

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

 

Пример. Для откорма животных используется три вида комбикорма: А, В и С. Каждому животному в сутки требуется не менее 800 г. жиров, 700 г. белков и 900 г. углеводов. Содержание в 1 кг. каждого вида комбикорма жиров белков и углеводов (граммы) приведено в таблице:

Содержание в 1 кг.

Комбикорм

 

	А	В	С
Жиры	320	240	300
Белки	170	130	110
Углеводы	380	440	450
Стоимость 1 кг	31	23	20

Сколько килограммов каждого вида комбикорма нужно каждому животному, чтобы полученная смесь имела минимальную стоимость?
Математическая модель задачи есть:
- количество комбикорма А,В и С. Стоимость смеси есть:

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

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

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

Пример. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:

Рабочие

Станки

 

	С1	С2	С3	С4
Р1	2,3	1,9	2,2	2,7
Р2	1,8	2,2	2,0	1,8
Р3	2,5	2,0	2,2	3,0
Р4	2,0	2,4	2,4	2,8

Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент?
Обозначим за - переменные, которые принимают значения 1, если i-й рабочий работает на j-м станке. Если данное условие не выполняется, то . Целевая функция есть:
.
Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть

Кроме того, каждый станок обслуживает только один рабочий:

Кроме того, все переменные должны быть целыми и неотрицательными: .

 

Транспортная задача.

 

Частным случаем задачи линейного программирования является транспортная задача.
ТЗ в общем виде состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления  в  пунктов назначения _n. В качестве критерия оптимальности можно взять минимальную стоимость перевозок всего груза, либо минимальное время его доставки.
Рассмотрим задачу с первым критерием, обозначив через сn тарифы перевозок единицы груза из i-го пункта отправления в j-й пункт назначения, через a_i - запасы груза в пункте А_i через b_j - потребности в грузе пункта  - количество единиц груза, перевозимого из i-го пункта в j-й пункт.
Составим математическую модель задачи. Так как от i-гo поставщика к j-му потребителю запланировано к перевозке  единиц груза.

Таблица 2.1

Поставщики	Потребители				Запасы
	B1	B2	...	Bn
А1	C11 X11	C12 X12	...	C1n X1n	a1
А2	C21 X21	C22 X22	...	C2n X2n	a2
...	...	...	...	...	...
Аm	Cm1 Xm1	Cm2 Xm2	...	Cmn Xmn	am
Потребности	b1	b2	...	bn	∑ai=∑bj

 

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

(2.11)

при условиях:

    (2.12)
      (2.13)

(2.14)

 

Всякое неотрицательное решение систем уравнений (2.12)-(2.14), определяемое матрицей , называют опорным планом ТЗ, а план , при котором функция Z принимает минимальное значение - называется оптимальным планом ТЗ.
Все данные, а затем и опорный план, удобно занести в распределительную таблицу.
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения совпадают, т.е.

(2.16)

то модель ТЗ называется закрытой.

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

Доказательство:

Тогда величины являются планом, так как они удовлетворяют, системе ограничений (2.12), (2.13). Действительно, подставляя значения  в (2.12) и (2.13), имеем

 

 

Выберем из значений  наибольшее  и заменим в линейной функции (2.11) все коэффициенты на  тогда, учитывая (2.12), получаем

Выберем из значений наименьшее  и заменим в линейной функции все коэффициенты на  тогда, имеем

Объединяя два последних неравенства в одно двойное, окончательно получаем , т. е. линейная функция ограничена на множестве планов транспортной задачи.
Ч.Т.Д.
Если общее количество груза в пунктах отправления и общая потребность в нем в пунктах назначения не совпадают ТЗ называется открытой. Введением фиктивного потребителя (если ), или фиктивного отправителя (если ), любая задача приводится к закрытой модели (во всех фиктивных ячейках таблицы полагают ). Для разрешимости задачи равенство (2.15) является необходимым и достаточным условием.
Нахождение опорных и оптимального планов ТЗ можно вести симплексным методом, но, ввиду специфики ТЗ, и большого ее прикладного значения, разработаны специальные методы.
Нахождение опорных планов ТЗ можно осуществить одним из пяти методов: северо-западного угла, минимальной стоимости, аппроксимации Фогеля, двойного предпочтения и дельта-метода.

 

Методы составления опорного плана транспортной задачи.

 

Метод северо-западного угла

Пусть условия транспортной задачи заданы таблице 2.2.
Не учитывая стоимости перевозки единицы груза, начинаем удовлетворение потребностей первого потребителя  за счет запаса поставщика  Для этого сравниваем  с ,  меньший из объемов, т. е. = 100 ед. записываем в левый нижний угол клетки А₁B₁. Запасы первого поставщика полностью израсходованы, по этому остальные клетки первой строки прочеркиваем. Потребности  остались неудовлетворенными на . Сравниваем этот остаток с запасами поставщика : так как , то  ед. записываем в клетку , чем полностью удовлетворяем потребности потребителя , а оставшиеся клетки в первом столбце прочеркиваем.

Таблица 2.2

Поставщики	Потребители					Запасы
	10 100	7 -	4 -	1 -	4 -	100
	2 100	7 150	10 -	6 -	11	250
	8 -	5 50	3 100	2 50	2 -	200
	11 -	8	12	16 50	13 250	300
Потребности	200	200	100	100	250	850

 

У поставщика  осталось 150 ед. груза. Удовлетворяем потребителя за счет оставшегося у поставщика груза. Для этого сравниваем этот остаток с потребностями потребителя : , записываем 150 ед. в клетку  и, так как запасы  полностью израсходованы, прочеркиваем остальные клетки второй строки. Потребности  остались неудовлетворенными на 50 ед. Удовлетворяем их за счет поставщика и переходим к удовлетворению  за счет остатка, имеющегося у поставщика , и т. д. Процесс продолжаем до тех пор, пока не удовлетворим всех потребителей за счет запасов поставщиков. На этом построение первоначального опорного плана заканчивается.
Таким образом, в табл. в правых верхних углах клеток стоят числа, определяющие стоимость перевозки единицы грузов, а в левых нижних углах — числа, определяющие план перевозок, так как их сумма по строкам равна запасам соответствующего поставщика, а сумма по столбцам — потребности соответствующего потребителя.
Проверим, является ли план, построенный в табл. 2.2, опорным. Видим, что, начиная движение от занятой клетки A1B1, вернуться не только в нее, но и в любую другую занятую клетку, двигаясь только по занятым ячейкам, невозможно. Следовательно, план является опорным. В то же время план невырожденный, так как содержит точно  занятых клеток.
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы груза не учитывалась, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Поэтому рассмотренный метод используется при вычислениях-с помощью ЭВМ.
Найдем общую стоимость составленного плана как сумму произведений объемов перевозок, стоящих в левом углу занятых клеток, на соответствующие стоимости в этих же ячейках:
Если при составлении опорного плана учитывать стоимость перевозки единицы груза, то, очевидно, план будет значительно ближе к оптимальному.

Пример 1

 

 

Методом северо-западного угла составить опорный план перевозок груза из трех пунктов отправления с запасами 30, 48, 24 т в четыре пункта назначения с потребностями 18, 27, 42, 15т. Тарифы перевозок  (в ден/ед.) из  приведены в матрице.

 

Решение. Составим распределительную таблицу (табл. 2.2), в которой последовательно, начиная с верхнего левого угла (ячейка , ) и двигаясь по диагонали таблицы, заполним клетки до A₃ , B₄.

Таблица 2.3

 

					Запасы
	13 18	7 12	11	5	30
	11	8 15	13 33	7	48
	6	10	12 9	9 15	24
Потребности	18	27	42	15	102

 

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

Метод минимальной стоимости

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел , или . Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.
Составим с помощью этого метода опорный план уже рассмотренной задачи. Запишем ее условие в таблицу (табл. 2.4). Выбираем в таблице наименьшую стоимость (это стоимость, помещенная в клетке
, ) так как = , 100 ед. груза помещаем в этой клетке и исключаем из рассмотрения первую строку и четвертый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке , и в клетке , . Заполняем любую из них, например , . Имеем , следовательно, записываем в нее  и исключаем из рассмотрения столбец
. В клетку , записываем  ед. и исключаем из рассмотрения строку . В оставшейся таблице стоимостей снова выбираем наименьшую стоимость и продолжаем процесс до тех пор, пока все запасы не будут распределены, а потребности удовлетворены. В результате получен план
,
остальные значения переменных равны нулю.

Таблица 2.4

 

Поставщики	Потребители					Запасы
	10	7	4	1 100	4	100
	2 200	7 50	10	6	11	250
	8	5	3	2	2 200	200
	11	8 150	12 100	16	13 50	300
Потребности	200	200	100	100	250	850

 

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

Пример 2

 

 

Решим методом минимальной стоимости.
Опорный план по этому методу составлен в таблице 2.5.

Таблица 2.5

 

					Запасы
	13	7 15	11	5 15	30
	11	8 12	13 36	7	48
	6 18	10	12 6	9	24
Потребности	18	27	42	15	102

 

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

 

Метод аппроксимации Фогеля

Данный метод состоит в следующем:

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

Процесс продолжается до тех пор, пока все грузы не будут развезены по потребителям. Данный метод в ряде задач приводит к оптимальному плану. Решим этим методом задачу из примера 1. (см. табл.2.6).

 

Таблица 2.6

 

					Запасы
	13	7 15	11	5 15	30	2,2,4,B
	11	8 12	13 36	7	48	1,1,5,B
	6 18	10	12 6	9	24	3,1,2,B
Потребности	18	27	42	15	102
	5,B	1,2,B	1,1,1,B	2,B

 

На первом шаге заполняем клетку
, исключаем 1-ый столбец, отметив в дополнительной строке буквой «В» факт выполнения заказа пункта . Находим новые разности минимальных тарифов по строкам (в столбцах они не изменились) и в 1-ой строке и в 4-ом столбце. Заполняем клетку и исключаем 4-й столбец и т.д. В конце остается последовательно заполнить клетки 3-го столбца остатками запасов в . Составленный опорный план дает значение .

Метод двойного предпочтения

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

 

Пример 3

 

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

Таблица 2.7

 

Поставщики	Потребители					Запасы
	10	7	4	1	4	100
	2	7	10	4	11	250
	8	5	3	2	2	200
	11	8	12	16	13	300
Потребности	200	200	100	100	250	850

 

Сначала, отмечаем знаком V ячейку с наименьшей стоимостью в каждом столбце, затем - в каждой строке (табл. 2.8).

Таблица 2.8

 

Поставщики	Потребители					Запасы
	10	7	4	1 VV	4	100
	2 VV	7	10	4	11	250
	8	5 V	3 V	2 V	2 VV	200
	11	8 V	12	16	13	300
Потребности	200	200	100	100	250	850

 

Ячейки  имеют отметку , следовательно, с них и начинаем заполнение. Затем заполняем ячейку (т.к. в столбце нет ни одной ячейки с отметкой ). В оставшейся части таблицы последовательно заполняем ячейки по минимальной стоимости  . План, полученный в табл. 2.9, является вырожденным опорным планом.

Таблица 2.9

 

Поставщики	Потребители					Запасы
	10	7	4	1 100	4	100
	2 200	7	10 50	4	11	250
	8	5	3	2	2 200	200
	11	8 200	12 50	16	13 50	300
Потребности	200	200	100	100	250	850

 

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

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

 

 

Оптимальность плана транспортной задачи.

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

Пусть одним из рассмотренных в п.2.6 методов найден опорный план, содержащий  занятых клеток (в некоторых из них могут стоять нули). Поставим в соответствие каждому пункту отправления некоторое число  и каждому пункту назначения - число . Эти числа назовем потенциалами, соответственно, пунктов отправления и пунктов назначения.

Вопрос об оптимальности опорного плана решает следующая теорема:

Теорема 5. Если для некоторого плана ) транспортной задачи выполняются условия:

1. для  (для занятых клеток), (2.16)
2. для  (для свободных клеток), (2.17)

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

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

Для «улучшения» опорного плана (при невыполнении условия (2.17)) выбирают свободную клетку с  и строят для нее цикл пересчета (сдвига).

Циклом называют замкнутую ломаную линию, все вершины которой лежат в занятых ячейках, кроме одной, расположенной в свободной клетке, подлежащей заполнению, а звенья параллельны строкам и столбцам, причем в каждой строке (столбце) лежит не более 2-х вершин. Всем вершинам поочередно приписывают знаки «+» и «-», начиная со свободной клетки.
Далее, в свободную клетку помещают груз величиной λ, равной минимальному значению из всех чисел в отрицательных ячейках цикла. Во все положительные клетки прибавляется λ, из отрицательных - вычитается λ (сдвиг по циклу). Нетрудно подсчитать, насколько изменится (уменьшится) стоимость перевозок при новом плане:

, где - сумма тарифов в положительных вершинах, - в отрицательных вершинах цикла.
Новый опорный план снова проверяют на оптимальность с помощью системы уравнений потенциалов.
Заметим, что в результате пересчета по циклу может оказаться число занятых клеток меньше, чем  (план называется вырожденным). В этом случае следует заполнить числом «0» пустую клетку, имеющую минимальный тариф, и не образующую с занятыми клетками замкнутого прямоугольного контура.

 

 

Пример 1

Проверить оптимальность опорного плана ТЗ, решенной, в примере 6.
Решение. Составляем систему уравнений потенциалов:

 

 

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

Таблица 2.10

 

					Запасы
	13	7 15-	11 +	5 15	30
	11	8 12+	13 36 -	7	48
	6 18	10	12 6	9	24
Потребности	18	27	42	15	102

 

при этом будет  

В системе потенциалов для этого плана лишь 1-ое уравнение заменялся равенством .
Тогда, положив , находим  
Убеждаемся, что для всех свободных клеток выполняется условие (2.17). Следовательно, план и  

 

 

Свойство 1. Если, для некоторого оптимального плана

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

 

Пример 2.

 

Проверить оптимальность ТЗ, определенную таблицей (табл.2.11).

Таблица 2.11

 

	2	7	3	6	2	50
	9	4	5	7	3	50
	5	7	6	2	4	50
	10	40	20	60	20	150

 

Решение. Ведем построение опорного плана методом наименьшей стоимости (таблица 2.12)

Таблица 2.12

 

	2 10	7	3 20	6	2 20	50
	9	4 40	5	7 10	3 0	50
	5	7	6	2 50	4	50
	10	40	20	60	20	150

 

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

Получаем опорный план:

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

Составляем систему уравнений потенциалов:

Полагая

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

 

 

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

 

---

Дата добавления: 2018-04-05; просмотров: 1443; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

⇐ Предыдущая1234567Следующая ⇒

---

Мы поможем в написании ваших работ!