Фонд оценочных средств по направлению подготовки (специальности)38.03.01 Экономика направленность (профиль/специализация) «Общий » (стр. 12 )

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

·  установить курсор в ячейку F4.

·  кликнуть по кнопке Мастер функций, расположенной на панели инструментов.

·  на экране появляется диалоговое окно Мастер функций – шаг 1 из 2.

·  выбрать категорию Математические;

·  выбрать функцию СУММПРОИЗВ

·  на экране появляется диалоговое окно СУММПРОИЗВ;

·  в строку Массив 1 введем В$3:Е$3;

·  в строку Массив 2 введем В4:Е4;

·  кликнуть по кнопке ОК. На экране в ячейку F4 введена функция.

5. Ввести зависимости для ограничений:

·  курсор в ячейку F4; кнопка Копировать;

·  курсор в ячейку F7; кнопка Вставить;

·  курсор в ячейку F8; кнопка Вставить;

·  курсор в ячейку F9; кнопка Вставить.

В строке Меню установить указатель мыши на имя Сервис. В развернутом меню выбрать команду Поиск решения.

6. Назначим целевую функцию (установим целевую ячейку):

·  курсор в строку Установить целевую ячейку;

·  введем адрес ячейки $F$4;

·  введем направление целевой функции в зависимости от условия задачи – Максимальному значению;

·  курсор в строку Изменяя ячейки;

·  введем адреса искомых переменных В$3:E$3.

7. Введем ограничения:

·  кнопка Добавить. Появляется диалоговое окно Добавление ограничения;

·  в строке Ссылка на ячейку введем адрес $F$7: $F$9 (или укажем на листе, т. е. щелкнуть на маленькой красной стрелке рядом с этим полем, выйти в таблицу, выделить ячейки F7:F9, нажать клавишу F4, при этом ссылка станет абсолютной $F$7: $F$9, щелкнуть на красной стрелке и вернуться в блок Поиска решения, при этом нужный адрес будет введен);

·  выберем знак ограничения <=;

·  в строке Ограничения введем адрес $Н$7: $Н$9;

·  после введения ограничения кнопка ОК.

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

·  в диалоговом окне Поиск решения кнопка Параметры.

·  на экране диалоговое окно Параметры поиска решения

·  установим флажки:

ü  Линейная модель (это обеспечит применение симплекс-метода)

ü  Неотрицательные значения;

·  кнопка ОК. На экране диалоговое окно Поиск решения;

·  кнопку Выполнить.

·  в диалоговом окно Результаты поиска решения

·  выбрать Сохранить найденное решение

·  кнопка OK

На экране представлена исходная таблица с заполненными ячейками ВЗ:ЕЗ для значений X и ячейка F4 с максимальным значением целевой функции. Введем экономическую интерпретацию полученных результатов: «Максимальный доход 1320 денежных единиц предприятие может получить при объемах выпуска продукции первого вида – 10 единиц, третьего вида – 6 единиц. Продукцию второго и четвертого вида выпускать не выгодно.»

Задача целочисленного линейного программирования

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

min (max) f(x1 ,x2 ,…,xn);

gj (x1 ,x2 ,…,xn) {≤¸=¸≥} xj ≥0, j= 1, m

xj — целые неотрицательные < п'> .

Если множество индексов <п'> = <п > – {1, 2, ... , п} , то задачу называют полностью целочисленной, если <n'> <n>,то частично целочисленной.

Примеры задачи целочисленного линейного программирования

Задача. Решить задачу Z = 3x1 + x2 ® max при ограничениях:

х1, х2 – целые числа.

Решение. За нижнюю границу линейной функции примем, например, ее значение в точке (0,0), т. е. Z0= Z(0; 0) = 0.

I этап. Решая задачу симплексным методом, получим Zmax=13 при = (4,5; 0; 0; 1,5; 0,5; 4); так как первая компонента дробная, то из области решения исключается полоса, содержащая дробное оптимальное значение , т. е. 4<x1<5. Поэтому задача 1 разбивается на две задачи 2 и 3:

Задача 2	Задача 3
Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.	Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.

Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0=0.

II этап. Решаем (по выбору) одну из задач списка, например задачу 3 симплексным методом.

Получим, что условия задачи 3 противоречивы.

III этап. Решаем задачу 2 симплексным методом. Получим при . Хотя , по-прежнему сохраняется Z0=0, ибо план Х3 нецелочисленный. Так как - дробное число, из области решений исключаем полосу 0<x2<1 и задачу 2 разбиваем на две задачи 4 и 5.

Задача 4	Задача 5
Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.	Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.

Список задач: 4 и 5. Значение Z0=0.

IV этап. Решаем задачу 4 симплексным методом. Получим Zmax = 12 при = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняем Z0; Z0= Z()=12, ибо план целочисленный.

V этап. Решаем задачу 5 симплексным методом. Получим Zmax = 12,25 при =(3,75; 1; 0; 0,25; 0,25; 0; 3). Z0 не меняется, т. е. Z0=12, ибо план нецелочисленный. Так как - дробное, из области решений исключаем полосу 3<x1<4 и задача 5 разбивается на две задачи: 6 и 7.

Задача 6	Задача 7
Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.	Z = 3x1 + x2 ® max при ограничениях: х1, х2 – целые числа.

Список задач: 6 и 7. Значение Z0=12.

VI этап. Решаем одну из задач списка, например задачу 7, симплексным методом.

Получим, что условия задачи 7 противоречивы.

VII этап. Решаем задачу 6 симплексным методом. Получим Zmax = 10,5 при =(3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как Z()=10,5 < Z0=12, то задача исключается из списка.

Итак, список задач исчерпан и оптимальным целочисленным решением исходной задачи будет Х* = = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax =12.

Существуют различные методы решения задач дискретного программирования (дискретной оптимизации). Наиболее часто используемым методом является метод ветвей и границ. Именно этот метод реализован в программе Поиск решения пакета Ехсеl.

Дискретная оптимизация средствами Ехсеl проводится аналогично решению соответствующих непрерывных задач. Основное отличие заключается во вводе при оформлении диалогового окна Поиск решения требования целочисленности соответствующих переменных (при этом в режиме Параметры устанавливается тип задачи - линейная или нелинейная).

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

Достаточно часто при моделировании экономических процессов используется особый случай дискретности задачи - булевость переменных, т. е. переменные могут принимать значения 0 или 1. Характерным примером этого случая является задача о назначениях (приводится в качестве примера задачи дискретной оптимизации и для иллюстрации механизма учета в Excel булевости переменных).