Применение линейного программирования для решения экономических задач (оптимизация прибыли) (стр. 4 из 5)

(2.7)

(2.8)

(2.9)

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

Таблица 2.1

Матрица планирования ТЗ

Поставщики	Потребители				Запасы
	B1	B2	…	Bn
A1	C11	C12	…	C1n	a1
A2	C21	C22	…	C2n	a2
…	…	…	…	…	…
Am	Cm1	Cm2	…	Cmn	am
b1	b2	…	bn

Таким образом, обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки. Всякое неотрицательное решение систем линейных уравнений называется планом транспортной задачи. План, при котором целевая функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи. Если в опорном плане число отличных от нуля компонент равно в точности n+m–1, то план является невырожденным, а если меньше – то вырожденным. [3 c.132-134]

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

В случае превышения запаса над потребностью, вводится фиктивный (n+1)–й пункт назначения с потребностью (формула 2.10) и соответствующие тарифы считаются равными нулю. Аналогично, в случае, если потребности превышают количество запасов, также вводится фиктивный (m+1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю (формула 2.11). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

(2.10)

(2.11)

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

1. метод северо-западного угла;

2. метод минимального элемента;

3. метод двойного предпочтения;

4. метод штрафов (Фогеля).

"Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла– наихудшее.

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

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

Для того чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце. Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы. [3 c.137]

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

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

На каждом шаге метода Фогеля для каждой i-й строки вычисляются штрафы, как разность между двумя наименьшими тарифами строки. Таким же образом вычисляются штрафы для каждого j-го столбца. После чего выбирается максимальный штраф из всех штрафов строк и столбцов. В строке или столбце, соответствующем выбранному штрафу, для заполнения выбирается не вычеркнутая клетка с минимальным тарифом. Если существует несколько одинаковых по величине максимальных штрафов в матрице, то в соответствующих строках или столбцах выбирается одна не вычеркнутая клетка с минимальным тарифом.

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел Ui и Vj, удовлетворяющих условиям: Ui+Vj=Cij для занятых клеток и Ui+Vj≤Сij в свободных клетках. Числа Ui и Vj называются потенциалами соответственно поставщиков и потребителей. При решении одному неизвестному потенциалу придается произвольное значение. [3 c.141]

3. Оптимизация прибыли с применением метода линейного программирования

3.1 Постановка задачи и формирование оптимизационной модели

Предприятие реализует товары трех групп. Известны нормативы затрат ресурсов A_ijв расчете на единицу товара и ограничения по располагаемым ресурсам, которые приведены в (табл. 3.1)

Таблица 3.1

Нормативы затрат ресурсов и ограничений

Ресурсы	Нормативы затрат ресурсов по продаже товаров
	Aj	Bj	Cj
Рабочее время, чел.ч.	А11=0,1	А12=0,2	А13=0,4
Площадь торговых помещений, м2	А21=0,05	А22=0,02	А23=0,02
Издержки обращения на ед. товара, руб.	А31=3	А32=1	А33=2
Доход на единицу товара, руб.	С1=3	С2=5	С3=4
План продажи, ед.	X1	X2	X3

Ограничение объемов ресурсов составляют: ресурс первого вида ≤ 1300, ресурс второго вида ≤ 140, ресурс третьего вида ≤8200.

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

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

Составим оптимизационную модель. Запишем целевую функцию(формула 3.1), ограничения на количество ресурсов (формула 3.2) и условия неотрицательности (формула 3.3)

(3.1)

(3.2)

(3.3)

3.2 Расчет и анализ результатов оптимизации прибыли

Первоначальный опорный план симплекс методом находится только тогда, когда в системе ограничения левые и правые части уравнения равны. Поэтому необходимо перейти от неравенств к равенствам, прибавляя к левым частям неотрицательные дополнительные переменные (дополнительным переменным в линейной функции соответствуют коэффициенты равные нулю). Следовательно, целевая функция (формула 3.4), система ограничений (формула 3.5) и условия неотрицательности (формула 3.6)примут другой вид.

(3.4)

(3.5)

(3.6)

Решаем задачу симплексным методом. Расчеты производим в симплекс таблице. (см. табл. 3.2)

Таблица 3.2

Первая симплексная таблица

Базис	Cj баз.	B	X1	X2	X3	X4	X5	X6
			3	5	4	0	0	0
X4	0	1300	0.1	0.2	0.4	1	0	0
X5	0	140	0.05	0.02	0.02	0	1	0
X6	0	8200	3	1	2	0	0	1
П(x)		0	-3	-5	-4	0	0	0

Этот план не является оптимальным, так как в строке «прибыль» есть три отрицательные оценки. Выбирая наименьшую оценку, находим направляющий столбец. Направляющую строку находим, поочередно деля, значение «В» i-й строки на элемент i-й строки направляющего столбца. Направляющей строкой будет та, в которой значение частного будет наименьшим. Направляющий столбец - пятый, направляющая строка первая. Разрешающий элемент находим на пересечении направляющей строки и столбца, он равен 0.2. Строим вторую симплексную таблицу. (табл. 3.3)