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

Автор работы: Пользователь скрыл имя, 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 Кб (Скачать документ)

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

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

 

B

x 1

x 2

x 3

x 4

x 5

x 6

70 : 22/3

0 : 22/3

1/3 : 22/3

22/3 : 22/3

1 : 22/3

0 : 22/3

-2/3 : 22/3

140-(70 • 41/3):22/3

0-(0 • 41/3):22/3

22/3-(1/3 • 41/3):22/3

41/3-(22/3 • 41/3):22/3

0-(1 • 41/3):22/3

1-(0 • 41/3):22/3

-1/3-(-2/3 • 41/3):22/3

40-(70 • 2/3):22/3

1-(0 • 2/3):22/3

11/3-(1/3 • 2/3):22/3

2/3-(22/3 • 2/3):22/3

0-(1 • 2/3):22/3

0-(0 • 2/3):22/3

1/3-(-2/3 • 2/3):22/3

3200-(70 • -62/3):22/3

0-(0 • -62/3):22/3

362/3-(1/3 • -62/3):22/3

-62/3-(22/3 • -62/3):22/3

0-(1 • -62/3):22/3

0-(0 • -62/3):22/3

262/3-(-2/3 • -62/3):22/3


 

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

Базис

B

x1

x2

x3

x4

x5

x6

x3

261/4

0

1/8

1

3/8

0

-1/4

x5

261/4

0

21/8

0

-15/8

1

3/4

x1

221/2

1

11/4

0

-1/4

0

1/2

F(X2)

3375

0

371/2

0

21/2

0

25


 

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

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

Окончательный вариант симплекс-таблицы:

 

Базис

B

x1

x2

x3

x4

x5

x6

x3

261/4

0

1/8

1

3/8

0

-1/4

x5

261/4

0

21/8

0

-15/8

1

3/4

x1

221/2

1

11/4

0

-1/4

0

1/2

F(X3)

3375

0

371/2

0

21/2

0

25


Оптимальный план можно записать так:

x3 = 261/4

x1 = 221/2

F(X)усл. = 60•261/4 + 80•221/2 = 3375

Конечная функция будет иметь вид:

 

Ответ: 19075

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ситуация №2

 

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

 

Предприятие предложен на выбор выпуск 3 новых изделий, за счёт которых можно было бы расширить номенклатуру продукции предприятия при тех же запасах ресурсов. Нормы затрат ресурсов и прибыль от реализации единицы продукции для этих изделий представлены в таблице. Определить из предложенных видов изделия, выгодные для выпуска предприятием

 

Ресурсы

Объективно обусловленные оценки ресурсов

Затраты ресурсов на 1 изделие

А

Б

В

Труд

40

6

4

2

Сырьё

20

2

1

3

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

20

3

1

2

Прибыль на 1 изделие

 

80

70

45


 

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

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

6x1 + 4x2 + 2x3≤40

2x1 + x2 + 3x3≤20

3x1 + x2 + 2x3≤20

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

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

6x1 + 4x2 + 2x3 + 1x4 + 0x5 + 0x6 = 40

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

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

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

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

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

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

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

x4, x5, x6,

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

X1 = (0,0,0,40,20,20)

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

Базис

B

x1

x2

x3

x4

x5

x6

x4

40

6

4

2

1

0

0

x5

20

2

1

3

0

1

0

x6

20

3

1

2

0

0

1

F(X0)

0

-80

-70

-45

0

0

0


 

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

Итерация №0.

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

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

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

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

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

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

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

min (40 : 6 , 20 : 2 , 20 : 3 ) = 62/3

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

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

Базис

B

x1

x2

x3

x4

x5

x6

min

x4

40

6

4

2

1

0

0

62/3

x5

20

2

1

3

0

1

0

10

x6

20

3

1

2

0

0

1

62/3

F(X1)

0

-80

-70

-45

0

0

0

0


 

Поскольку в последнем столбце присутствует несколько минимальных элементов 62/3, то номер строки выбираем по правилу Креко.

Метод Креко заключается в следующем. Элементы строк, имеющие одинаковые наименьшие значения min=62/3, делятся на предполагаемые разрешающие элементы, а результаты заносятся в дополнительные строки. За ведущую строку выбирается та, в которой раньше встретится наименьшее частное при чтении таблицы слева направо по столбцам.

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

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

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

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

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

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

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

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

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

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

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

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

 

B

x 1

x 2

x 3

x 4

x 5

x 6

40-(20 • 6):3

6-(3 • 6):3

4-(1 • 6):3

2-(2 • 6):3

1-(0 • 6):3

0-(0 • 6):3

0-(1 • 6):3

20-(20 • 2):3

2-(3 • 2):3

1-(1 • 2):3

3-(2 • 2):3

0-(0 • 2):3

1-(0 • 2):3

0-(1 • 2):3

20 : 3

3 : 3

1 : 3

2 : 3

0 : 3

0 : 3

1 : 3

0-(20 • -80):3

-80-(3 • -80):3

-70-(1 • -80):3

-45-(2 • -80):3

0-(0 • -80):3

0-(0 • -80):3

0-(1 • -80):3


 

 

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

Базис

B

x1

x2

x3

x4

x5

x6

x4

0

0

2

-2

1

0

-2

x5

62/3

0

1/3

12/3

0

1

-2/3

x1

62/3

1

1/3

2/3

0

0

1/3

F(X1)

5331/3

0

-431/3

81/3

0

0

262/3

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