Методические материалы по курсу «экономико-математическое моделирование»


Тема 2. Задачи линейного программирования (ЗЛП)



страница5/9
Дата06.06.2016
Размер0.64 Mb.
ТипЛитература
1   2   3   4   5   6   7   8   9

Тема 2. Задачи линейного программирования (ЗЛП)



Пример задачи 1.

Решить ЗЛП графическим способом.

Требуется найти max L = x1 + 4x2,

при ограничениях


Решение задачи:

Запишем уравнения граничных прямых и построим их на плоскости x1ox2



EMBED CorelDRAW.Graphic.11


Рис. 1. Решение ЗЛП геометрическим способом
Выделив область решения каждого неравенства системы ограничений, получим многоугольник допустимых решений ЗЛП.

На рис. 1 видно, что областью допустимых решений является многоугольник ONAC.

Построим основную прямую L = 0, то есть x1 + 4x2 = 0, проходящую через начало координат O (0,0) перпендикулярно вектору . Перемещая прямую L = 0 в направлении вектора , находим максимальную точку A, в которой пересекаются прямые L2 и L3, и координаты которой: x1 = 3, x2 = 1. Минимальной точкой является точка начала координат.

Итак, Omin (0,0), Amax (3;1). Тогда Lmin = 0, Lmax = 7



Пример задачи 2. Решить ЗЛП симплексным методом


х10; х20; х30.
Решение задачи:
Приведем данную ЗЛП к канонической форме. Запишем ограничения – неравенства в форме ограничений - равенств, для чего введем дополнительные переменные х4, х5, х6:

18х1 + 15х2 + 12х3 + х4 = 360,

6х1 + 4х1 + 8х3 + х5 = 192,

5х1 + 3х2 + 3х3 +х6 = 180,

Составим симплекс – таблицу (табл. 11).

В табл. 11 (итерация 0) имеем базисное решение Б1 (0; 0; 0; 360; 192; 180). Данное решение не оптимально, т.к. при Fmax коэффициенты в строке оценок целевой функции должны быть положительны – условие оптимальности задачи.

Исключаем переменные, содержащие в строке оценок F отрицательные коэффициенты. Допустим, это будет переменная х3. Для выбора разрешающего элемента (с целью получения неотрицательных решений) используется правило симплекс – преобразования: для всех положительных элементов столбца исключаемой переменной х3 вычисляется отношение свободного члена строки к ним самим, т.е bi/aij. Выбирается наименьшее из отношений, а соответствующий ему коэффициент aij - за разрешающий элемент.

Таблица 11



Итерация

Базис

х1 х2 х3 х4 х5 х6


bi

bi/aij

0


x4

x 5

x 6

18 15 12 1 0 0

6 4 8 0 1 0

5 3 3 0 0 1


360

192


180

30

24

60



F

-9 -10 -16 0 0 0

0



1


x 4

x 3

x 6

9 9 0 1 -12/8 0

6/8 4/8 1 0 1/8 0

22/8 12/8 0 0 3/8 1


72

24

108



8

48

72



F

3 -2 0 0 2 0

384



2


x 2

x 3

x 6

1 1 0 1/9 -1/6 0

1/4 0 1 -1/18 57/72 0

5/4 0 0 -1/6 117/72 1


8

20

96






F

5 0 0 2/9 11 0

400




Наименьшее отношение дает коэффициент , который выбирается за разрешающий элемент.

Для пересчета таблицы относительно этого разрешающего элемента используется следующий порядок:

1) Разрешающая строка (вторая) делится на разрешающий элемент a23 .

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

3) Все остальные строки и столбцы таблицы пересчитываются по правилу прямоугольника. Суть его состоит в том, что пересчитываемый элемент аi,j всегда составляет с разрешающим а23 диагональ прямоугольника и весь расчет производится по диагоналям этого прямоугольника по следующей схеме (если пересчитывается а11 ):

,

По данной схеме рассчитываются все элементы таблицы, включая строку целевой функции и столбец свободных членов.

Результаты пересчета представлены в табл. 11 (первая итерация), новое базисное решение Б2 = (0; 0; 24; 72; 0; 108).

Целевая функция F = 384.

Однако это решение не оптимально, т.к. в строке оценок целевой функции F имеется отрицательный элемент (при переменной х2). Следовательно, на новом шаге итерации необходимо исключить переменную х2, а за разрешающий элемент взять = 9, т.к. он дает наименьшее отношение bi/aij.

Пересчитывается таблица относительно разрешающего элемента a22, результаты пересчета представлены в табл. 11 (итерация 2). Все коэффициенты в строке оценок целевой функции положительны. Следовательно, решение оптимально.

Базисное решение (оптимальное) Б3 = (0; 8; 20; 0; 0; 96).

Целевая функция F = 400.





Каталог: books -> met files
met files -> А. А. Потехин А. Ю. Чурин С. В. Оболенский измерение вольт-амперных характеристик Полупроводникового Диода
met files -> Измерение параметров полупроводников с помощью эффекта холла
met files -> Исследование динамических систем: построение фазовых портретов и бифуркационных диаграмм Методическое пособие
met files -> Учебная программа курса специализации
met files -> Н. И. Лобачевского А. П. Горшков, С. В. Тихов физика поверхности полупроводников учебное пособие
met files -> Составители: старший преподаватель А. П. Горшков, профессор И. А. Карпович, инженер Л. А. Истомин Кафедра физики полупроводников и оптоэлектроники физического факультета ннгу
met files -> О. С. Сухих Традиции Ф. М. Достоевского в русской литературе ХХ века Учебно-методическое пособие
met files -> Н. И. Лобачевского общая теория статистики: методические материалы и задания для контрольных работ учебно-методическое пособие
met files -> О. С. Сухих Достоевский и мировая литература Учебно-методическое пособие


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7   8   9


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

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