Оптимизация задач линейного программирования с помощью симплекс-метода.

Цель работы

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

 

Теоретические сведения

 

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

 

Задача об использовании ресурсов.

Обозначим x_j (j=1,2,…,n) – число единиц продукции P_j, запланированной к производству; b_i (i=1,2,…,m) – запас ресурса S_i, a_ij – число единиц ресурса S_i, затрачиваемого на изготовление единицы продукции P_j; c_j – прибыль от реализации единицы продукции P_j.

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план X=(x₁, x₂,…,x_n) выпуска продукции, удовлетворяющий системе [4]:

 

(1)

 

и условию:

 

(2)

 

при котором функция:

 

(3)

принимает максимальное значение [1].

Пример.

Для изготовления двух видов продукции P1 и P2 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на единицу продукции, приведены в таблице 1 (цифры условные).

 

Таблица 1 - Исходные данные

 

Вид ресурса	Запас ресурса	Число единиц ресурса, затрачиваемых на изготовление единицы продукции
P1	P2
S1
S2
S3		-
S4			-
Прибыль от единицы продукции

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

Решение.

Составим экономико-математическую модель задачи.

Обозначим x₁, x₂ – число единиц продукции соответственно P1 и P2, запланированных к производству. Для их изготовления потребуется (1*x₁+3*x₂) единиц ресурса S1 и т.д. Так как потребление ресурсов S1, S2, S3 и S4 не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и запасами выражается системой неравенств:

 

(4)

 

По смыслу задачи переменные положительны:

 

(5)

 

Суммарная прибыль составит:

 

(6)

 

Цель задачи: найти такой план X=(_x1, x₂) выпуска продукции, удовлетворяющий системе (4) и условию (5), при котором функция (6) принимает максимальное значение.

 

2.2. Симплексные таблицы

 

Практические расчеты при решении реальных задач симплексным методом выполняются в настоящее время с помощью компьютеров. Однако если расчеты осуществляются без ЭВМ, то удобно использовать так называемые симплексные таблицы. Далее мы рассмотрим алгоритм их составления, не углубляясь в его подробное обоснование. Для определенности считаем, что решается задача на отыскание максимума.

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

 

(7)

 

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены [5].

II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указываются коэффициенты функции цели с противоположным знаком: . В левом столбце таблицы записываем основные переменные (базис), в первой строке таблицы — все переменные (отмечая при этом основные), во втором столбце — свободные члены расширенной системы b₁, b₂,…, b_m. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты а_ij при переменных из расширенной системы. Далее таблица преобразуется по определенным правилам.

III. Проверяем выполнение критерия оптимальности при решении задачи на максимум — наличие в последней строке отрицательных коэффициентов . Если таких нет, то решение оптимально, достигнут max F = c₀ (в левом нижнем углу таблицы), основные переменные принимают значения а_i0 (второй столбец), основные переменные равны 0, т.е. получаем оптимальное базисное решение.

IV. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент b_i < 0 в последней строке определяет разрешающий столбец s.

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

1) , если b_i и а_is имеют разные знаки;

2) , если bi = 0 и а_is< 0;

3) , если а_is = 0;

4) 0, если bi = 0 и а_is> 0;

5) , если a_i0 и а_is имеют одинаковые знаки.

Определяем . Если конечного минимума нет, то задача не имеет конечного оптимума . Если минимум конечен, то выбираем строку q, на которой он достигается (любую, если их несколько), и называем ее разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент а_qs.

V. Переходим к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной x_q — переменную х_s

б) в столбцах, соответствующих основным переменным, проставляем нули и единицы: 1 — против "своей" основной переменной, 0 — против "чужой" основной переменной, 0 — в последней строке для всех основных переменных;

в) новую строку с номером q получаем из "старой" делением на разрешающий элемент a_qs,

г) все остальные элементы , вычисляем по правилу прямоугольника:

 

(8)

 

(9)

 

Рисунок 1 – Правило прямоугольника

 

Далее переходим к п. III алгоритма.

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

Решение. Расширенная система задачи имеет вид:

 

 

Линейную функцию представим в виде . Заполняем первую симплексную таблицу (таблица 2), в которой переменные x₃, x₄, x₅, x₆ основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

 

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

 

Базис	Свобод-ный член	Переменные	Оценочное отношение
Х1	Х2	X3	Х4	Х5	Х6
Xз					0		0	18/3
Х4
Х5
Х6
F		-2	-3

 

В соответствии с п. III алгоритма проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем из них наибольший по модулю (-3); второй столбец разрешающий, переменная х₂ перейдет в основные. В соответствии с п. IV находим оценочные отношения и х₂ ==min{l8/3; 16; 5; ¥}= 5. Третья строка является разрешающей. На пересечении разрешающих строки и столбца стоит разрешающий элемент a₃₃ = 1.

Строим таблицу 3 по правилам п. V алгоритма:

а) в новом базисе основные переменные: x₃, x₄, x₂, x_6;

б) расставляем нули и единицы; например, в клетке, соответствующей основной переменнойx₃ по столбцу и строке, ставим 1, а в клетке, соответствующей основной переменной x₃ по строке, а основной переменной х₂ — по столбцу, ставим 0 и т.п. В последней строке против всех основных переменных ставим 0. Третья строка получается делением на разрешающий элемент а₃₃ = 1. Остальные клетки заполняем по правилу прямоугольника. Например: , и т.д.

Получим вторую симплексную таблицу (таблица 3).

 

Таблица 3 – Вторая симплексная таблица

 

Базис	Свобод-ный член	Переменные	Оценочное отношение
X1	X2	X3	X4	X5	X6
Хз			0			-3	0
X4						-1	0	11/2
X2.							0	¥
X6,
F		-2

 

Критерий оптимальности вновь не выполнен. Теперь первый столбец разрешающий; х₁ — переходит в основные, min{3/l; 11/2; ¥; 7}= 3; первая строка разрешающая, a₁₁ — разрешающий элемент.

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

 

Таблица 4 – Третья симплексная таблица

 

Базис	Свобод-ный член	Переменные	Оценочное отношение
X1	X2	X3	X4	X5	X6
X1						-3		ОС
X4				-2				5/5
X2								5/1
X6				-3				12/9
F						-3

 

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, a₂₅ = 5 — разрешающий элемент. Переходим к таблице 5.

 

Таблица 5 – Четвертая симплексная таблица

 

Базис	Свобод-ный член	Переменные	Оценочное отношение
X1	X2	X3	X4	X5	X6
X1				-1/5	3/5			ОС
X5				-2/5	1/5			5/5
X2				2/5	-1/5			5/1
X6				3/5	-9/5			12/9
F				4/5	3/5

Критерий оптимальности выполнен, значит , оптимальное базисное решение (6;4;0;0;1;3).

Варианты заданий

Индивидуальная работа предполагает выполнение задачи согласно выбранному варианту. Распределение заданий по вариантам представлено в таблице 20.

Таблица 20 - Варианты заданий

Номер варианта
Номер задания
Задача
Номер варианта
Номер задания
Задача

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

Задача 1.

Для производства двух видов изделий А и В предприятие использует три вида сырья. Исходные данные приведены в таблице 17.

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

 

Таблица 18 – Исходные данные

 

Вид сырья	Нормы расхода сырья на производство одного изделия, кг	Общее количество сырья, кг
А	В
Прибыль от реализации одного изделия, грн.

 

Задача 2.

Рацион для питания животных на ферме состоит из двух видов кормов (А и В). Один килограмм корма А стоит 80 грн. и содержит: 1 ед. жиров, 3 ед. белков, 1 ед. углеводов, 2 ед. нитратов. Один килограмм корма В стоит 10 грн. и содержит 3 ед. жиров, 1 ед. белков, 8 ед. углеводов и 4 ед. нитратов.

Составить наиболее дешевый рацион питания, обеспечивающий жиров не менее 6 ед., белков не менее 9 ед., углеводов не менее 8 ед., нитратов не более 16 ед.

Задача 3.

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

Найти программу максимального выпуска продукции.

 

Таблица 19 - Исходные данные

 

Вид технологического процесса	Норма расхода ресурса на производство единицы продукции, грн.
Сырье	Электроэнергия	Заработная плата
		0,2
		0,1
Запас ресурса

Задача 4.

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

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

 

Таблица 20 – Исходные данные

 

Вид ресурса	Норма расхода ресурса на производство одной единицы продукции, грн.	Объем ресурсов
А	В
Сырье и материалы
Топливо и электроэнергия	0,3	0,2
Заработная плата	0,8
Основные производственные фонды	1,2	0,8
Прибыль на единицу изделия, грн.			-

Задача 5.

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

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

Ограничения:

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

- количество произведенного не должно быть отрицательным.

 

Таблица 21 – Нормы расхода ресурсов для производства игрушек

 

Вид ресурса	Норма расхода ресурса на производство одной игрушки, грн.	Объем ресурсов
А	В
Краска
Пластик
Дерево
Клей
Прибыль на единицу изделия, грн.

 

Задача 6.

Компания Puck and Pawn специализируется на производстве хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере 2 долл. США, а каждый шахматный набор — 4 долл. США. На изготовление одной клюшки требуется четыре часа работы на участке А и два часа на участке В. Шахматный набор изготавливается с затратами шести часов работы на участке A, шести часов на участке В и одного часа на участке С. Доступная производственная мощность, выраженная в рабочих часах, участка А составляет максимум 120 часов в день; участка В — 72 часа, а участка С— 10 часов.

 

Задача 7.

В ходе производства два вида продукции X и Y проходят обработку на станках I и II. У станка I есть 200 часов доступного времени, а у станка II — 400. Для обработки одной единицы продукции X необходим один час работы на станке I и четыре часа на станке II. Обработка продукции Y требует одного часа на станке I и одного — на станке II. Единица продукции X дает прибыль в размере 10 долл., а единица продукции Y — 5 долл.

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

 

СОДЕРЖАНИЕ ОТЧЕТА

1) Цель работы;

2) постановка задачи;

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

4) выводы по выполнению работы.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

1) Сформулируйте основную задачу линейного программирования?

2) Опишите алгоритм решения задачи линейного программирования графическим методом?

3) В чем заключается суть симплекс-метода?

4) Как выбирают разрешающие столбец и строку при решении задач линейного программирования методом симплекс - таблиц?

5) Как установить оптимальность допустимого базисного решения?

6) Опишите алгоритм решения задачи линейного программирования методом симплекс - таблиц?

 

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