Главная страница

Контрольная. Задача 37 b j a i запасы b 1 100


Скачать 59.61 Kb.
НазваниеЗадача 37 b j a i запасы b 1 100
Дата14.12.2021
Размер59.61 Kb.
Формат файлаdocx
Имя файлаКонтрольная.docx
ТипЗадача
#302802
страница2 из 2
1   2

Задание 2


Симплекс-метод основан на последовательном приближении к оптимальности. Процедура симплекс-метода включает 3 существенных элемента:

  • указывается способ нахождения исходного (опорного) плана;

  • устанавливается признак, дающий возможность проверить, является ли допустимый план оптимальным;

  • формулируются правила, по которым неоптимальный план можно улучшить.

В математическую постановку задачи входит построение ограничений и целевой функции.

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

Особенность метода состоит в том, что составление первоначального плана основывается на понятии «базиса» – совокупности линейно независимых векторов.

Таблица 2.1– Исходные данные

Пример № 1

Способ изготовления продукции

Ограничения на запасы ресурсов по месяцам

Итого

Цена единицы продукции

первый

второй

третий

65

85

75

ресурсы

Затраты ресурсов на единицу продукции ai.j; i=1,2,3; j=1,2,3

1 месяц

2 месяц

3 месяц




сырье, (усл. ед.)

4,75

5,3

4,25

3500

3400

3500




труд (чел.-час)

3,72

1,83

2,92

1850

1800

1800

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

(станко -час)

1,85

1,11

1,49

1000

1000

1000







Заявки по месяцам

700

720

740

2160


Решение

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

Определим максимальное значение целевой функции

F(X) = 65x1+85x2+75x3 

при следующих условиях-ограничений.

4,75x1+5,3x2+4,25x3≤3500
3,72x1+1,83x2+2,92x3≤1850
1,85x1+1,11x2+1,49x3≤1800
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

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

4.75x1+5.3x2+4.25x3+x4 = 3500

3.72x1+1.83x2+2.92x3+x5 = 1850

1.85x1+1.11x2+1.49x3+x6 = 1800

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

A =

4,75

5,3

4,25

1

0

0

3,72

1,83

2,92

0

1

0

1,85

1,11

1,49

0

0

1













Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных: x4, x5, x6

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

X0 = (0,0,0,3500,1850,1800)

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

Базис

B

x1

x2

x3

x4

x5

x6

x4

3500

4.75

5.3

4.25

1

0

0

x5

1850

3.72

1.83

2.92

0

1

0

x6

1800

1.85

1.11

1.49

0

0

1

F(X0)

0

-65

-85

-75

0

0

0

Итерация №0.

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

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

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

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

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

Вычислим значения Di по строкам как частное от деления: bi / ai2
и из них выберем наименьшее:

min (3500 : 5,3 , 1850 : 1,83 , 1800 : 1,11 ) = 660,377

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


Базис

B

x1

x2

x3

x4

x5

x6

min

x4

3500

4,75

5,3

4,25

1

0

0

660,38

x5

1850

3,72

1,83

2,92

0

1

0

1010,93

x6

1800

1,85

1,11

1,49

0

0

1

1621,62

F(X1)

0

-65

-85

-75

0

0

0





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

Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 1 войдет переменная x2.
Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=5.3.

На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули.

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

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

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

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

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

B

x1

x2

x3

x4

x5

x6

3500

4.75

5.3

4.25

1

0

0

1850

3.72

1.83

2.92

0

1

0

1800

1.85

1.11

1.49

0

0

1

0

-65

-85

-75

0

0

0


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

Базис

B

x1

x2

x3

x4

x5

x6

x2

660.38

0.9

1

0.8

0.19

0

0

x5

641.51

2.08

0

1.45

-0.35

1

0

x6

1066.98

0.86

0

0.6

-0.21

0

1

F(X1)

56132.08

11.18

0

-6.84

16.04

0

0


Итерация №1.

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

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

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

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

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

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

bi / ai3

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

min (660,377 : 0,802 , 641,509 : 1,453 , 1066,981 : 0,6 ) = 441,644

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

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


Базис

B

x1

x2

x3

x4

x5

x6

min

x2

660.38

0.9

1

0.8

0.19

0

0

823.53

x5

641.51

2.08

0

1.45

-0.35

1

0

441.64

x6

1066.98

0.86

0

0.6

-0.21

0

1

1778.58

F(X2)

56132.08

11.18

0

-6.84

16.04

0

0





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

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

Строка, соответствующая переменной x3 в плане 2, получена в результате деления всех элементов строки x5 плана 1 на разрешающий элемент РЭ=1.453. На месте разрешающего элемента получаем 1.

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

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

B

x1

x2

x3

x4

x5

x6

660,377

0,896

1

0,802

0,189

0

0

641,509

2,08

0

1,453

-0,345

1

0

1066,981

0,855

0

0,6

-0,209

0

1

56132,075

11,179

0

-6,84

16,038

0

0


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

Базис

B

x1

x2

x3

x4

x5

x6

x2

306,23

-0,25

1

0

0,38

-0,55

0

x3

441,64

1,43

0

1

-0,24

0,69

0

x6

802,04

-0,00382

0

0

-0,067

-0,41

1

F(X2)

59152,76

20,97

0

0

14,41

4,71

0


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

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

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


Базис

B

x1

x2

x3

x4

x5

x6

x2

306,23

-0,25

1

0

0,38

-0,55

0

x3

441,64

1,43

0

1

-0,24

0,69

0

x6

802,04

-0,00382

0

0

-0,067

-0,41

1

F(X3)

59152,76

20,97

0

0

14,41

4,71

0

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

x1 = 0, x2 = 306,228, x3 = 441,644

F(X) = 65*0 + 85*306,228 + 75*441,644 = 59152,757

Анализ оптимального плана.

В оптимальный план вошла дополнительная переменная x6.

Следовательно, при реализации такого плана имеются недоиспользованные ресурсы 3-го вида в количестве 802.036.

Значение 20.973> 0 в столбце x1 означает, что использование x1 - не выгодно.

Значение 0 в столбце x2 означает, что использование x2 - выгодно.

Значение 0 в столбце x3 означает, что использование x3 - выгодно.

Значение 14.412 в столбце x4 означает, что теневая цена (двойственная оценка) равна y1=14.412.

Значение 4.709 в столбце x5 означает, что теневая цена (двойственная оценка) равна y2=4.709.

Значение 0 в столбце x6 означает, что теневая цена (двойственная оценка) равна y3=0.

Список литературы



1   2


написать администратору сайта