Задание 4. Решение задачи симплекс-методом

Дано:

L= Х₁+2Х₂+3Х₃-Х₄;

Х₁+Х₂+Х₃+Х₄=4;

Х₁+2Х₂+Х₃+2Х₄=6;

Х₁+2Х₂+2Х₃+Х₄=6;

Х₁,Х₂,Х₃,Х₄ ≥0

Решение.

Решение задачи ЛП симплекс-методом состоит из 2х этапов:

1) Находят какой-либо начальный опорный план Х₀;

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

Записываем задачу линейного программирования в форме симплексной таблицы. Последняя строка в симплексной таблице – строка для целевой функции (ЦФ) – f-строка. Все элементы столбца свободных членов должны быть неотрицательны. Те уравнения системы, в которых свободные члены отрицательны, предварительно умножаются на (-1).

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

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

Таблица 2 Таблица 3

		-Х1	-Х2	-Х3	-Х4
f		-1	-2	-3

		-Х1	-Х2	-Х3
-Х4
	-2	-1		-1
	-2
f	-4	-2	-3	-4

Таблица 4 Таблица 5

		-Х1	-Х2
-Х4
		-1
-Х3
F		-2

		-Х1
-Х4
-Х2		-1
-Х3
F		-1

При Х₁ =0, получим Х₂ =0, Х₃ =2, Х₄ =2, тогда f(Х₀) =4

2) Нахождение оптимального опорного плана.

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

Таблица 6

		-Х3
-Х4
-Х2
-Х1
f

Так как в f- строке нет отрицательных элементов (не считая свободного члена) - план оптимален.

Х*(2; 2; 1; 0) f(Х*) =6

Вывод: Решили задачу симплекс- методом.

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

Дано:

Завод имеет три цеха – А, В, С и четыре склада – 1; 2; 3; 4. Цех А производит 30 тысяч штук изделий, цех В – 40; цех С – 20 тысяч штук изделий. Пропускная способность складов за то же время характеризуется следующими показателями: склад 1 – 20 тысяч штук изделий; склад 2 – 30; склад 3 – 30 и склад 4 – 10 тысяч штук изделий. Стоимость первозки 1 тысячи штук изделий из цеха А на склады 1, 2, 3, 4 – соответственно (д.е): 20, 30, 40, 40; из цеха В – соответственно 30, 20, 50, 10; а из цеха С – 40, 30, 20, 60.

Решение.

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

Таблица транспортной задачи в общем виде:

Таблица 7

Пункты отправления	Пункты назначения	Запасы продукции
В1	В2	В3	В4
А1	X11 C11	X12 C12	X13 C13	X14 C14	а1
А2	X21 C21	X22 C22	X23 C23	X24 C24	а2
А3	X31 C31	X32 C32	X33 C33	X34 C34	а3
Потребность	b1	b2	b3	b4	а1+а2+ а3= b1+ b2+ b3+ b4

а_i – запас продукции в пункте отправления А_i;

b_j – спрос на продукцию в пункте назначения В_j;

С_ij – тариф перевозки единицы продукции из пункта отправления А_i в пункт назначения В_j.

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

L(X) – транспортные расходы на перевозку всей продукции.

Преобразовав таблицу по нашему варианту получим:

Таблица 8

Цеха	Склады	Производительность
А
В
С
Пропускная способность

Существуют 3 метода нахождения опорных планов:

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

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

Таблица 9

Цеха	Склады	Производительность
А
В
С
Пропускная способность

Затем записываем матрицу и рассчитываем расходы на перевозку

20000 10000 0 0

0 20000 20000 0

0 0 10000 10000

L(Х) = 20000∙20+10000∙30+20000∙20+20000∙50+10000∙20+10000∙60 = 2900000 рублей.

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

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

Таблица 10

Цеха	Склады	Производительность
А
В
С
Пропускная способность

20000 0 10000 0

0 30000 0 10000

0 0 20000 0

L(X)= 20000∙20+10000∙40+30000∙20+10000∙10+20000∙20= 1900000 рублей.

3) Метод Фогеля.

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

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

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

Цеха	Склады	Производительность	Штрафы строк
А
В
С								-
Пропускная способность
Штрафы столбцов
				-
				-

Таблица 11

20000 0 10000 0

0 30000 0 10000

0 0 20000 0

L(X) = 20000∙20+10000∙40+30000∙20+10000∙10+20000∙20= 1900000 рублей.

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

Задание 6. Решение задачи линейного программирования с помощью EXCEL на примере задачи оптимизации плана производства.

Дано:

Малое мебельное предприятие изготовляет стулья и кресла. Стоимость стула А рублей, стоимость кресла B рублей. Для их производства используются материалы трех наименований: с1 кг – материала первого наименования, с2 кг - второго и с3 кг – третьего наименования. Расходы этих материалов составляют: на стул - а1 кг материала первого наименования, а2 кг – второго, а3 кг – третьего наименования; на кресло, соответственно, материала первого наименования - в1 кг, второго, - в2 кг, третьего, - в3 кг. Установить такой план выпуска изделий, чтобы предприятие от их реализации получило максимальную прибыль.

Таблица 12

Вариант	а1	а2	а3	в1	в2	в3	с1	с2	с3	А	В

Решение.

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

Составим математическую модель, для чего введем следующие обозначения:

x_j - количество выпускаемой продукции j-го типа, j=1,4;

b_i - количество располагаемого ресурса i-го вида, i=1,3;

a_ij - норма расхода i-го ресурса для выпуска единицы продукции j-го типа;

c_j - прибыль, получаемая от реализации единицы продукции j-го типа.

2) Теперь приступим к составлению модели.

6Х₁+9Х₂ → max

14Х₁+40Х₂ ≤ 740

15Х₁+27Х₂ ≤ 742

20Х₁+4Х₂ ≤ 822

Х₁,Х₂ ≥0

3) Заполнили созданную форму данными – коэффициентами целевой функции, коэффициентами системы линейных неравенств, свободными членами системы линейных неравенств, соотношениями между левыми и правыми частями неравенств.

4) Установили: амбарчик с целевой функцией, направление оптимизации, диапазон амбарчиков со значениями переменных, которые должны определиться как решение задачи.

5) Убедились, что все параметры выставлены правильно и перешли к решению задачи.

Рисунок 2 – Решение задачи в Excel

Из таблицы видно, что в оптимальном решении стул = В2=3, кресло = С2 =2. При этом максимальная прибыль будет составлять D5= 36, количество использованных ресурсов равно: наим1=D8=122, наим2=D9=99, наим3= D10 =68. Таково оптимальное решение рассматриваемой задачи распределения ресурсов.

Вывод: научились решать задачи оптимизации средствами табличного процессора Excel.