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

Автор работы: Пользователь скрыл имя, 26 Мая 2015 в 17:36, контрольная работа

Краткое описание

Фабрика выпускает 3 вида тканей, причём суточное плановое задание составляет не менее 90м тканей 1-го вида, 70м- 2, 60м- 3. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на 1м представлен в таблице. Цена за 1м равна 80 у.е.- 1 вид, 70-2й, 60-3й. Определить сколько метров ткани каждого вида следует выпускать, чтобы общая стоимость выпускаемой продукции была максимальной.

Содержание

Ситуация №1. Построить математическую модель задачи оптимизации производства.
Ситуация №2. Построить математическую модель задачи. Составить задачу, двойственную к исходной.

Прикрепленные файлы: 1 файл

Методы оптимальных решений ситуация 1-2.docx

— 86.45 Кб (Скачать документ)

Вариант 3

Ситуация №1

 

Построить математическую модель задачи оптимизации производства.

Фабрика выпускает 3 вида тканей, причём суточное плановое задание составляет не менее 90м тканей 1-го вида, 70м- 2, 60м- 3. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на 1м представлен в таблице. Цена за 1м равна 80 у.е.- 1 вид, 70-2й, 60-3й. Определить сколько метров ткани каждого вида следует выпускать, чтобы общая стоимость выпускаемой продукции была максимальной.

 

Ресурсы

1

2

3

Оборудование

2

3

4

Сырьё

1

4

5

Электроэнергия

3

4

2


 

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

 

 

Учитывая минимальный объём производства преобразуем условие задачи.

 

Смысл данного преобразования заключается в том, чтобы уменьшить заданные ресурсы, на тот обязательный объём, который необходимо произвести и исключить данные ограничения.В дальнейшем при рассмотрении итогового решения данное условие будет добавлено в целевую функцию.

 

Далее решим задачу симплекс методом.

 

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

Определим максимальное значение целевой функции F(X) = 80x1 + 70x2 + 60x3 при следующих условиях-ограничений.

2x1 + 3x2 + 4x3≤150

x1 + 4x2 + 5x3≤180

3x1 + 4x2 + 2x3≤120

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≤) вводим базисную переменную x5. В 3-м неравенстве смысла (≤) вводим базисную переменную x6. 

2x1 + 3x2 + 4x3 + 1x4 + 0x5 + 0x6 = 150

1x1 + 4x2 + 5x3 + 0x4 + 1x5 + 0x6 = 180

3x1 + 4x2 + 2x3 + 0x4 + 0x5 + 1x6 = 120

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A = | 2;3;4;1;0;0;1;4;5;0;1;0;3;4;2;0;0;1

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

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

Решим систему уравнений относительно базисных переменных:

x4, x5, x6,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,0,150,180,120)

 

 

 

 

Базисное решение называется допустимым, если оно неотрицательно.

 

Базис

B

x1

x2

x3

x4

x5

x6

x4

150

2

3

4

1

0

0

x5

180

1

4

5

0

1

0

x6

120

3

4

2

0

0

1

F(X0)

0

-80

-70

-60

0

0

0


Переходим к основному алгоритму симплекс-метода.

Итерация №0.

1. Проверка критерия  оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai1

и из них выберем наименьшее:

min (150 : 2 , 180 : 1 , 120 : 3 ) = 40

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

min

x4

150

2

3

4

1

0

0

75

x5

180

1

4

5

0

1

0

180

x6

120

3

4

2

0

0

1

40

F(X1)

0

-80

-70

-60

0

0

0

0


 

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x6 в план 1 войдет переменная x1.

Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3

На месте разрешающего элемента в плане 1 получаем 1.

В остальных клетках столбца x1 плана 1 записываем нули.

Таким образом, в новом плане 1 заполнены строка x1 и столбец x1.

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

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

НЭ = СЭ - (А*В) /РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B

x 1

x 2

x 3

x 4

x 5

x 6

150-(120 • 2):3

2-(3 • 2):3

3-(4 • 2):3

4-(2 • 2):3

1-(0 • 2):3

0-(0 • 2):3

0-(1 • 2):3

180-(120 • 1):3

1-(3 • 1):3

4-(4 • 1):3

5-(2 • 1):3

0-(0 • 1):3

1-(0 • 1):3

0-(1 • 1):3

120 : 3

3 : 3

4 : 3

2 : 3

0 : 3

0 : 3

1 : 3

0-(120 • -80):3

-80-(3 • -80):3

-70-(4 • -80):3

-60-(2 • -80):3

0-(0 • -80):3

0-(0 • -80):3

0-(1 • -80):3


 

Получаем новую симплекс-таблицу:

Базис

B

x1

x2

x3

x4

x5

x6

x4

70

0

1/3

22/3

1

0

-2/3

x5

140

0

22/3

41/3

0

1

-1/3

x1

40

1

11/3

2/3

0

0

1/3

F(X1)

3200

0

362/3

-62/3

0

0

262/3


 

Итерация №1.

1. Проверка критерия  оптимальности.

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

2. Определение  новой базисной переменной.

В качестве ведущего выберем столбец, соответствующий переменной x3, так как это наибольший коэффициент по модулю.

3. Определение  новой свободной переменной.

Вычислим значения Di по строкам как частное от деления: bi / ai3

и из них выберем наименьшее:

min (70 : 22/3 , 140 : 41/3 , 40 : 2/3 ) = 261/4

Следовательно, 1-ая строка является ведущей.

Разрешающий элемент равен (22/3) и находится на пересечении ведущего столбца и ведущей строки.

Базис

B

x1

x2

x3

x4

x5

x6

min

x4

70

0

1/3

22/3

1

0

-2/3

261/4

x5

140

0

22/3

41/3

0

1

-1/3

324/13

x1

40

1

11/3

2/3

0

0

1/3

60

F(X2)

3200

0

362/3

-62/3

0

0

262/3

0


 

4. Пересчет симплекс-таблицы.

Формируем следующую часть симплексной таблицы.

Вместо переменной x4 в план 2 войдет переменная x3.

Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=22/3

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x3 плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x3 и столбец x3.

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