Методические указания к лабораторным работам по курсу “Математическое моделирование” (стр. 2 )

В последней строке таблицы с оценками Δk в столбце "А0" записываются значения целевой функции на опорном решении Z(X1).

Начальное опорное решение не является оптимальным, так как в задаче на максимум оценки Δ1 = -2, Δ3= -9 для векторов А1 и А3 отрицательные. Если в задаче на максимум хотя бы один вектор имеет отрицательную оценку, то можно найти новое опорное решение, на котором значение целевой функции будет больше.

Определим, введение какого из двух векторов приведет к большему приращению целевой функции.

Приращение целевой функции находится по формуле: .

Вычисляем значения параметра θ01 для первого и третьего столбцов по формуле:

Получаем θ01 = 6 при l = 1, θ03 = 3 при l = 1.

Находим приращение целевой функции при введении в базис первого вектора ΔZ1 = - 6*(- 2) = 12, и третьего вектора ΔZ3 = - 3*(- 9) = 27.

Следовательно, для более быстрого приближения к оптимальному решению необходимо ввести в базис опорного решения вектор А3 вместо первого вектора базиса А6, так как минимум параметра θ03 достигается в первой строке (l = 1).

Производим преобразование Жордана с элементом Х13 = 2, получаем второе опорное решение Х2 = (0,0,3,21,42,0) с базисом Б2 = (А3, А4, А5).

Это решение не является оптимальным, так как вектор А2 имеет отрицательную оценку Δ2 = — 6. Для улучшение решения необходимо ввести вектор А2 в базис опорного решения.

Определяем номер вектора, выводимого из базиса. Для этого вычисляем параметр θ02 для второго столбца, он равен 7 при l = 2. Следовательно, из базиса выводим второй вектор базиса А4. Производим преобразование Жордана с элементом х22 = 3, получаем третье опорное решение Х3 = (0,7,10,0,63,0) Б2 = (А3, А2, А5).

Это решение является единственным оптимальным, так как для всех векторов, не входящих в базис оценки положительные: Δ1 = 7/2, Δ4 = 2, Δ6 = 7/2.

Ответ: max Z(X) = 201 при Х = (0,7,10,0,63).

ТРЕБОВАНИЯ К ОТЧЕТУ

Отчет по лабораторной работе должен содержать:

1. Цель и порядок выполнения работы.

2. Математическую модель задачи и краткую характеристику математической модели.

3. Описание хода выполнения расчетов.

4. Результаты расчетов.

6. Выводы.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1.  В чем заключается основная идея симплекс-метода решения задач линейного программирования?

2.  Назовите разновидности задач линейного программирования.

3.  Опишите алгоритм симплексного метода решения задач линейного программирования.

4.  В чем заключается приведение задачи линейного программирования к каноническому виду?

5.  Дайте понятие целевой функции.

Лабораторная работа № 3. Решение задач линейного программирования средствами MS Excel: задача о смесях, задача об оптимальном распределении ресурсов

ЦЕЛЬ РАБОТЫ: овладение методикой решения оптимизационных задач в области технология продукции и организации общественного питания средствами MS Excel.

ЗАДАНИЕ

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

Ресурсы	Плановый фонд ресурсов	Нормативные затраты ресурсов на 100 блюд
Первые блюда	Вторые мясные	Вторые рыбные	Вторые молочные	Вторые прочие
Мясо, кг	40000	4,0	8,0	-	-	3,8
Рыба, кг.	25000	2,5	-	10	-	-
Овощи, кг	27000	3,2	2,0	3,0	-	4,6
Мука, крупа, кг.	20000	2,1	2,6	2,3	2,2	-
Молоко, л.	45000	6,5	-	-	21	-
Выручка, у. е.		1,3	2,0	1,5	0,3	1,7

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Выполним построение математической модели.

Обозначим, х2, х3, х4, х5 – количество блюд, соответствующего вида (100шт.): х1 - первые блюда; х2 – вторые мясные блюда; х3 - вторые рыбные; х4 - вторые молочные блюда; х5 - 2-е вторые прочие блюда.

Запишем целевую функцию, максимизирующую выручку:

F(X) = 1,3х1 + 2х2 + 1,5х3 + 0,3х4 + 1,7х5 ® max

Запишем ограничения:

4х1 + 8х2 + 0х3 + 0х4 + 3,8х5 £ 40000 (ограничение по ресурсу «Мясо»);

2,5х1 + 0х2 + 10х3 + 0х4 + 0х5 £ 25000 (ограничение по ресурсу «Рыба»);

3,2х1 + 2х2 + 3х3 + 0х4 + 4,6х5 £ 27000 (ограничение по ресурсу «Овощи»);

2,1х1 + 2,6х2 + 2,3х3 + 2,2х4 + 0х5 £ 20000 (ограничение по ресурсу «Мука, крупа»);

6,5х1 + 0х2 + 0х3 + 21х4 + 0х5 £ 45000 (ограничение по ресурсу «Молоко»);

х1,2,3,4,5 £ 0 (условие неотрицательности количества блюд)

В результате получаем следующую экономико-математическую модель:

F(X) = 1,3х1 + 2х2 + 1,5х3 + 0,3х4 + 1,7х5 ® max

4х1 + 8х2 + 0х3 + 0х4 + 3,8х5 £ 40000

2,5х1 + 0х2 + 10х3 + 0х4 + 0х5 £ 25000

3,2х1 + 2х2 + 3х3 + 0х4 + 4,6х5 £ 27000

2,1х1 + 2,6х2 + 2,3х3 + 2,2х4 + 0х5 £ 20000

6,5х1 + 0х2 + 0х3 + 21х4 + 0х5 £ 45000

х1,2,3,4,5 ³ 0

2.Создаем документ Microsoft Excel и вводим исходные данные задачи, как показано на рисунке 2.1.

Рисунок 2.1. – Исходные данные задачи линейного программирования

3. Вводим зависимость для целевой функции

Для этого ставим курсор в ячейку G4, затем нажимаем на кнопку «Мастер функций», которая находится на панели инструментов. Окно мастера функций показано на рисунке 2.2.Выбираем категорию «Математические», Функцию «СУММПРОИЗВ» и нажимаем OK. Окно для ввода аргументов функции показано на рисунке 2.3.

Рисунок 2.2. – Окно «Мастера функций»

В появившемся окне «Аргументы функции», в строку «Массив 1» вводим B$3:F$3, а в строку «Массив 2» вводим B4:F4 и нажимаем ОK. В ячейку G4 введена функция.

Рисунок 2.3. – Окно для ввода аргументов функции

4. Вводим зависимости для ограничений. Для этого повторяем процесс, описанный в п.3 для каждого из ограничений. В результате в ячейке G7 должна появиться формула: =СУММПРОИЗВ(B$3:F$3, B7:F7). В ячейке G8 должна появиться формула: =СУММПРОИЗВ(B$3:F$3, B8:F8), в ячейке G9 должна появиться формула: =СУММПРОИЗВ(B$3:F$3, B9:F9), в ячейке G10 должна появиться формула: =СУММПРОИЗВ(B$3:F$3, B10:F10), а в ячейке G11 должна появиться формула: =СУММПРОИЗВ(B$3:F$3, B11:F11)

Далее в строке Меню выбираем Сервисà Поиск решения. В появившемся окне «Поиск решения» назначаем целевую функцию. Для этого ставим курсор в строку «Установить целевую ячейку»à вводим адрес ячейки $G$4, равной «Максимальному значению»à курсор в строку «Изменяя ячейки»à вводим адреса искомых переменных $B$3:$F$3. Окно «Поиск решения» показано на рисунке 2.3.

Рисунок 2.3 – Окно «Поиск решения»

Нажимаем на кнопку «Добавить», появляется окно «Добавление ограничения», представленного на рисунке 2.4.

Рисунок 2.4 – Окно «Добавление ограничения»

В строке «Ссылка на ячейку» вводим адрес $G$7à вводим знак ограниченияà в строке «Ограничение» вводим адрес $I$7à нажимаем на кнопку «Добавить». Вводим остальные ограничения по этому же алгоритму. После введения последнего ограничения нажимаем кнопку OK. На экране появляется окно «Поиск решения» с введенными условиями, как показано на рисунке 2.5.

Рисунок 2.5 – Окно «Поиск решения» с введенными ограничениями

5. Вводим параметры для решения ЗЛП.

Для этого в окне «Поиск решения» нажимаем на кнопку «Параметры». Появляется окно «Параметры поиска решения». Устанавливаем в окнах «Линейная модель» (это обеспечивает применение симплекс-метода) и «Неотрицательные значения» , как показано на рисунке 2.6.

Рисунок 2.6 – Окно «Параметров поиска решения»

Далее нажимаем кнопку OK и на экране появляется окно «Поиск решения». Нажимаем кнопку «Выполнить». Появляется окно «Результаты поиска решения» и исходная таблица с заполненными ячейками B3:F3 и ячейка G4 с максимальным значением целевой функции, как показано на рисунке 2.6.

Рисунок 2.7 – Окно «Результаты поиска решения»

Нажимаем кнопку OK.

Полученное решение означает, что для максимизации выручки необходимо:

Х1 = 0; Х2 = 3763,70; Х3 = 2500; Х4 = 2029,27; Х5 = 2602,74;

Максимальная выручка составляет: 16310,83 у. е.

Ответ: Максимальная выручка составляет 16310,83 у. е.

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