Лекции.Орг
 

Категории:


Макетные упражнения: Макет выполняется в масштабе 1:50, 1:100, 1:200 на подрамнике...


Универсальный восьмиосный полувагона: Передний упор отлит в одно целое с ударной розеткой. Концевая балка 2 сварная, коробчатого сечения. Она состоит из...


Построение спирали Архимеда: Спираль Архимеда- плоская кривая линия, которую описывает точка, движущаяся равномерно вращающемуся радиусу...

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



Загрузка...

Цель работы

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

 

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

 

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

 

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

Обозначим xj (j=1,2,…,n) – число единиц продукции Pj, запланированной к производству; bi (i=1,2,…,m) – запас ресурса Si , aij – число единиц ресурса Si, затрачиваемого на изготовление единицы продукции Pj; cj – прибыль от реализации единицы продукции Pj.

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

 

(1)

 

и условию:

 

(2)

 

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

 

(3)

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

Пример.

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

 

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

 

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

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

Решение.

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

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

 

(4)

 

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

 

(5)

 

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

 

(6)

 

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

 

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

 

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

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

 

(7)

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

(8)

 

(9)

 

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

 

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

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

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

 

 

Линейную функцию представим в виде . Заполняем первую симплексную таблицу (таблица 2), в которой переменные x3, x4, x5, x6 основные. Последняя строка заполняется коэффициентами линейной функции с противоположным знаком (см. п. II алгоритма).

 

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

 

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

 

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

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

а) в новом базисе основные переменные: x3, x4, x2, x6;

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

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

 

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

 

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

 

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

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

 

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

 

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

 

И на этот раз критерий оптимальности не выполнен; пятый столбец и вторая строка разрешающие, a25 = 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





Дата добавления: 2016-12-31; просмотров: 680 | Нарушение авторских прав


Рекомендуемый контект:


Похожая информация:

Поиск на сайте:


© 2015-2019 lektsii.org - Контакты - Последнее добавление

Ген: 0.017 с.