Контрольная работа по "Методы принятия оптимальных решений"

Автор работы: Пользователь скрыл имя, 21 Января 2015 в 19:44, контрольная работа

Описание работы

Целевая функция в виде нулевой линии уровня F0 проходит через начало координат. Если перемещать эту линию в направлении вектора – вниз, скользя началом линии по оси х1, то значения целевой функции будут возрастать от нуля до бесконечности при х2 = 0. Если её перемещать в противоположном направлении, скользя началом линии по прямой -х1 + х2 = 1, то значения целевой функции будут уменьшаться от нуля до бесконечности при х1 ≥ x2 – 1.

Содержание работы

Задача 1 3
Задача 2 5
Задача 3 11
Задача 4 15
Задача 5 17

Файлы: 1 файл

Методы оптимальных решений.doc

— 413.00 Кб (Скачать файл)

Для построения модели двойственной задачи преобразуем столбцы системы неравенств прямой задачи в строки, заменяя величины запасов сырья прибылью α, β, γ, δ, а знаки "меньше" знаками "больше". Получим математическую модель двойственной задачи, где целевая функция достигает минимума:

       

Решение этой задачи получено в нижней строке последней симплекс-таблицы:

Wmin = 123,4375;   y1 = 1,0625;  y2 = 0; y3 = 0,7031.

Проверка:

Wmin = 50∙1,0625 + 40∙0 + 100∙0,70313 = 123,438 = Zmax.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Задача 3.Четыре предприятия данного экономического района для производства продукции использует три вида сырья. Потребности в сырье каждого из предприятий соответственно равны b1, b2, b3 и b4 ед. Сырье сосредоточено в трёх местах его получения, а запасы соответственно равны a1, a2, a3 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

;

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

 

В1

В2

В3

В4

 

А1

6

7

2

4

90

А2

3

5

9

8

110

А3

10

2

6

7

100

 

120

50

80

50

 

Решение: Проверим задачу на соответствие ресурсов и потребностей:

SAi = 90 + 110 + 100 = 300;   SВi = 120 + 50 + 80 + 50 = 300.

Т.к. SАi = SВi, то это транспортная задача закрытого типа.

Составляем первоначальный опорный план по методу минимального элемента. В верхний правый угол клеток вписана стоимость перевозки.

 

 

 

 

Вj

Аi

В1

120

В2

50

В3

80

В4

50

Ui

А1 = 90

+ 6

-1

7

 

8

2

80

- 4

10

U1 = 0

А2 = 110

3

110

5

 

10

9

 

11

8

 

8

U2 = -4

А3 = 100

- 10

10

2

50

6

 

1

+ 7

40

U3 = 3

Vj

V1 = 7

V2 = -1

V3 = 2

V4 = 4

№1


Минимальная стоимость (2) в клетках А1В3 и А3В2 – закрываем потребности В3 и В2 поставкой из А1 и А3 и столбцы В2 и В3 исключаем из дальнейшего рассмотрения.

Следующий минимум в не исключённых столбцах и строках (3) в клетке А2В1 –  весь груз из А2 отправляем потребителю В1 и строку А2 исключаем из дальнейшего рассмотрения.

Следующий минимум (4) в клетке А1В4  –  остаток груза из А1 отправляем потребителю В4 и строку А1 исключаем из дальнейшего рассмотрения.

Осталось лишь 50 единиц груза у поставщика А3, которые распределяем между потребителями В1 и В4, закрывая их потребности.

Опорный план составлен. Число заполненных клеток должно быть:

m + n – 1 = 3 + 4 – 1 = 6,

Фактически число заполненных клеток 6, т.е. план не вырожден.

 Цена этого плана:

Z1 = 80∙2 + 10∙4 + 110∙3 + 10∙10 + 50∙2 + 40∙7 = 1010.

Проверяем оптимальность плана методом потенциалов, присвоив первой строке нулевой потенциал U1 = 0. Потенциалы других строк и столбцов определяем по формулам:

Ui = Cij – Vj;      Vj = Cij  – Ui,

где Cij – стоимость перевозок, записанная в правом верхнем углу клеток.

V3 = C13 – U1 = 2 – 0 = 2;     V4 = C14 – U1 = 4 – 0 = 4;       U3 = C34 – V4 = 7 – 4 = 3;  

V1 = C31 – U3 = 10 – 3 = 7;   V2 = C32 – U3 = 2 – 3 = -1;   U2 = C21 – V1 = 3 – 7 = -4;   

Определяем характеристики клеток, оставшихся свободными по формуле:

Eij = Cij – (Vj + Ui):  (вписаны в левый нижний угол):

Е11 = С11 – (V1 + U1) = 6 – (7 + 0) = -1; Е12 = С12 – (V2 + U1) = 7 – (-1+ 0) = 8;

Е22 = С22 – (V2 + U2) = 5 – (-1 – 4) = 10;   Е23 = С23 – (V3 + U2) = 9 – (2 – 4) = 11;

Е24 = С24 – (V4 + U2) = 8 – (4 – 4) = 8; Е33 = С33 – (V3 + U3) = 6 – (2 + 3) = 1;

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

Строим для клетки А1В1 цикл (показан пунктиром) и перемещаем по циклу наименьшую из перевозок (10), находящихся в углах цикла, отмеченных знаком "минус".

Вj

Аi

В1

120

В2

50

В3

80

В4

50

Ui

А1 = 90

6

10

7

 

8

2

80

4

0

U1 = 0

А2 = 110

3

110

5

 

9

9

 

10

8

 

7

U2 = -3

А3 = 100

10

 

1

2

50

6

 

1

7

50

U3 = 3

Vj

V1 = 6

V2 = -1

V3 = 2

V4 = 4

№1


Получаем новый план. Его цена:

Z2 = 10∙6 + 80∙2 + 110∙3 + 50∙2 + 50∙7 = 1000.

что лучше первоначального плана на 10 ден. единиц.

Т.к. теперь число заполненных клеток оказалось равно 5, что меньше m + n – 1 = 6, то план стал вырожденным. Для устранения вырожденности плана вписываем в клетку А1В4 значение 0.

Определив потенциалы строк и столбцов (U1 = 0) и характеристики свободных клеток по тем же формулам, устанавливаем, что этот план оптимален, т.к. среди характеристик свободных клеток нет отрицательных.

Zопт = Zmin =  Z2 = 1000.

Т.о. оптимальный план перевозок:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Решение: Построим в осях Х1ОХ2 граничные прямые, соответствующие исходным неравенствам. Каждая из этих прямых делит плоскость на две части, одна из которых удовлетворяет неравенству. Подставив в неравенство координаты любой точки, например (0;0), находим эту полуплоскость (показано стрелками). В результате получен четырёхугольник ОАВС, ограничивающий часть плоскости, удовлетворяющую всем ограничениям – это область допустимых решений – ОДР (заштрихован). Точка В – точка пересечения прямых, заданных уравнениями системы ограничений.

Уточним границу области допустимых решений задачи целочисленного программирования. Для этого придадим переменной х1 целочисленные значения от 0 до 6 (значение х1 = 7 уже вне ОДР) и вычислим соответствующие значения х2 из обеих уравнений.

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

 

 

 

 

х1

0

1

2

3

4

5

6

х2 из неравенства 2х1+ х2 ≤ 13

≤ 13

≤ 11

≤ 9

≤ 7

≤ 5

≤ 3

≤ 1

х2 из неравенства -2х1+ 3х2 ≤ 18

≤ 6

≤ 6,667

≤ 7,333

≤ 8

≤ 8,667

≤ 9,333

≤ 10

х2

6

6

7

7

5

3

1


Целевая функция в виде нулевой линии уровня проходит через начало координат. Перемещая эту линию параллельно самой себе в направлении вектора , увеличиваем значение F. Узел этой ступенчатой линии, через которую проходит последняя линия уровня, определит наибольшее значение целевой функции. Этой вершиной оказалась точка L, координаты которой Е(6; 0).

Т.о. значения х1 = 6 и х2 = 0 обеспечивают максимальное значение целевой функции в целых числах:

 

 

 

 

 

 

 

 

 

 

 

 

Задача 5.Целочисленное линейное программирование.

На предприятии производятся изделия четырёх наименований, обладающие различной ценностью. В производственном процессе используются три вида сырья. Информация о ресурсе сырья, о нормах их расхода на единичное изделие и ценности изделий приведена в табл. 1:

 

Нормы расхода ресурсов на единичное изделие

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

Изделие 1

Изделие 2

Изделие 3

Изделие 4

Ресурс 1

3

7

1

1

50

Ресурс 2

1

4

2

5

40

Ресурс 3

4

7

12

10

100

Ценность

6

7

9,5

7

 

Решение: Обозначим х1 – выпуск изделия 1; х2 – выпуск изделия 2; х3 – выпуск изделия 3; х4 – выпуск изделия 4.

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

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

Z = αх1 + βх2 + γх2 + δх2 = 6х1 + 7х2 + 9,5х3 + 7х4 → max;

Преобразуем систему неравенств в систему уравнений, введя дополнительные переменные х5; х6; х7, которые дают начальный  базис:

Т.к. исходные данные те же, что и в задаче 3.6. то приведём сразу матрицу её решения:

Сi

Базис хi

Сi

В

6

7

9,5

7

0

0

0

x1

x2

х3

х4

х5

х6

х7

х1

6

15,625

1,000

2,406

0,000

1,188

0,375

0,000

-0,031

 

х6

0

18,125

0,000

2,031

0,000

2,938

-0,125

1,000

-0,156

 

х3

9,5

3,125

0,000

-0,219

1,000

0,438

-0,125

0,000

0,094

 

Z ≥ 0

123,4375

0,000

5,359

0,000

4,281

1,0625

0,000

0,70313

№3


Т.о. х1 = 15,625; х2 = х4 = 0; х3 = 3,125; Zmax = 123,4375.

Т.к. требуется целочисленное решение, то округлим полученные значения в меньшую сторону до х1 = 15 и х3 = 3, тогда:

Z = 15·6 + 9,5·3 = 118,5.

Максимально ли это решение в целочисленном исчислении?

Наибольшая дробная часть 0,625 имеется в значении переменной х1, поэтому для строки х1 последней симплекс-таблицы составляем дополнительное ограничение:

х1 + 2,406х2 + 1,118х4 + 0,375х5 – 0,031х7 ≥ 15,625;

Берём только дробные части чисел. Для числа (-0,031) дробная часть [-0,031-(-1) = 0,969].

Информация о работе Контрольная работа по "Методы принятия оптимальных решений"