Лабораторные работы по Основам теории систем

Лабораторная работа № 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 Управляемые параметры

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

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

– решение.

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

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

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

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

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

(л).

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

(л).

(л).

(л).

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

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

4. Решение.

при:

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

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

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

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

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

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

=>

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

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

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

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

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

;

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