Лекции по линейному программированию
  • Регистрация
1 1 1 1 1 1 1 1 1 1 Рейтинг 0.50 (1 Голос)

Универсальным вычислительным методом решения задачи ЛП является так называемый Симплекс-метод. Идея метода состоит в последовательном “улучшении” планов задачи по определенному критерию до получения оптимального решения.

Как уже было отмечено, оптимальное значение линейная целевая функция может достигать в крайних (граничных) точках ОДР, а именно в угловых точках. Важно заметить, что, если размерность задачи (количество переменных и количество ограничений) велики, то угловых точек может быть очень много и указать нужную становится весьма затруднительным делом, а определять оптимальное решение простым перебором весьма долгое и рутинное занятие.

Этих недостатков и лишен симплекс-метод, согласно которому: находясь в одной из вершин многогранной области - из всех соседних[1] вершин выбирается та, которая “улучшает” целевую функцию.

Рассмотрим процесс подготовки исходных данных и алгоритм решения задачи этим методом. Для решения задачи ЛП

Необходимо предварительно выполнить следующие процедуры:

·  привести математическую модель задачи к каноническому виду (систему активных ограничений типа неравенств привести к уравнениям путем введения дополнительных “искусственных” переменных);

·  определить начальное допустимое решение задачи;

·  ввести в исходную таблицу параметры, соответствующие начальному опорному плану;

·  весовые коэффициенты переменных целевой функции; переменные текущего базиса; значения базисных переменных (столбец ); элементы матрицы условий задачи (столбцы ); оценки “Дефект” -

Оценки определяются по формулам:

Весовые коэффициенты при базисных переменных проставляются в левый столбец таблицы. Значение целевой функции при текущем базисе

Заносятся в последнюю строку столбца

Алгоритм симплекс-метода.

Шаг I: Выбор начального базисного решения.

Шаг II: Переход от начального решения к другому допустимому базисному решению с лучшим значением целевой функции (все решения, которые “хуже” исключаются).

Шаг III: Продолжение поиска допустимых базисных решений. (Если полученное решение не является оптимальным, то симплекс-метод позволяет перейти к смежному допустимому базисному решению).

Шаг IV: Смежное допустимое базисное решение отличается только одной базисной переменной (независимая переменная становится базисной, а одна из базисных переменных становится независимой). Тем самым осуществляется переход на соседнюю вершину многогранника ОДР.

Критерий оптимальности. Обозначим относительную оценку небазисной переменной через

Оценки базисных переменных.

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

Проиллюстрируем все выше сказанное примером.

Приведем задачу к каноническому виду:

Здесь мы ввели в рассмотрение дополнительные переменные и , которые “уравновешивают” активные ограничения. Они же и образуют начальный базис.

Последовательные итерации удобно вести в компактном виде в таблице (см. таблицу I.).

Таблица I.

№ 1

3

2

0

0

0

   

0

-1

2

1

0

0

4

0

3

2

0

1

0

14

0

1

-1

0

0

1

3

3

3

2

0

0

0

 
рис. i. 2.3. графическое изображение ситуации, соответствующей таблице i.
Элемент -максимальный из положительных в строке , следовательно - Разрешающий столбец (он выделен). Таким образом, в базис необходимо ввести переменную . Далее, возникает вопрос о выводе из базиса одной из переменных. Ясно, что она выбирается далеко не произвольным образом. Для этого элементы столбца делим на соответствующие им по строке элементы разрешающего столбца и результат вписываем в рабочий столбец . При этом, отрицательный результат и результат деления на 0 заменяем знаком . Отсюда, по компонентам столбца видно, что при увеличении (которая должна войти в базис) переменная будет оставаться положительной. Переменная станет равной 0 при . Однако, переменная станет равной 0 быстрее, при . Это значение минимальное из компонент столбца . Таким образом, целесообразно сделать свободной, а базисной, тем самым осуществится переход на соседнюю вершину ОДР.

Далее элементарные гауссовы преобразования строк приведут исследователя к новому базису и новой таблице (таблица II).

Таблица II.

№ 2

3

2

0

0

0

   

0

0

1

1

0

1

7

7

0

0

5

0

1

-3

5

1

3

1

-1

0

0

1

3

0

5

0

0

-3

 

 
рис. i. 2.4. графическое изображение ситуации, соответствующей таблице ii.
Сформулируем последовательность операций перехода к таблице II.

·  Прибавить разрешающую строку к первой строке таблицы I. Результат записать в первую строку таблицы II.

·  Умножить разрешающую строку на -3 и прибавить ко второй строке таблицы I. Результат записать во вторую строку таблицы II.

·   
рис. i.2.5.
Третья строка таблицы II - это разрешающая строка таблицы I, элементы которой разделены на разрешающий элемент (в клетке на пересечении разрешающей строки и разрешающего столбца).

·  Строка так же вычисляется с помощью элементарных преобразований. По-прежнему, и это чрезвычайно важно, - рабочей строкой является разрешающая строка. Умножить третью строку таблицы I на -3 И прибавить к строке . Результат записать в строку таблицы II.

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

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

Далее процесс продолжается до тех пор пока не будет выполнен критерий оптимальности (см. таблицу III).

Таблица III.

№ 3

3

2

0

0

0

   

0

0

0

1

6

 

2

0

1

0

1

 

3

1

0

0

4

 

0

0

0

-1

0

Таким образом,

Изобразим графически полученную ситуацию (см. рисунок I. 2.5).

 

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

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

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

Таблица данных I.

Варианта

I

7

6

5

8

3

1

476

364

319

11

10

II

10

9

3

18

15

1

123

111

523

11

13

III

8

7

7

12

9

5

459

379

459

9

9

IV

8

7

7

10

5

2

612

492

562

11

9

V

10

9

5

6

3

1

735

765

455

8

4

VI

5

6

7

7

6

1

256

283

363

9

7

VII

3

9

10

5

3

2

414

723

788

12

16

VIII

7

7

8

5

2

1

347

300

357

11

7

IX

7

7

8

13

8

2

363

327

429

6

4

X

5

9

10

7

9

8

343

587

587

11

7

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

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

Таблица данных II.

Варианта

I

20

15

14

28

9

1

758

526

541

10

2

II

15

15

9

33

25

3

571

577

445

8

10

III

11

13

13

21

15

3

741

741

822

5

3

IV

14

12

8

8

4

2

624

541

376

7

3

V

19

16

19

26

17

8

868

638

853

5

4

VI

14

15

20

40

6

4

1200

993

1097

5

13

VII

9

15

15

27

15

3

606

614

575

5

7

VIII

13

13

11

11

23

1

608

802

840

11

6

IX

8

10

14

7

8

1

417

580

591

5

5

X

19

16

19

31

9

1

1121

706

1066

16

19

 

[1] Соседняя вершина ОДР - смежное допустимое решение.

Табличный симплекс-метод - 0.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

По темам:

История Украины

Культурология

Высшая математика

Информатика

Охотоведение

Статистика

География

Военная наука

Английский язык

Генетика

Разное

Технологиеские темы

Украинский язык

Филология

Философия

Химия

Экология

Социология

Физическое воспитание

Растениевосдство

Педагогика

История

Психология

Религиоведение

Плодоводство

Экономические темы

Бухгалтерские темы

Маркетинг

Иностранные языки

Ветеринарная медицина

Технические темы

Землеустройство

Медицинские темы

Творчество

Лесное и парковое хозяйство