Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Контрольная работа - файл 2 Линейное программирование.doc


Загрузка...
Контрольная работа
скачать (1273 kb.)

Доступные файлы (5):

1 Графический метод решения задач линейного программирования.doc488kb.27.09.2008 16:04скачать
2 Линейное программирование.doc1049kb.28.09.2008 18:29скачать
3 Транспортная задача.doc770kb.28.09.2008 18:31скачать
4 Динамическое программирование и сетевое планирование.doc299kb.28.09.2008 18:31скачать
Прочитай.txt1kb.28.11.2008 14:06скачать

2 Линейное программирование.doc

Реклама MarketGid:
Загрузка...
2. Линейное программирование
Задание:

Предприятие имеет три типа металлообрабатывающих станков А, В, и С, на которых изготавливаются изделия вида 1 и 2. Изделия первого вида изготавливаются только на станках А и С, а изделия второго вида изготавливаются на всех станках (А, В, С).
Производственная мощность станков такова (тысяч в год):


Тип станка

Производительная мощность

(тыс.штук в год)

А

6 изделий вида 1 или 6 изделий вида 2

В

4 изделия вида 2

С

5 изделий вида 1 или 10 изделий вида 2.

Прибыль на единицу изделия 1 составляет 2 усл.ед., на изделие 2 - 4 усл.ед.
Определить такие объемы производства чтоб прибыль была максимальной.



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

  2. Решить задачу графически.

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


Решение:

  1. Составить математическую модель.

Пусть х1 – количество изготовленных за год изделий вида 1.

Пусть х2 – количество изготовленных за год изделий вида 2.
По условию задачи целевая функция выглядит так:

(общая прибыль в год)

Составим ограничения функции. В нашем случает кол-во изделийпроизводительной мощиности станков.

Для станка А:

Для станка В:

Для станка С:

Включая условие неотрицательности получаем систему ограничений:


Математическая модель задачи имеет вид:






  1. Графическое решение.


Строим многоугольник решений (рис.5):



frame1

Находим координаты вершин области (х12).

Для точки А координаты вершины (5;0);

Для точки В координаты вершины (5;4);

Для точки С координаты вершины (0;4);

Координаты точки О(0;0) совпадают с началом координат.
Целевая функция определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение.

Вектор с координатами с1=1, с2=4 и выходящий из начала координат, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания функции, а противоположный вектор – направление убывания.

frame2

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

Из рисунка 7 видно, что находится в точке В(5;4).


Ответ: Максимальная прибыль предприятия 26 тыс. условных единиц в год, для получения такой прибыли предприятие должно выпустить 5 тыс. деталей вида 1 и 4 тыс.деталей вида 2.


  1. Симплекс-метод.





Запишем задачу в канонической форме, т.е. ограничения-неравенства перепишем в виде равенств, добавляя балансовые переменные:



;



Эта система является системой с базисом (базис s1, s2, s3, s4, s5, каждая из них входит только в одно уравнение системы с коэффициентом 1), x1 и x2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами:

-система ограничений должна быть системой уравнений с базисом;

-свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Таблица 1) для решения задачи на симплекс-метод, т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь «БП» означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

Таблица 1

БП

x1

x2

s1

s2

s3

s4

s5

Решение

Отношение

z

-2

-4

0

0

0

0

0

0

-

s1

1

0

1

0

0

0

0

6

-

s2

0

1

0

1

0

0

0

6

6/1=6

s3

0

1

0

0

1

0

0

4

4/1=4

s4

1

0

0

0

0

1

0

5

-

s5

0

1

0

0

0

0

1

10

10/1=10

Для улучшения решения перейдем к следующей симплекс-таблице (таблица 2). Для этого надо в таблице 1 выбрать разрешающий столбец, т.е. переменную, которая войдет в базис на следующей итерации симплекс-метода. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации симплекс-метода это столбец x2 (коэффициент -4).

Затем выбирается разрешающая строка, т.е. переменная, которая выйдет из базиса на следующей итерации симплекс-метода. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s3 (коэффициент 4).

^ Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации симплекс-метода переменная x2 заменит в базисе s1. Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполняем таблицу 2.

1)Вычисление строки х2 таблицы 2. Сначала делим все члены разрешающей строки s3 таблицы 1 на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x2 в таблице 2. Т.к. разрешающий элемент в данном случае равен 1, то строка s3 таблицы 1 будет совпадать со строкой х2 таблицы 2. Строку x2 таблицы 2 мы получили 0 1 0 0 1 20, остальные строки таблицы 2 будут получены из этой строки и строк таблицы 1 следующим образом:

2) Вычисление z-строки таблицы 2. На месте -4 в первой строке (z-строке) в столбце х2 таблицы 1 должен быть 0 в первой строке таблицы 2. Для этого все элементы строки х2 таблицы 2 (0 1 0 0 1 0 0 4) умножим на 4, получим (0 4 0 0 4 0 0 16) и сложим эту строку с первой строкой (z - строкой) таблицы 1 (-2 -4 0 0 0 0 0 0), получим (-2 0 0 0 4 0 0 16). В столбце x2 появился ноль 0, цель достигнута. Элементы разрешающего столбца х2 выделены красным цветом.

3) Строку s1 оставляем без изменений.

4) Вычисление строки s2 таблицы 2. На месте 1 в s2 строке таблицы 1 должен быть 0 в таблице 2. Для этого все элементы строки х2 таблицы 2 (0 1 0 0 1 0 0 4) умножим на -1, получим 0 -1 0 0 -1 0 0 -4 и сложим эту строку с s2 - строкой таблицы 1 (0 1 0 1 0 0 0 6), получим строку (0 0 0 1 -1 0 0 2). В столбце х2 получен необходимый 0.

5) Вычисление строки s5 таблицы 2. На месте 1 в s5 строке таблицы 1 должен быть 0 в таблице 2. Для этого все элементы строки х2 таблицы 2 (0 1 0 0 1 0 0 4) умножим на -1, получим 0 -1 0 0 -1 0 0 -4 и сложим эту строку с s5 - строкой таблицы 1 (0 1 0 0 0 0 1 10), получим строку 0 0 0 0 -1 0 1 6. В столбце х2 получен нужный 0. Столбец х2 в таблице 2 стал единичным, он содержит одну 1 и остальные 0.

Таблица 2

БП

x1

x2

s1

s2

s3

s4

s5

Решение

Отношение

z

-2

0

0

0

4

0

0

16

-

s1

1

0

1

0

0

0

0

6

6/1=6

s2

0

0

0

1

-1

0

0

2

-

х2

0

1

0

0

1

0

0

4

-

s4

1

0

0

0

0

1

0

5

5/1=5

s5

0

0

0

0

-1

0

1

6

-

В этой таблице берем столбец х1 и строку s4. Пересчет элементов таблицы делаем аналогично и получаем:


Таблица 3

БП

x1

x2

s1

s2

s3

s4

s5

Решение

Отношение

z

0

0

0

0

4

2

0

26

-

s1

0

0

1

0

0

-1

0

1




s2

0

0

0

1

-1

0

0

2

-

х2

0

1

0

0

1

0

0

4

-

x1

1

0

0

0

0

1

0

5

-

s5

0

0

0

0

-1

0

1

6

-


Разрешающий столбец х1, разрешающая строка s4, s4 выходит из базиса, х1 входит в базис (таблица 3).

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x1 = 5, x2 = 4, zmax = 26.
Ответ: Максимальная прибыль предприятия 26 тыс. условных единиц в год, для получения такой прибыли предприятие должно выпустить 5 тыс. деталей вида 1 и 4 тыс.деталей вида 2.







Скачать файл (1273 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации
Рейтинг@Mail.ru