Учебная работа № 1995. Лабораторные работы по Основам теории систем

Учебная работа № 1995. Лабораторные работы по Основам теории систем

Лабораторная работа № 2

Телешовой Елизаветы, гр. 726,

Цель работы: Решение задач линейного программирования симплексметодом. Варианты разрешимости задач линейного программирования.

1 вариант.

1. Четыре студента: Иванов, Петров, Сидоров и Васильев пошли на концерт группы «Чайф», захватив пиво 2 сортов: «Русич» и «Премьер». Определить план распития напитков для получения максимального суммарного опьянения (в ). Исходные данные даны в таблице:

Студент Норма выпитого

Запасы

(в литрах)

«Русич» «Премьер»
Иванов 2 2 1.5
Петров 3,5 1 1,5
Сидоров 10 4 4,5
Васильев 1 0,7
Крепость напитка 16 % 10 %

2. Математическая модель.

2.1 Управляемые параметры

x1[л] – количество выпитого пива «Русич».

x2[л] – количество выпитого пива «Премьер».

– решение.

2.2 Ограничения

– количество пива «Русич», выпитого Ивановым.

– количество пива «Премьер», выпитого Ивановым.

– общее количество пива, выпитого Ивановым.

Общее количество пива, выпитого Ивановым, не превосходит имеющихся у него запасов пива, поэтому:

(л).

Аналогично строим другие ограничения:

(л).

(л).

(л).

3. Постановка задачи.

Найти *, где достигается максимальное значение функции цели:

4. Решение.

при:

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

Определим начальный опорный план: .

Это решение является опорным, т.к. вектора условий при положительных компонентах решения линейно независимы, также , где , но не все оценки положительны (, где )

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

Предположим, что , тогда:

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

=>

При увеличении , первой перестает выполнять условие неотрицательности переменная , т.к. она первая обращается в ноль. Значит выведем из базиса . Теперь базисными переменными являются , а свободными . Для анализа этого плана выразим функцию цели через новые переменные.

Из ограничения (2) имеем: .

Подставляя в функцию цели: получаем:

Оформим данный этап задачи в виде симплекстаблицы:

Начальная симплекстаблица:

16 10 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

в
0

X3

2 2 1 0 0 0 1,5
0

X4

3,5 1 0 1 0 0 1,5
0

X5

10 4 0 0 1 0 4,5
0

X6

0 1 0 0 0 1 0,7
F 16 10 0 0 0 0 0

;

Пересчитаем элементы исходной таблицы по правилу четырехугольника:

16 10 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В
0

X3

0 1,428 1 0,572 0 0 0,642
16

X1

1 0,286 0 0,286 0 0 0,428
0

X5

0 1,14 0 2,86 1 0 0,214
0

X6

0 1 0 0 0 1 0,7
F 0 5,424 0 4,576 0 0 6,857

;

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (2) и (3): . Тогда: ;

16 10 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В

0

X3

0 0 1 3 1,25 0 0,375
16

X1

1 0 0 1 0,25 0 0,375
10

X2

0 1 0 2,5 0,875 0 0,1875
0

X6

0 0 0 2,5 0,875 1 0,5125
F 0 0 0 9 4,75 0 7,875

Пересчитав все оценки, видим, что , значит критерий можно улучшить. Будем увеличивать . Пусть , тогда:

откуда получаем:

;

Все оценки опорного плана должны быть неотрицательны, а значит должны выполняться условия:

=>

Выведем из базиса . Теперь базисными переменными являются , а свободными . Выразим функцию цели через новые переменные:

, а из ограничений (1) и (2): . Тогда: ;

16 10 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

в
0

X4

0 0 0,333 1 0,416 0 0,125
16

X1

1 0 0,333 0 0,166 0 0,25
10

X2

0 1 1,833 0 0,166 0 0,5
0

X6

0 0 0,833 0 0,166 1 0,2
F 0 0 3 0 1 0 9

Видим, что все оценки положительны, значит любое увеличение какойлибо свободной переменной уменьшит критерий. Данное решение является оптимальным. Изобразим это решение на графике:

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

2 вариант.

Отмечая успешно сданную сессию, вышеупомянутые студенты взяли столько же пива и в таких же пропорциях, за исключением того, что вместо пива «Премьер» было куплено пиво «Окское», крепость которого 6,4 % (дешевое и разбавленное). Определить план распития напитков для получения максимального суммарного опьянения (в ).

Функция цели: .

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

=>

Решаем симплексметодом:

16 6,4 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В
0

X3

2 2 1 0 0 0 1,5
0

X4

3,5 1 0 1 0 0 1,5
0

X5

10 4 0 0 1 0 4,5
0

X6

0 1 0 0 0 1 0,7
F 16 10 0 0 0 0 0

,

16 6,4 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В
0

X3

0 1,428 1 0,571 0 0 0,642
16

X1

1 1,286 0 0,286 0 0 0,428
0

X5

0 1,142 0 2,85 1 0 0,214
0

X6

0 1 0 0 0 1 0,7
F 0 1,82 0 4,571 0 0 6,857

;

16 6,4 0 0 0 0

Св

Б.П.

X1

X2

X3

X4

X5

X6

В
0

X3

0 0 1 3 1,25 0 0,375
16

X1

1 0 0 1 0,25 0 0,375
6,4

X2

0 1 0 2,5 0,875 0 0,1875
0

X6

0 0 0 2,5 0,875 1 0,5125
F 0 0 0 0

Учебная работа № 1995. Лабораторные работы по Основам теории систем

Яндекс.Метрика