Решение. Обозначим через Х= Х




Скачать 401.15 Kb.
НазваниеРешение. Обозначим через Х= Х
страница1/3
Дата публикации27.10.2013
Размер401.15 Kb.
ТипРешение
litcey.ru > География > Решение
  1   2   3
Задача 1. Составить математическую модель задачи и решить её двумя способами: симплекс-методом и графически. Для полученной задачи составить двойственную и проверить оптимальность плана исходной задачи с помощью критериев оптимальности планов двойственных задач.

На предприятии в процессе производства используется два технологических способа I и II. При этом расходуются сырьё, трудовые ресурсы и учитываются накладные расходы. Известны удельные затраты для каждого ресурса, запасы ресурсов, а также удельная прибыль при использовании каждого технологического способа. Условия производства требуют, чтобы накладные расходы были не меньше b3. Под удельными затратами и удельной прибылью понимают затраты и прибыль при единичной интенсивности соответствующего технологического способа. Условия задачи можно кратко записать в виде таблицы:

Виды ресурсов

Технологические способы

Запасы ресурсов

Запасы ресурсов

I

II

Сырьё

Трудовые ресурсы

Накладные расходы

3

1
3

1

3
2

18

14
6

Прибыль

4

2




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

Решение.

Обозначим через Х=(х1;x2) план производства, показывающий, какие технологические линии нужно использовать при производстве, чтобы обеспечить предприятию максимум прибыли при имеющихся ресурсах.

Тогда общий прибыли будет следующий:




ЦФ=с1х1+ с2х2

(38)

Это выражение – целевая функция, которую необходимо максимизировать.

В нашем случае: ЦФ=4х1+ 2х2

Так как aijxj расход i-го ресурса на производство xj единиц j-той технологической линии, то, просуммировав расход i-го ресурса на выпуск всех N видов продукции, получим общий расход этого ресурса, который не должен превосходить bi единиц:




Ai1x1+…+aijxj+…+ainxn<=bi

(39)

Чтобы искомый план х=(х1;x2) был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объемы xj выпуска продукции:




Xj>=0 (j=1,N)

(40)

В результате получаем:

max ЦФ=4х1+2 х2

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



Решим данную задачу графическим способом.

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

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

Рисунок 1. Границы области допустимых решений
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.

Обозначим границы области многоугольника решений.
рисунок 2 - решение задач линейного программирования графическим методом

Рисунок 2. Границы области многоугольника
Рассмотрим целевую функцию задачи F = 4x1+2x2 → max. 

Построим прямую, отвечающую значению функции F = 0: F = 4x1+2x2 = 0. Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике (рис. 3) эта прямая обозначена пунктирной линией.

рисунок 3 - пример решения графическим методом

Рисунок 3.
Область допустимых решений представляет собой многоугольник.

Прямая F(x) пересекает область в точке D. Так как точка D получена в результате пересечения прямых BD и DE, то ее координаты удовлетворяют уравнениям этих прямых:



Получили: x1 = 5, x2 = 3. Откуда найдем максимальное значение целевой функции: F(X) = 4*5 + 2*3 = 26

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

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



Дополнительные переменные х3, х4, х5 обозначают возможные остатки ресурсов, т.е. сырье, трудовые ресурсы, и накладные расходы соответственно.

Таким образом, математическая модель примет вид:

max ЦФ=4х1+ 2х2+0* х3+0* х4+0* х5

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



Составим начальный опорный план для данной задачи (таблица 1).

Таблица 1

БП

СБ

А

X1

X2

X3

X4

X5

4

2

0

0

0

X3

0

18

3

1

1

0

0

X4

0

14

1

3

0

1

0

X5

0

6

3

2

0

0

1

FJ-CJ

0

-4

-2

0

0

0

В столбец «БП» на начальном этапе внесены дополнительные переменные, отвечающие за возможные остатки ресурсов: сырье x3, трудовые ресурсы x4 и накладные расходы x5.

Столбец «СБ» содержит значения прибыли с единицы продукции соответствующих базисных переменных. В нашем случае, переменные х3, х4, х5 не несут никакой прибыли, поэтому в столбце «СБ» нули.

Столбец «А» – запасы сырья каждого вида (правая часть ограничений математической модели).

Х1, Х2 – выпускаемая продукция на технологических линиях А1 и А2 соответственно.

Столбец «Х1» содержит в первой строке значение прибыли с единицы выпускаемой продукции, далее расход каждого вида ресурса на выпуск единицы продукции Х1 (коэффициенты в математической модели при переменной Х1). Аналогичным образом заполняются оставшиеся столбец X2, столбцы X3, Х4, Х5 заполняются на основе ограничений математической модели.

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









Значения целевой функции равно соответственно Δ0.

Начальное значение ЦФ равно нулю, т.е. при начальном опорном плане прибыль отсутствует, данные таблицы 1.

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

В нашем случае, начальный опорный план неоптимален (таблица 1), следовательно, необходимо перейти к нехудшему опорному плану.

Для этого определяется разрешающий столбец. Разрешающий столбец определяется по максимальной по модулю оценке в индексной строке среди отрицательных, в таблице 1 разрешающий столбец – Х1.

Разрешающая строка соответствует минимальному симплексному отношению, которое определяется как А/Хj. А – соответствующее значение в столбце А; Хj – это соответствующие значения разрешающего столбца.

В нашем случае симплексные отношения определяются по таблице 4 и имеют вид:



Минимальный элемент соответствует Х3, значит разрешающая строка – первая. Элемент Х5 исключен из рассмотрения, так как по условию его значение должно быть не менее 6.

Перейдем к новому нехудшему опорному плану (таблица 2).

В таблице 2 в столбец «БП» необходимо внести переменную соответствующую переменной разрешающего столбца, т.е. переменную Х1 вместо переменной Х3, т.е. вместо переменной соответствующую переменной разрешающей строки. В столбец «СБ» вносится значение прибыли для продукции Х1.

При составлении таблицы 2 необходимо выполнить следующие правила симплексных преобразований:

1) все элементы разрешающей строки делятся на разрешающий элемент;

2) все элементы разрешающего столбца равны нулю, за исключением разрешающего элемента, он равен 1;

3) все остальные элементы таблицы находят по правилу прямоугольника.









Правило прямоугольника формулируется следующим образом:

Чтобы получить элемент a’ij новой симплексной таблицы необходимо из произведения угловых элементов главной диагонали вычесть произведение угловых элементов побочной диагонали и полученное число разделить на разрешающий элемент, т.е.

Разреш_элемент

аij

главная

побочная

аij0

аij0

Рисунок 7 – Правило прямоугольника
В нашем случае, после симплексных преобразований, не худший опорный план представлен в таблице 2:

Таблица 2

БП

СБ

А

X1

X2

X3

X4

X5

4

2

0

0

0

X1

4

6

1

0,3333

0,3333

0

0

X4

0

8

0

2,6667

-0,333

1

0

X5

0

-12

0

1

-1

0

1

FJ-CJ

24

0

-0,667

1,3333

0

0

В таблице 2 в индексной строке есть отрицательные элементы, поэтому начальный опорный план неоптимален, следовательно, необходимо перейти к нехудшему опорному плану (таблица 3).

Разрешающий столбец 2, разрешающая строка вторая.

Таблица 3

БП

СБ

А

X1

X2

X3

X4

X5

4

2

0

0

0

X1

4

5

1

0

0,375

-0,13

0

X2

2

3

0

1

-0,125

0,375

0

X5

0

-15

0

0

-0,875

-0,38

1

FJ-CJ

26

0

0

1,25

0,25

0

В опорном плане (таблица 3) в индексной строке нет отрицательных значений. Следовательно, полученный опорный план – оптимальный. Переменные, входящие в оптимальный план, определяются по двум столбцам: БП и А. Переменные в оптимальном плане выстраиваются по возрастанию. Переменные столбца БП входят в оптимальный план Х* в количестве, взятом из столбца А, т.е.:

Х*=(5; 3; 0; 0;-15). ЦФ = 26 ден. ед.

Проанализируем оптимальный план Х*. Согласно ему, выпускать следует продукцию по первой технологической линии Х1 в количестве 5ед, продукцию по второй технологической линии Х2 – 3 ден. ед. Из ресурсов накладные расходы (Х5) увеличатся на 15 ед, т. е. составят 21 ед. Ресурсы Х3 (сырье), Х4 (трудовые ресурсы) израсходованы полностью (их величины в Х* равны нулю). Максимальная прибыль от реализации данного плана составит 26 ден. ед.

Каждой прямой задаче линейного программирования соответствует двойственная задача. Двойственная задача формулируется по следующим правилам.

Пара взаимно двойственных симметричных задач в виде конечных сумм имеет вид:


Прямая задача

Двойственная задача









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

min ЦФ = 18у1+14у2+6у3

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



Двойственная переменная yi является коэффициентом при bi и, следовательно, показывает, как изменяется ЦФ при изменении ресурса bi на единицу. Двойственные переменные называют двойственными оценками. Существенным является то, что для нахождения двойственных оценок решать двойственную задачу не требуется. Их значения уже находятся в симплексной таблице оптимального решения исходной задачи.

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

В двойственную задачу для перехода от неравенств к равенствам вводятся дополнительные двойственные переменные. Смысл дополнительных двойственных переменных заключается в следующем: если основные переменные (например, х1, х2) вошли в оптимальное решение, то дополнительные переменные (y4, y5) равны нулю. Если основные переменные не вошли в оптимальное решение, т.е. равны нулю, то соответствующие им дополнительные переменные имеют положительное значение. Дополнительные переменные двойственной задачи показывают насколько уменьшиться значение целевой функции при принудительном выпуске единицы данной продукции, т.е. убыточность.

В каноническом виде ДЗ для нашего случая имеет вид:

min ЦФ = 18у1+14у2+6у3-0* у4-0* у5

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



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

БП

СБ







Оптимальный план двойственной задачи определяется по индексной строке таблицы 2, имеет следующий вид:

Y*=(1,25; 0,25; 0; 0; 0).

Анализируя оптимальный план двойственной задачи, получаем, что y1*>0 – ресурсы первого вида (сырье) и y2*>0 – ресурсы второго вида (трудовые ресурсы) используются полностью. Остальные ресурсы равны 0, значит используются не полностью. y4*=0 и y6*=0 – значит продукция х1 и х2 вошли в оптимальный план.
Задача 2.

Решить транспортную задачу. Заданы мощности поставщиков ai(i = 1,2,3), емкости потребителей bj ( j= 1,2,3) и матрица стоимостей перевозок единицы продукции от каждого поставщика каждому потребителю. Требуется найти план перевозок, при котором суммарные транспортные затраты будут наименьшими.

bj

ai

19

31

10

20

5

8

3

10

2

4

2

12

7

6

3
  1   2   3

Похожие:

Решение. Обозначим через Х= Х iconОбозначим через [меш.] количество мешков с мукой, которые будут перевезены...

Решение. Обозначим через Х= Х iconОстаток в формуле Тейлора и его оценка
Разность между функцией и её многочленом Тейлора называется -м остатком, или -м остаточным членом; обозначим этот остаток через
Решение. Обозначим через Х= Х icon§ 14. Нормальное уравнение прямой. Задача определения расстояния от точки до прямой
...
Решение. Обозначим через Х= Х iconПусть и непрерывное отображение. Можно ли утверждать, у отображения есть неподвижные точки?
Рассмотрим модель чистого обмена с видами товаров и потребителями. Обозначим через начальный запас го товара у -го потребителя. Пусть...
Решение. Обозначим через Х= Х iconНет вакуума (нуля) и бесконечности
...
Решение. Обозначим через Х= Х iconИспользование wifi роутеров для управления устройствами через Интернет
Также в этих работах не рассматривался вопрос об ударенной работе с устройствами через Интернет. Решение представлено только для...
Решение. Обозначим через Х= Х icon§ 11. Параметрические уравнения линии
Обозначим буквами Х и у координаты некоторой точки М; рассмотрим две функции аргумента t
Решение. Обозначим через Х= Х iconВ задачах о размещениях полагается
...
Решение. Обозначим через Х= Х iconКак добраться от Москвы до Ельца на машине и далее через Талицу
Внимание! Во время половодья в марте-апреле этот удобный и короткий маршрут не действует, по причине затопления моста через р. Сосну....
Решение. Обозначим через Х= Х iconРешение этих задач и обеспечивается через налогообложение
Материалы данного файла могут быть использованы без ограничений для написания собственных работ с целью последующей сдачи в учебных...
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
litcey.ru
Главная страница