Logo GenDocs.ru

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


Загрузка...

Контрольная работа по линейному программированию - файл 1.docx


Контрольная работа по линейному программированию
скачать (197.4 kb.)

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

1.docx198kb.13.12.2011 00:13скачать

Загрузка...

1.docx

Реклама MarketGid:
Загрузка...
1. Графический метод решения задач линейного программирования.
Вариант 10.

Задание 1.

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

Решение.

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




0

3




6

0

Причем неравенству удовлетворяет верхняя полуплоскость, образовавшееся при делении плоскости прямой I.
II.




0

10




5

0

Причем неравенству удовлетворяет нижняя полуплоскость.
III.




0

6




6

0

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

Кроме того, по условию ,

Таким образом решение системы , находится в I четверти координатной плоскости, заключено между прямыми I и II, и при этом принадлежит прямой III, всем этим условиям соответствует отрезок АВ.



Координаты точки В мы нашли ранее В(6;0), координаты точки А находятся решением системы: А(2;4)

Для того чтобы найти минимальное и максимальное значение функции при заданных ограничениях, построим нормальный вектор

(3;2), затем построим перпендикулярно вектору прямую, проходящую через начало координат, перемещая данную прямую в направлении вектора заметим что она входит в область определения в точке А (на рисунке прямая а), это минимум данной функции. При дальнейшем перемещении прямой видно, что она выходит из области определения в точке В (на рисунке прямая b), это максимум данной функции.



2. Симплексный метод
Задание 2.

Предположим, что в производстве двух видов продукции А и В принимают участие три предприятия. При этом на изготовление единицы изделия А первое предприятие тратит 5 ч, второе предприятие – 9 ч, третье предприятие – 10 ч. На изготовление единицы изделия В первое предприятие тратит 7 ч, второе предприятие – 9 ч, третье предприятие – 8 ч. На производство всех изделий первое предприятие может затратить не более чем 343 ч, второе предприятие – 587 ч, третье предприятие – 587 ч. От реализации единицы готовой продукции вида А прибыль составляет 11 руб., а вида В – 7 руб.

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

Представим данные этой задачи в виде таблицы:




Изделие А ч.

Изделие В ч.

Допустимые затраты ч.

I предприятие

5

7

343

II предприятие

9

9

587

III предприятие

10

8

587

Прибыль от реализации руб.

11

7




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

Составим систему ограничений.
Приведем систему ограничений в классическом виде:

Составим симплекс-таблицу:





























343

5

7

1

0

0

343/5=68.6




587

9

9

0

1

0

587/9=65.2




587

10

8

0

0

1

587/10=58.7

F

0

-11

-7

0

0

0




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

Получим таблицу следующего вида:































0






















0



















58,7

1

0,8

0

0

0,1




F




0
















После вычислений получим:




























49,5

0

3

0

0

-0,5







58,7

0

1,8

0

0

-0,9







58,7

1

0,8

0

0

0,1




F

645,7

0

1,8

0

0

1,1





В данной таблице нижняя строка F не содержит отрицательных значений, а значит мы пришли к оптимальному решению задачи. Причем наиболее выгодным оказалось производство изделия А, а на первом и втором предприятиях образовались излишки рабочего времени, соответственно 49,5 и 58,7 часов. Для увеличения объемов выпуска необходимо повысить эффективность третьего предприятия.
X (58.7; 0; 49.5; 58.7; 0)

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

I.




0

68.6




49

0


II.




0

65.2




65.2

0


III.




0

58.7




73.4

0


Область значений данной системы равенств ограничена отрезком координатной прямой y от 0 до 49, отрезком координатной прямой x от 0 до 58,7, отрезком прямой I от пересечения с координатной прямой y до пересечения с прямой III и прямой III от пересечения с прямой I до пересечения с координатной прямой x.

Для того чтобы найти минимальное и максимальное значение функции при заданных ограничениях, построим нормальный вектор

(11; 7), затем построим перпендикулярно вектору прямую, проходящую через начало координат, перемещая данную прямую в направлении вектора заметим что она входит в область определения в точке 0 (на рисунке прямая а), это минимум данной функции. При дальнейшем перемещении прямой видно, что она выходит из области определения в точке В (на рисунке прямая b), это максимум данной функции.


3. Транспортная задача.
Задание 3. Имеются три пункта поставки однородного груза

и четыре пункта потребления этого груза. На пунктах

находится груз соответственно в количестве 300, 320 и 380 т. В пункты требуется доставить соответственно 250, 200, 290 и 260 т груза. Расстояние между пунктами поставки и пунктами потребления приведено в следующей таблице:


Пункты отправления

Пункты назначения

Запасы
















1

4

5

11

300




12

8

3

14

320




10

15

7

9

380

Потребности

250

200

290

260

1000


Решение:

Данная задача имеет закрытую модель, так как суммарная мощность поставщиков равна суммарному спросу потребителей. И действительно 300+320+380=1000 и 250+200+290+260=1000.

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

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос













250

200

290

260




300

1

4

5

11




320

12

8

3

14




380

10

15

7

9

Согласно правилу учета наименьших затрат мы должны дать поставку в клетку имеющую наименьший показатель затрат, это клетка (А1; В1) показатель затрат равен 1, в эту клетку мы дадим 250 единиц груза, при этом потребности В1 удовлетворены полностью, а мощность поставщика А1 уменьшились до 50 единиц груза.

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос













250-250=0

200

290

260




300-250=50

1 250

4

5

11




320

12

8

3

14




380

10

15

7

9



Далее мы дадим поставку в клетку (А2; В3), где показатель затрат равен 3. Передав в эту клетку 290 единиц груза, мы полностью удовлетворим потребности пункта В3 и уменьшим мощность поставщика А2 до 30 единиц груза.

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос













0

200

290-290=0

260




50

1 250

4

5

11




320-290=30

12

8

3 290

14




380

10

15

7

9

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

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос













250-250

200-50-30-120

290-290

260-260




300-250-50

1 250

4 50

5

11




320-290-30

12

8 30

3 290

14




380-120-260

10

15 120

7

9 260

При данном распределении поставок целевая функция F будет равна:

F=250+4*50+8*30+15*120+3*290+9*260=5700

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

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос



















250

200

290

260







300

1 250

4 50

5

11







320

12

8 30

3 290

14







380

10

15 120

7

9 260






















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

Впишем в правый верхний угол каждой клетки ее оценку.


Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос
















250

200

290

260




300

1 250

4 50

5

11

-1




320

12

8 30

3 290

14

-5




380

10

15 120

7

9 260

-12




0

-3

2

3





Таким образом определили, что первоначальное распределение поставок не является оптимальным (в клетках (А3; В1) и (А3; В3) отрицательные оценки). Необходимо произвести перераспределение поставок. Сделаем поставку в клетку (А3; В3). Но очевидно, что поставка в эту клетку повлечет изменения поставок в соседние клетки, другими словами образуется цикл. Передадим 120 единиц груза из клетки (А3; В2) в клетку (А3; В3), затем увеличим на 120 единиц поставку в клетку (А2; В2), а поставку в клетке (А2; В3) уменьшим на 120 единиц. Получили:

Пункты отправления

Мощности поставщиков


Пункты назначения и их спрос
















250

200

290

260




300

1 250

4 50

5

11

-1




320

12

8 150

3 170

14

-5




380

10

15

7 120

9 260

-9




0

-3

2

0




При данном распределении поставок целевая функция F будет равна:

F=250+4*50+8*150+3*170+7*120+9*260=5340

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

Следует отметить, что данное распределение поставок могло бать получено при первоначальном распределении по правилу северо-западного угла.


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

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

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