В начало

Литература

Часть I. Компьютерный практикум

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

Если в меню Сервис отсутствует команда Поиск решения необходимо выполнить следующие действия:

• выбрать команду Сервис/Надстройки;
• в диалоговом окне Надстройки установить флажок Поиск решения;
• щелкнуть ОК.

После этого в меню Сервис появится новая команда Поиск решения.

1. Задача линейного программирования (ЗЛП), компьютерная реализация стандартными офисными средствами (в среде пакета Excel)

Оптимизационные (экстремальные) модели в экономике возникают при практической реализации принципа оптимальности в управлении [12].

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

В наиболее общем виде задача (модель) линейного программирования записывается следующим образом: требуется найти максимум (или минимум) линейной целевой функции

f(x₁, x₂, …, x_n) = c₁x₁ + c₂x₂ + … + c_nx_n

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

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n {≤, =, ≥} b₁

a₂₁x₂ + a₂₂x₂ + … + a_2nx_n {≤, =, ≥} b₂

…

a_m1x₁ + a_m2x₂ + … + a_mnx_n {≤, =, ≥} b_m

x_j ≥ 0, j = 1, 2, …, n,

где a_ij, b_i, c_j (i = 1, 2, ..., m, j = 1, 2, ..., n) - заданные постоянные величины.

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

Первый случай связан с некорректностями в постановке экономической задачи и (или) разработанной ЭММ. Например, имеющимся объемом ресурсов заведомо невозможно выполнить даже те минимальные объемы работ, которые закладываются в ограничения как необходимые минимальные плановые задания. Если в данной ситуации все же необходимо найти решение задачи, то следует построить непустое множество допустимых решений, исключив одно или несколько ограничений, т.е. фактически соблюсти принцип альтернативности.

Второй случай обычно означает, что ЭММ разработана некорректно, и некоторые существенные ограничения в ней отсутствуют.

1.1. Технология компьютерной реализации ЗЛП

Первым шагом при работе с командой (программой, надстройкой) Сервис/Поиск решения является создание специального (рабочего) листа, т.е. специальная запись ЭММ в терминах электронной таблицы (ЭТ) Excel [8,10,18].

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

Ограничения модели определяются с помощью значений соответствующих ячеек, которые должны находиться в определенных пределах или удовлетворять граничным условиям. Ограничения могут налагаться как на целевую, так и на переменные ячейки (по два ограничения для каждой изменяемой ячейки с указанием верхнего и нижнего пределов, а также до ста дополнительных). Таким образом, на специальном листе должны содержаться ячейки, в которых вычисляются ограничиваемые величины. Тип каждого из ограничений модели (≤, =, ≥) задается (вводится) в специальном окне диалога при выполнении команды Поиск решения. Численные значения самих ограничений включать в специализированный лист необязательно - они также вводятся в специальном окне диалога при выполнении команды Поиск решения. В режиме Параметры окна диалога Поиск решения задается тип модели (линейная или нелинейная).

После команды Выполнить диалогового окна Поиск решения осуществляется поиск оптимального решения - в итоге появляется диалоговое окно Результаты поиска решения.

В режиме Справки этого диалогового окна содержатся сведения об итоговых сообщениях процедуры поиска решения. Например, в случае несовместности системы ограничений Excel будет выдавать сообщение Поиск не может найти подходящего решения. Если же решение задачи отсутствует вследствие неограниченности целевой функции на множестве допустимых решений, то Excel будет выдавать сообщение Значения целевой ячейки не сходятся. При успешном завершении решения задачи появляется диалоговое окно Результат поиска решения. Решение найдено. С помощью рубрики Результаты этого диалогового окна можно получить отчет по результатам решения, рубрики Устойчивость и Пределы позволяют провести дополнительный экономико-математический анализ оптимального плана и получить отчеты по устойчивости и по пределам.

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

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

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

Пример 1. Задача об оптимальном использовании ограниченных ресурсов. Фабрика имеет в своем распоряжении определенное количество производственных ресурсов: трудовые, денежные средства, сырье, оборудование, производственные площади и т.п. Допустим, например, ресурсы трех видов - трудовые, сырье и оборудование имеются в количестве соответственно 80 чел./дней, 480 кг, 130 станко/часов. Фабрика может выпускать ковры четырех видов. Информация о количестве единиц каждого ресурса, необходимых для производства одного ковра каждого вида (о нормах расхода производственных ресурсов), и доходах, получаемых предприятием от реализации единицы каждого вида товаров, приведена в следующей таблице.

Таблица

Требуется составить такой план выпуска продукции, при котором будет получен максимальный доход от реализации продукции (сбыт всей выпущенной продукции обеспечен).

Экономико-математическая модель

Обозначим через X₁, X₂, X₃, X₄ объемы производства соответствующего вида продукции (количество ковров каждого типа).

Целевая функция - это математическая запись критерия оптимальности, т.е. выражение, которое необходимо максимизировать f(x) = 3X₁ + 4X₂ + 3X₃ + X₄.

Ограничения по ресурсам:

7X₁ + 2X₂ + 2X₃ + 6X₄ ≤ 80

5X₁ + 8X₂ + 4X₃ + 3X₄ ≤ 480

2X₁ + 4X₂ + X₃ + 8X₄ ≤ 130

X₁, X₂, X₃, X₄ ≥ 0

Решение. Приведем подробное описание технологии получения решения приведенной ЗЛП.

Обозначим: M1 - один щелчок левой кнопки мыши; М2 - двойной щелчок левой кнопки мыши.

Прежде чем приступить к решению задачи студенту необходимо на сервере создать папку под своим именем. Порядок работы:

• На рабочем столе найдите пиктограмму «Сетевое окружение» → М2.
• Двойным щелчком мыши открывайте пиктограмму «Для документов».
• Двойным щелчком мыши открывайте пиктограмму «Для студентов».
• В папке с фамилией ведущего преподавателя создайте папку под своей фамилией.

Далее необходимо последовательно выполнить следующую работу.

1. Создать форму для ввода условий задачи. Запустите Excel, выбрав Microsoft Excel из подменю Программы главного меню Windows. Открывается чистый лист Excel. Создайте текстовую форму - таблицу для ввода условий задачи (рис. 1.1).

Рис. 1.1

Рис. 1.2

2. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначьте через X₁, X₂, X₃, X₄ количество ковров каждого типа. В нашей задаче оптимальные значения компонент вектора X = (X₁, X₂, X₃, X₄) будут помещены в ячейках В3:Е3, оптимальное значение целевой функции — в ячейке F4.
3. Ввести исходные данные задачи в созданную форму—таблицу, представленную на рис. 1.2. Сохраните таблицу, т.к. она должна быть представлена в отчете по лабораторной работе.

Порядок сохранения таблицы следующий.

В строке Меню указатель мыши на имя Файл → M1. В развернутом меню команда Сохранить как → M1. Появляется диалоговое окно Сохранение документа. Путем перебора папок в строке Папка должна быть установлена папка с фамилией студента. Далее курсор переведите в строку Имя файла и присвойте ему имя. Далее нажать кнопку Сохранить.

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

• курсор в ячейку F4.
• курсор на кнопку «Мастер функций», расположенную на панели инструментов.
• M1. На экране появляется диалоговое окно Мастер функций шаг 1 из 2 (рис. 1.3).

Рис. 1.3

Рис. 1.4

• курсор в окно «Категория» на категорию Математические;
• M1;
• курсор в окно Функции на СУММПРОИЗВ;
• M1. На экране появляется диалоговое окно СУММПРОИЗВ (рис. 1.4);
• в строку «Массив 1» ввести В$3:Е$3;
• в строку «Массив 2» ввести В4:Е4;
• кнопка «ОК». На экране: в ячейку F4 введена функция (рис. 1.4).

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

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

• курсор в ячейку F4;
• на панели инструментов кнопка Копировать в буфер → M1;
• курсор в ячейку F7;
• на панели инструментов кнопка Вставить из буфера → M1;
• курсор в ячейку F8;
• на панели инструментов кнопка Вставить из буфера → M1;

Рис. 1.5

• курсор в ячейку F9;
• на панели инструментов кнопка Вставить из буфера → M1.

Примечание. Содержимое ячеек F7-F9 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис. 1.5 (в качестве примера представлено содержимое ячейки F7).

В строке Меню указатель мыши на имя Сервис → M1. В развернутом меню команда Поиск решения → M1. Появляется диалоговое окно Поиск решения (рис. 1.6).

Рис. 1.6

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

• курсор в строку Установить целевую ячейку;
• введите адрес ячейки $F$4;
• введите направление целевой функции в зависимости от условия вашей задачи - Максимальному значению или Минимальному значению);
• курсор в строку Изменяя ячейки;
• введите адреса искомых переменных В$3:Е$3.

7. Ввести ограничения:

• указатель мышки на кнопку Добавить → M1. Появляется диалоговое окно Добавление ограничения (рис. 1.7);
• в строке Ссылка на ячейку введите адрес $F$7;
• введите знак ограничения ≤;
• в строке Ограничение введите адрес $Н$7;
• указатель мыши на кнопку Добавить → M1. На экране вновь диалоговое окно Добавление ограничения (рис. 1.7).
• введите остальные ограничения задачи, по вышеописанному алгоритму;
• после введения последнего ограничения кнопка ОК.

Рис. 1.7

На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.8).

Рис. 1.8

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

Рис. 1.9

• установите флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения;
• указатель мыши на кнопку ОК. На экране диалоговое окно Поиск решения;
• указатель мыши на кнопку Выполнить.

Через непродолжительное время появится диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками В3:Е3 для значений X_i и ячейка F4 с максимальным значением целевой функции (рис. 1.10).

Рис. 1.10

Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске и реализации 30 ковров второго вида и 10 ковров третьего вида. При этом трудовые ресурсы и фонд рабочего времени оборудования будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.

Пример 2. Задача об оптимальном использовании ограниченных ресурсов. На участок строящейся дороги необходимо вывезти 20000 м³ каменных материалов. В районе строительства имеются три карьера с запасами 8000 м³, 9000 м³ и 10000 м³. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м³/смену в карьерах А, Б и 500 м³/смену в карьере В. Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рассматриваемого участка выделен для экскаваторов общий лимит 60 машино-смен с правом использовать его по усмотрению строителей. Транспортные затраты на перевозку материалов характеризуются следующими показателями: на перевозку 1000 м³ материалов из карьера А требуется 100 автомобиле-смен, из карьера Б - 135 автомобиле-смен, из карьера В - 170 автомобиле-смен.

Требуется составить оптимальный план перевозок, обеспечивающий минимальные транспортные затраты.

Экономико-математическая модель

Для удобства записи модели примем за единицу измерения количества материалов 10000 м³. Обозначим через х₁ объем добычи материалов в карьере А, х₂ - в карьере Б, х₃ — в карьере В. С учетом сказанного математически задача может быть записана следующим образом:

min f(x₁, x₂, x₃) = 1000x₁ + 1350х₂ + 1700х₃

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

x₁ + x₂ + x₃ = 2,0

40х₁ + 40х₂ + 20x₃ ≤ 60

0 ≤ x₁ ≤ 0,8

0 ≤ х₂ ≤ 0,9

0 ≤ х₃ ≤ 1,0.

Решение. Приведенная ЭММ является моделью задачи линейного программирования (ЗЛП). Она может быть реализована симплекс-методом. Получим решение средствами пакета Excel. Ниже на рис. 1.11 приведена одна из возможных форм специального листа (рабочей таблицы) для рассматриваемой модели.

Рис. 1.11

Рис. 1.12. Диалоговое окно Поиск решения

На рабочем листе не показаны промежуточные формулы для ячеек F5:F7, G5:G7, H5:H7, которые являются произведением изменяемых ячеек для X и соответствующих ячеек для коэффициентов ЦФ и функциональных ограничений. После команды Сервис/Поиск решения необходимо оформить диалоговое окно как это показано на рис. 1.12.

После нажатия клавиши Выполнить в диалоговом окне Поиск решения осуществляется реализация модели. Ниже в таблице приведены результаты решения задачи.

ЗАДАЧА ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ ОГРАНИЧЕННЫХ РЕСУРСОВ

То есть оптимальные значения переменных х₁ = 0,8; х₂ = 0,2; x₃ = 1,0. Таким образом, из карьера А следует вывезти 8000 м³, из карьера Б - 2000 м³, из карьера В - 10000 м³ каменных материалов. При этом транспортные затраты будут минимальны и равны 2770 автомобиле-смен.

1.3. Специальные задачи линейного программирования, примеры компьютерной реализации

Ниже приводятся примеры специальных ЗЛП - транспортной задачи и задачи о назначениях, которая интерпретируется как частный случай транспортной задачи (в разделе 2.2 задача о назначениях рассматривается как пример задачи дискретной оптимизации).

Пример. Перед менеджером нефтяной компании «Магнум» стоит задача создания схемы поставки нефтепродуктов от четырех нефтеперерабатывающих комплексов компании к пяти регионам страны. Одним из основных условий поставленной задачи является минимизация стоимости перевозок, при этом все мощности нефтеперерабатывающих комплексов должны быть реализованы и все потребности регионов должны быть удовлетворены.

Мощности поставщиков и мощности потребителей, а также стоимость перевозок нефтепродуктов представлены в следующей таблице (в условных единицах).

Экономико-математическая модель

В данном случае мощности поставщиков нефтепродуктов и потребности регионов в них совпадают, т.е. имеем дело с закрытой моделью транспортной задачи (см., например, [12]).

Решение. Ввод условий задачи состоит из следующих основных этапов.

1. Создание формы для решения задачи.
2. Ввод граничных условий.
3. Ввод исходных данных.
4. Назначение целевой функции.
5. Ввод зависимостей из математической модели.
6. Ввод ограничений.
7. Просмотр результатов и печать отчета.

Рассмотрим более подробно каждый из этих этапов.

1. Создание формы для решения задачи предполагает создание матрицы перевозок.

Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек B3:F6 вводится «1».

Таким образом, резервируется место, где после решения задачи будет находиться распределение поставок, обеспечивающее минимальные затраты на перевозку груза (нефтепродуктов).

2. Ввод граничных условий.

Введение условия реализации мощностей поставщиков, т.е.

где a_i - мощность i-го поставщика;

x_ij — объем поставки груза от i-го поставщика к j-му потребителю;

n — количество потребителей.

Для этого необходимо выполнить следующие операции:

• курсор в ячейку A3;
• щелкнуть знак «∑»;
• выделить необходимые для суммирования ячейки B3:F3;
• нажать ENTER - подтверждение ввода формулы для суммирования.

Аналогичные действия выполнить для ячеек А4, А5, А6, т.е. ввести условия реализации мощностей всех поставщиков (для всех строк). Эти действия можно реализовать иначе:

• курсор в A3;
• копировать в буфер (т.е. копировать в буфер формулу, введенную для ячейки A3);
• выделить ячейки А4:А6;
• вставить из буфера (вставка формулы для суммирования в А4:А6).

Введение условия удовлетворения запросов потребителей, т.е.

где b – мощность j-го потребителя;

m - количество поставщиков.

Для этого необходимо выполнить следующие операции:

• курсор в В7;
• щелкнуть знак «∑ ». При этом автоматически выделяется весь столбец В3:В6;
• ENTER - подтверждение суммирования показателей выделенного столбца.

Последовательность этих действий выполнить для ячеек C7-F7, или же:

• курсор в В7;
• копировать в буфер;
• выделить С7:F7;
• вставить из буфера.

Таким образом, введены ограничения для всех поставщиков и всех потребителей.

3. Ввод исходных данных.

В конкретном примере осуществляется ввод мощностей четырех нефтеперерабатывающих предприятий (ячейки А11:А14), потребности регионов в их продукции (B10:F10), а также удельные затраты по доставке нефтепродуктов от конкретного поставщика потребителю (блок B11:F14) (рис. 1.13).

Рис. 1.13. Ввод исходных данных и граничных условий

4. Назначение целевой функции.

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

где С_ij — стоимость доставки единицы груза от i-го поставщика к j-му потребителю;

x_ij — объем поставки груза от i-го поставщика к j-му потребителю.

Для этого:

• курсор в ячейку В15. В данную ячейку будет помещаться значение целевой функции после решения задачи;
• щелкнуть Мастер функций (значок f_x);
• в окне Категория выбрать Математические;
• в окне Функция при помощи спинера выбрать СУММПРОИЗВ;
• ОК;
• в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.

В задаче целевая функция представляет собой произведение удельных затрат на доставку груза (расположенных в блоке ячеек B11:F14) и объемов поставок для каждого потребителя (содержимое ячеек B3:F6). Для этого:

• в поле Массив 1 указать адреса B11:F14;

Рис. 1.14. Назначение целевой функции

• в поле Массив 2 указать адреса B3:F6;
• OK - подтверждение окончания ввода адресов массивов.

В поле ячейки В15 появится некоторое числовое значение, равное произведению единичных поставок на удельные коэффициенты затрат по доставке грузов (число 77 в данной задаче, рис. 1.14).

5. Ввод зависимостей из математической модели.

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

• щелкнуть Сервис - Поиск решения;
• курсор подвести в поле Установить целевую (ячейку);
• ввести адрес $В$15. Таким образом производится указание ячейки, куда при решении задачи помещается значение целевой функции (или же: курсор в В15, затем щелкнуть Поиск решения. При этом осуществится автоматический ввод адреса $В$15 в поле адреса целевой ячейки);
• установить направление изменения целевой функции, равное «минимальному значению»;
• ввести адреса изменяемых ячеек B3:F6. Для этого:
  • щелкнуть в поле изменяя ячейки;
  • ввести адреса $B$3:$F$6 ( или же щелкнуть на маленькой красной стрелке рядом с этим полем, выйти в таблицу с матрицей перевозок, выделить блок ячеек B3:F6, щелкнуть на красной стрелке и вернуться в блок Поиска решения, при этом нужные адреса будут введены).

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

• щелкнуть Добавить ограничения;
• в поле Ссылка на ячейку ввести адреса $А$3:$А$6;
• в среднем поле установить знак " = ". Для этого щелкнуть спикер и выбрать необходимый знак " = ".
• в поле Ограничение установить адреса $А$11:$А$14.
• щелкнуть ОК, т.е. осуществить подтверждение введенного условия. После этого Вы вернетесь в поле Поиск решения.

Далее вводится ограничение, которое реализует условие удовлетворения мощностей всех потребителей. Для этого:

• щелкнуть Добавить ограничение;
• в поле Ссылка на ячейку ввести адреса $B$7:$F$7;
• в поле знака выбрать при помощи спинера знак " = ";
• в поле Ограничение (третье поле) установить адреса $B$10:$F$10;
• ОК (рис. 1.15).

Рис. 1.15. Ввод зависимостей из математической модели

6. Ввод ограничений.

Далее необходимо установить ограничения на решение задачи. Для этого:

• щелкнуть Параметры;
• установить Линейная модель;
• установить Неотрицательные значения, так как объемы поставок груза отрицательной величиной быть не могут (рис. 1.16);
• ОК. После этого осуществится выход в поле Поиска решений;
• нажать Выполнить.

Рис. 1.16. Установление параметров задачи

7. Просмотр результатов и печать отчета.

После выполнения всех вышеуказанных действий на экран выводится окно Результаты поиска решения (рис. 1.17).

Рис. 1.17. Решение найдено

• В окне Тип отчета выбрать интересующий вид отчета.
• ОК.
• Внизу страницы экрана содержится сообщение Отчет по результатам 1. Щелкнуть на этом сообщении, на экран выводятся результаты решения задачи, которые можно распечатать.

При нажатии Лист 1 происходит возврат в программу к исходным данным.

В матрице перевозок содержатся оптимальные объемы поставок грузов от поставщика потребителям, дающие минимум затрат на доставку. Значение целевой функции содержится в ячейке В15 и для конкретной задачи равно 7800 (рис. 1.18).

Рис. 1.18. Задача решена

Из вышеизложенного можно сделать следующий вывод: минимум затрат на доставку нефтепродуктов, равный 7800 условных денежных единиц, будет обеспечен при следующем плане поставок:

• от первого поставщика первому потребителю в объеме 200 единиц и четвертому в объеме 500 единиц (условных);
• от второго поставщика второму потребителю в объеме 100 единиц и третьему потребителю в объеме 700 единиц (условных);
• от третьего поставщика пятому потребителю в объеме 900 единиц (условных);
• от четвертого поставщика первому потребителю в объеме 400 единиц и второму потребителю в объеме 300 единиц (условных).

При данной схеме поставок мощности всех поставщиков будут реализованы и спросы всех потребителей будут удовлетворены.

Рассмотрим задачу о назначениях, которая в этом случае интерпретируется и реализуется как частный случай транспортной задачи.

Пример. На коммерческом предприятии имеется m работников A₁, А₂, ..., A_i, ..., А_m, каждый из которых может выполнять одну из имеющихся m видов работ: В₁, В₂, ..., В_j, ..., В_m. Известно, что один и тот же работник может выполнять разливные виды работ с разной производительностью труда (С_ij) в зависимости от опыта работы, квалификации, индивидуальных особенностей. В связи с этим возникает проблема распределения работников по должностям таким образом, чтобы производительность труда в коллективе была максимальной.

Экономико-математическая модель.

Обозначим через x_ij назначение i-го работника на j-должность. Так как количество работников равно количеству должностей и один работник может занимать только одну должность, то x_ij может принимать только два значения: 1 (если работник назначается на данную должность) или 0 (если не назначается). Тогда суммарная производительность труда работников (целевая функция) имеет следующий вид:

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

x_ij ≥ 0, i = 1, …, m; j = 1, …, m,

Умножая целевую функцию на -1, задача распределения по должностям может быть приведена к транспортной задаче, в которой объем запасов каждого поставщика и объем потребностей каждого потребителя равны 1.

Числовой пример. Перед менеджером фирмы «Стар» стоит задача распределения четырех работников по вакантным должностям по условиям результатов контрольных испытаний. Производительность труда по отдельным видам работ, показанная каждым из работников, приведена в таблице.

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

Решение. Ввод условий задачи состоит из следующих основных этапов:

1. Создание формы для решения задачи.
2. Ввод граничных условий.
3. Ввод исходных данных.
4. Назначение целевой функции.
5. Ввод зависимостей из математической модели.
6. Ввод ограничений.
7. Просмотр результатов и печать отчета.

Рассмотрим более подробно каждый из этих этапов.

1. Создание формы для решения задачи предполагает создание матрицы назначений по должностям.

Для этого необходимо выполнить резервирование изменяемых ячеек: в блок ячеек В3:Е6 вводятся «1».

Таким образом, резервируется место, где после решения задачи будет находиться распределение рабочих по должностям, обеспечивающее максимальную производительность труда.

2. Ввод граничных условий.

Введение условия назначения работника только на одну должность, т.е.

где х_ij — назначение i-го работника на j-ую должность;

m — количество вакантных должностей.

Для этого необходимо выполнить следующие операции:

• курсор в ячейку A3;
• щелкнуть знак «∑»;
• выделить необходимые для суммирования ячейки В3:Е3;
• нажать ENTER - подтверждение ввода формулы для суммирования.

Аналогичные действия выполнить для ячеек А4, А5, А6, т.е. ввести условия реализации мощностей всех поставщиков (для всех строк). Эти действия можно реализовать иначе:

• курсор в A3;
• копировать в буфер (т.е. копировать в буфер формулу, введенную для ячейки A3);
• выделить ячейки А4:А6;
• вставить из буфера (вставка формулы для суммирования в А4:А6).

Введение условия заполнения вакантной должности, т.е.

Для этого необходимо выполнить следующие операции:

• курсор в В7;
• щелкнуть знак «∑». При этом автоматически выделяется весь столбец В3:В6;
• ENTER - подтверждение суммирования показателей выделенного столбца.

Последовательность этих действий выполнить для ячеек C7:F7, или же:

• курсор в В7;
• копировать в буфер;
• выделить С7:Е7;
• вставить из буфера.

Таким образом, введены ограничения по назначению работника только на одну должность и условию заполнения всех вакантных мест.

3. Ввод исходных данных.

В конкретном примере осуществляется ввод условной мощности работника фирмы (в ячейки А11:А14 вводится «1»), потребности в заполнении вакантной должности («1» - в В10:Е10), ввод производительности труда конкретного работника при проведении контрольных испытаний по каждой должности (блок В11:Е14) (рис. 1.19).

Рис. 1.19. Ввод исходных данных

4. Назначение целевой функции.

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

где С_ij — производительность труда i-го работника при занятии j-й должности;

x_ij - назначение i-го работника на j-должность.

Для этого:

• курсор в ячейку В16. В данную ячейку будет помещаться значение целевой функции после решения задачи;
• щелкнуть Мастер функций (значок f_x);
• в окне Категория выбрать Математические;
• в окне Функция при помощи спинера выбрать СУММПРОИЗВ;
• OK;
• в окне СУММПРОИЗВ указать адреса массивов, элементы которых обрабатываются этой функцией.

В задаче целевая функция представляет собой произведение производительности труда работников (расположенных в блоке ячеек В11:В14) и назначения работников на должности (содержимое ячеек В3:Е6). Для этого:

• в поле Массив 1 указать адреса В11:E14;
• в поле Массив 2 указать адреса В3:Е6;
• ОК - подтверждение окончания ввода адресов массивов.

В поле ячейки В16 появится некоторое числовое значение, равное произведению «1» на производительность каждого работника на конкретной должности (число 67 в данной задаче) (рис. 1.20).

Рис. 1.20. Назначение целевой функции

5. Ввод зависимостей из математической модели.

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

• щелкнуть Сервис - Поиск решения;
• курсор подвести в поле Установить целевую (ячейку);
• ввести адрес $В$16. Таким образом производится указание ячейки, куда при решении задачи помещается значение целевой функции (или же: курсор в В16, затем щелкнуть Поиск решения. При этом осуществится автоматический ввод адреса $В$16 в поле адреса целевой ячейки);
• установить направление изменения целевой функции, равное «максимальному значению»;
• ввести адреса изменяемых ячеек В3:Е6. Для этого:
  • щелкнуть в поле Изменяя ячейки;
  • ввести адреса $В$3:$Е$6 (или же щелкнуть на маленькой красной стрелке рядом с этим полем, выйти в таблицу с матрицей перевозок, выделить блок ячеек В3:Е6, щелкнуть на красной стрелке и вернуться в блок Поиск решения, при этом нужные адреса будут введены).
• Ввести ограничение задачи. В матрицу перевозок, содержащую исходные данные по задаче, необходимо ввести условие назначения работника только на одну должность. Для этого:
  • щелкнуть Добавить ограничения;
  • в поле Ссылка на ячейку ввести адреса $А$3:$А$6;
  • в среднем поле установить знак " = ". Для этого щелкнуть спинер и выбрать необходимый знак " = ";
  • в поле Ограничение установить адреса $А$11:$А$14;
  • щелкнуть ОК, т.е. осуществить подтверждение введенного условия. После этого Вы вернетесь в поле Поиск решения.

Далее вводится ограничение, которое реализует условие заполнения вакантной должности. Для этого:

• щелкнуть Добавить ограничение;
• в поле Ссылка на ячейку ввести адреса $В$7:$Е$7;
• в поле знака выбрать при помощи спинера знак " = ";
• в поле Ограничение (третье поле) установить адреса $В$10:$Е$10;
• ОК (рис. 1.21).

Рис. 1.21. Ввод зависимостей из математической модели

6. Ввод ограничений.

Далее необходимо установить ограничения на решение задачи. Для этого:

• щелкнуть Параметры;
• установить Линейная модель;
• установить Неотрицательные значения (назначение работника на должность принимает значение «1» или «0» , т.е. отрицательной величиной быть не может);
• ОК. После этого осуществится выход в поле Поиск решения;
• нажать Выполнить.

7. Просмотр результатов и печать отчета.

После выполнения всех вышеуказанных действий на экран выводится окно Результаты поиска решения.

• В окне Тип отчета выбрать интересующий вид отчета;
• ОК;
• Внизу страницы экрана содержится сообщение Отчет по результатам 1. Щелкнуть на этом сообщении, на экран выводятся результаты решения задачи, которые можно распечатать.

При нажатии Лист 1 происходит возврат в программу к исходным данным.

В Матрице назначений содержится схема распределения работников по должностям (1 - назначен, 0 - не назначен), дающая максимальную суммарную производительность труда. Значение целевой функции содержится в ячейке В16 и для конкретной задачи равно 22 (рис. 1.22).

Рис. 1.22. Задача решена

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

• первого работника на должность В₃ (содержимое ячейки D3 равно 1);
• второго работника на должность В₄ («1» в ячейке Е4);
• третьего работника на должность В₁ («1» в ячейке В5);
• четвертого работника на должность В₂ («1» в ячейке С6).

2. Модели нелинейной и дискретной оптимизации, компьютерная реализация стандартными офисными средствами (в среде пакета Excel)

Рассмотрим некоторые примеры нелинейных и дискретных типовых оптимизационных экономических задач, их экономико-математические модели и методы компьютерной реализации в среде пакета Excel.

2.1. Особенности компьютерной реализации

Задача (модель) нелинейного программирования (НЛП) формулируется так же, как и общая задача оптимального программирования со следующими требованиями к целевой функции (ЦФ) и допустимой области: ЦФ f(х₁, х₂, ..., х_n) и (или) одна из функций g_i (x₁, х₂, ..., х_n) являются нелинейными:

min(max) f(x₁, x₂, …, x_n)

У произвольной задачи НЛП некоторые или все свойства, характерные для задач ЛП, отсутствуют [12]. Вследствие этого задачи НЛП несравнимо сложнее задач ЛП, и для них не существует общего универсального метода их решения (аналогично симплексному методу).

Есть целый ряд методов решения задач НЛП, некоторые из них рассмотрены в [12]. В пакете Excel реализован [8] метод множителей Лагранжа, идея которого заключается в преобразовании задачи условной оптимизации в задачу безусловной оптимизации, решение которой производится методами поиска - градиентными методами (методы первого порядка) или методами Ньютона (методы второго порядка). Наиболее распространенными являются градиентные методы.

Следует, на наш взгляд, согласиться с Б.Курицким [8], что для практического решения задачи оптимизации суть этих методов знать не обязательно.

Однако необходимо помнить, что существующие методы дают возможность находить только локальные оптимумы (помимо случаев, когда задачи обладают соответствующими свойствами выпуклости и вогнутости [7,12]). Если же есть подозрение, что в допустимой области ЦФ может иметь несколько оптимумов, то эту область следует разбить на ряд областей и в каждой из них определить свои локальные оптимумы, а затем из всех локальных оптимумов выбрать глобальный. В таком практическом подходе задача поиска глобального оптимума сводится к решению ряда задач, в которых ищется свой (локальный) оптимум.

Следует отметить, что в подавляющем большинстве практических задач оптимизации существует только один оптимум [8].

Решение задачи НЛП (реализация модели нелинейной оптимизации) средствами Excel отличается от решения ЗЛП следующим:

• назначаются начальные значения искомых переменных так, чтобы ЦФ в начальной точке не была равна нулю,
• в диалоговом окне Поиск решения в режиме Параметры не надо вводить Линейная модель.

В Excel признаком достижения оптимума является величина относительного приращения ЦФ на каждой итерации . Оптимум считается достигнутым, если выполняется условие Δf_k ≤ Δf_зад, где Δf_зад - точность, назначаемая при решении задачи (Параметры).

Примером задачи НЛП является модель оптимального формирования портфеля ценных бумаг (модель Марковица минимального риска).

В этой модели приняты следующие обозначения [17]:

x_j, - доля капитала, потраченная на покупку ценных бумагу j-го вида (весь выделенный капитал принимается за 1);

m_j — средняя ожидаемая доходность j-й ценной бумаги, (m_j называют эффективностью j-й ценной бумаги);

ν_j - дисперсия случайной доходности j-й ценной бумаги, ( называют риском j-й ценной бумаги).

В предположении о некоррелированности ценных бумаг (их независимости) модель Марковица имеет вид:

Найти x_j, , минимизирующие риск портфеля ценных бумаг

(2.1)

при условии, что обеспечивается заданное значение эффективности портфеля m_p, т.е.

(2.2)

и условии, что весь выделенный для инвестиций капитал в целях моделирования принимается за 1, т.е.

(2.3)

(2.4)

В модели (2.1)-(2.4) нелинейной является ЦФ.

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

min(max) f(x₁, x₂, …, x_n)

x_j - целые неотрицательные

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

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

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

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

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

Пример 1. Имеется n видов работ и n исполнителей этих работ. Известны экономические оценки эффекта С_ij, , от назначения i-го исполнителя на j-й вид работ. Распределите исполнителей по видам работ так, чтобы суммарный эффект от назначений был максимальным.

Экономико-математическая модель

Введем необходимые обозначения, пусть

Тогда математически задачу о назначениях можно записать в виде:

(на каждую работу должен быть назначен исполнитель)

(все исполнители должны получить назначение)

(*)

Для реализации этой ЭММ средствами Excel ограничение (*) в рабочей таблице Excel следует записать в виде:

Этот прием используется во всех дискретных задачах с булевыми переменными.

Отметим некоторые особые случаи приведенной задачи.

1. Если по той или иной причине некоторое назначение является недопустимым, то соответствующий элемент матрицы (С_ij)_n×n принимается равным (-М), т.е. его значение заведомо меньше любого другого значения. После этого в ходе решения мы сможем избежать данного назначения автоматически.

2. Если матрица (С_ij)_n×n не является квадратной, то по аналогии открытой транспортной задачи в модели задачи о назначениях следует записать либо ограничение (число исполнителей m больше числа работ n), или (число исполнителей m меньше числа работ n).

Рассмотрим некоторые типовые задачи (модели) нелинейной и дискретной оптимизации.

2.2. Примеры задач нелинейной и дискретной оптимизации

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

Пример 2. Задача производства неделимой продукции (оптимизация производственной программы мебельного предприятия). Мебельное предприятие выпускает три вида наборов мебели, книжные полки и тумбу под телевизоры. Характеристики каждого вида продукции приведены в таблице 2.1. При условии получения максимальной прибыли объем товарной продукции должен составить не менее 459,31 тыс. руб. Ситуация со сбытом продукции сложилась следующая. Книжными полками рынок насыщен, поэтому торговые организации уменьшили объем договоров до 10 тыс. шт. Тумбы для телевизоров могут быть реализованы в объемах от 4 до 7 тыс. шт., наборы мебели 2 - от 7 до 10 тыс. шт. Спрос на наборы мебели 1 и 3 неограничен и требуется не менее 10 тыс. шт. Предприятие имеет технологическое оборудование, число единиц которого и нормы затрат времени оборудования каждой группы на изготовление единицы каждого вида продукции приведены в табл. 2.2. Предприятие работает в две смены с эффективным временем работы каждой машины в 3945 ч. (коэффициент сменности 1,9). Оптимизируйте производственную программу предприятия (составьте план выпуска продукции, максимизирующий прибыль предприятия).

Таблица 2.1

Таблица 2.2

Экономико-математическая модель.

Обозначим через X₁, Х₂, Х₃, Х₄, Х₅ объем продукции каждого типа (шт.).

Каждая машина работает в две смены с эффективным временем работы 3945 ч. Определим фонд времени работы оборудования каждого типа:

Целевая функция — математическая запись критерия оптимальности "максимум прибыли от реализации", т.е. необходимо максимизировать f() = 2,4X₁ + 4,5Х₂ + 8,9X₃ + 0,06X₄ + 0,45X₅.

Ограничение по объему товарной продукции:

7,2X₁ + 14,3X₂ +26,9X₃ + 0,243X₄ + 1,5X₅ ≥ 459,31 тыс. руб.

Ограничения по фонду времени работы оборудования:

0,068X₁ + 0,096X₂ + 0,207X₃ + 0,018X₄ + 0,042X₅ ≤ 7890

0,045X₁ + 0,080X₂ + 0,158X₃ + 0,011X₄ + 0,035X₅ ≤ 7890

0,132X₁ + 0,184X₂ + 0,428X₃ + 0,020X₄ + 0,060X₅ ≤ 3945

0,057X₁ + 0,082X₂ + 0,230X₃ + 0,010X₄ + 0,028X₅ ≤ 7890

0,063X₁ + 0,090X₂ + 0,217X₃ + 0,010X₄ + 0,033X₅ ≤ 7890

0,170X₁ + 0,280X₂ + 0,620X₃ + 0,020X₄ + 0,096X₅ ≤ 15780

Ограничения по сбыту продукции:

X₁ ≥ 10000

7000 ≤ X₂ ≤ 10000

X₃ ≥ 10000

X₄ ≤ 10000

4000 ≤ X₄ ≤ 7000

X₁, X₂, X₃, X₄, X₅ ≥ 0

X₁, X₂, X₃, X₄, X₅ целые.

Решение. Подготовим рабочий лист Excel (рис. 2.1).

Основные этапы получения оптимального решения отражены на рис. 2.2-2.4.

Рис. 2.1. Рабочий лист с введенными данными

Рис. 2.2. Введение ограничений целочисленности переменных

Рис. 2.3. Введены все условия для решения задачи

Рис. 2.4. Решение найдено. Все ограничения и условия оптимальности выполнены

Таблица 2.3.

РЕЗУЛЬТАТЫ ПОИСКА ПРЕДСТАВЛЕНЫ РЕЗУЛЬТАТЫ ПОИСКА ОПТИМАЛЬНОГО РЕШЕНИЯ ЗАДАЧИ

Выводы. Для получения максимальной прибыли необходимо произвести: наборов мебели 1 вида 10002 шт., наборов мебели 2 вида 10000 шт., наборов мебели 3 вида 10490 шт., тумбы под телевизор 4000 шт. Книжные полки в этом месяце не следует производить.

Задача о ранце. В терминах задачи о ранце (рюкзаке) формулируются многие задачи загрузки в некоторую емкость тех или иных предметов.

Пример 3. Организация арендует баржу грузоподъемностью 83 т, на которой предполагает перевозить груз, состоящий из предметов четырех типов. Веса и стоимости предметов равны соответственно 24 т, 22 т, 16 т, 10 т и 96 у.е., 85 у.е., 50 у.е., 20 у.е. Требуется погрузить на баржу груз максимальной стоимости.

Экономико-математическая модель

Введем необходимые обозначения: пусть х_j (j = 1,2,3,4) — число предметов j-го типа, которое следует погрузить на баржу. Тогда ЭММ задачи о подборе для баржи допустимого груза максимальной ценности запишется следующим образом:

max f(x₁, х₂, х₃, х₄) = 96х₁ + 85х₂ + 50х₃ + 20х₄,

24x₁ + 22х₂ + 16х₃ + 10х₄ ≤ 83,

х_j (j = 1,2,3,4) - целые неотрицательные.

Решение. Приведенная ЭММ является моделью задачи целочисленного линейного программирования (ЦЛП). Для реализации этой модели средствами Excel в диалоговом окне режима Поиск решения с помощью кнопки Добавить следует ввести ограничение целочисленности переменных (целые числа в изменяемых ячейках). Специализированный (рабочий) лист может быть подготовлен в виде, представленном на рис. 2.5. Формулы этого листа очевидны. Диалоговое окно, отвечающее приведенному выше рабочему листу, представлено на рис. 2.5.

Результаты реализации разработанной ЭММ приведены ниже в таблице

Таблица 2.4

РЕЗУЛЬТАТЫ РЕШЕНИЯ ЗАДАЧИ О РАНЦЕ

Рис. 2.5. Начальная рабочая таблица и диалоговое окно

Таким образом, рекомендуемое управленческое решение с позиций принятого критерия оптимальности — следует погрузить три предмета первого типа и один предмет четвертого типа. В этом случае стоимость груза составит 308 у.е., и одна тонна грузоподъемности будет не использована (ее можно использовать на другие цели).

Пример 4. Задача о рациональном раскрое строительных материалов. Часть заемных оборотных средств предприятия иммобилизована в запасы пиломатериалов: на складе имеется партия бруса, содержащая 300 штук длиной 7,5 м каждый и партия бруса, содержащая 500 штук длиной 5 м каждый. Из этого материала можно изготовить оконные блоки, в каждый из которых входит две детали по 2,5 м и три детали длиной 2 м каждая. Как оптимально использовать заемные средства, если предположить, что спрос на оконные рамы неограничен?

Экономико-математическая модель

Оконный блок - некоторый комплект продукции или ассортиментный набор (2, 3). Понятно, что в этой задаче о раскрое критерий оптимальности - «максимум выпуска (реализации) комплектной продукции».

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

Введем необходимые обозначения: x_ij - число брусьев из i-й партии (i = 1, 2), которое следует раскроить j-м способом.

Рассмотрим соотношения:

и

Обозначим через Z - минимальное из этих соотношений (это и будет количество комплектной, ассортиментной продукции). С учетом этого ЭММ имеет вид - max Z при ограничениях:

x₁₁ + х₁₂ + х₁₃ + х₁₄ = 300,

х₂₁ + х₂₂ + х₂₃ = 500,

x_ij, Z - целые неотрицательные.

Решение. Приведенная ЭММ является моделью задачи целочисленного линейного программирования (ЦЛП). Для удобства записи сделаем замену двухиндексных переменных х_ij, и Z на одноиндексные переменные у_j так как это показано в таблице раскроя (Z = y₈). С учетом этих обозначений ЭММ задачи для записи ее в рабочей таблице ППП Excel будет иметь вид:

max (0y₁ + 0y₂ + 0y₃ + 0y₄ + 0y₅ + 0y₆ + 0y₇ + 1y₈)

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

1y₁ + 1y₂ + 1y₃ + 1y₄ + 0y₅ + 0y₆ + 0y₇ + 0y₈ = 300

0y₁ + 0y₂ + 0y₃ + 0y₄ + 1y₅ + 1y₆ + 1y₇ + 1y₈ = 500

3y₁ + 2y₂ + 1y₃ + 0y₄ + 2y₅ + 1y₆ + 0y₇ - 2y₈ ≥ 0

0y₁ + 1y₂ + 2y₃ + 3y₄ + 0y₅ + 1y₆ + 2y₇ - 3y₈ ≥ 0

y_j, j = 1, 8 — целые неотрицательные.

Основные этапы компьютерной реализации этой модели представлены на рис. 2.6.

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

РЕЗУЛЬТАТЫ РЕШЕНИЯ

Рис. 2.6. Основные этапы решения задачи о раскрое материалов средствами Excel

Ниже в таблице приведены указания на ячейки-формулы.

ФОРМУЛЫ РАБОЧЕЙ ТАБЛИЦЫ

Таким образом, реализуя приведенную модель средствами ППП Excel (см. рис. 2.6), получим решение:

y₄ = x₁₄ = 300; y₅ = x₂₁ = 380; у₇ = х₂₃ =120; у₈ = Z= 380

(оптимальные значения остальных переменных равны нулю).

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

• раскроить каждый из 300 брусьев длиной 7,5 м на 3 детали по 2 м;
• раскроить каждый из 380 брусьев длиной 5,0 м на 2 детали по 2,5 м;
• раскроить каждый из 120 брусьев длиной 5,0 м на 2 детали по 2,0 м.

В этом случае мы получим максимальную выручку для целей погашения кредита (займа).

Пример 5. Задача оптимального формирования портфеля ценных бумаг [17]. Необходимо сформировать оптимальный портфель Марковица (минимального риска) трех ценных бумаг с эффективностями и рисками: (4, 10), (10, 40), (40, 80). Нижняя граница доходности портфеля задана равной 15.

Экономико-математическая модель

Введем необходимые обозначения, пусть х_j (j = 1, 2, 3) - число предметов j-го типа, которое следует погрузить на баржу. Тогда математическая модель задачи о подборе для баржи допустимого груза максимальной ценности запишется следующим образом (см. пункт 2.1, 2,1):

4x₁ + 10x₂ + 40х₃ ≥ 15

x₁ + x₂ + x₃ = 1

x_j ≥ 0, j = 1, 2, 3.

Решение. Приведенная ЭММ является моделью задачи нелинейного программирования. Специальный (рабочий) лист может быть подготовлен в виде, представленном на рис. 2.7, формулы этого листа приведены в ячейках.

Рис. 2.7. Рабочий лист

Диалоговое окно, отвечающее приведенному выше рабочему листу, представлено на рис. 2.8.

Рис. 2.8. Диалоговое окно

Реализуя приведенную модель средствами ППП Excel (рис. 2.9), будем иметь оптимальный портфель Марковица:

x₁ = 0,5213, х₂ = 0,2078, х₃ = 0,2709,

т.е. доли ценных бумаг оказались равными 52,13 %; 20,78 % и 27,09 %. При этом минимальный риск - 23,79, доходность портфеля оказалась равной заданной - 15.

Рис. 2.9. Результаты решения

При решении приведенных выше типовых задач сознательно использовались разнообразные подходы к оформлению рабочей таблицы Excel и результатов решения. В каждой конкретной ситуации студенты вольны выбрать свой подход — с позиций содержательности, наглядности, удобства, дизайна. Результаты могут быть дополнительно представлены Отчетом по результатам или его фрагментом, кроме того, достаточно часто их целесообразно сопровождать графической иллюстрацией с помощью Мастера диаграмм (как это сделано в примере 5).

3. Задачи для самостоятельной работы и самопроверки

Составьте модель и получите решение следующих задач о смесях.

3.1. Постановка задачи. Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем — не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и их октановом числе, а также о содержании серы приведены в таблице.

Определите, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Ответ: оптимальное решение (поведение) в данной ситуации определяется вектором объемов смешиваемых компонент (571,429 т; 0; 142,857 т; 285,714 т), оценка затрат - 57142,86 ден.ед.

3.2. Получите решение задачи о смесях (3.1), если себестоимость смешиваемых компонент составит соответственно 40, 45, 60 и 70 ден.ед./т. Все остальные характеристики и числовые данные неизменны.

Ответ: оптимальное решение (поведение) в данной ситуации определяется вектором объемов смешиваемых компонент (550 т; 50 т; 100 т; 300 т), оценка затрат - 51250,0 ден.ед.

3.3. Получите решение задачи о смесях (3.1), если себестоимость смешиваемых компонент составит соответственно 40, 35, 60 и 90 ден.ед./т. Все остальные характеристики и числовые данные неизменны.

Ответ: оптимальное решение (поведение) в данной ситуации определяется вектором объемов смешиваемых компонент (0; 600 т; 100 т; 300 т), оценка затрат - 54000,0 ден.ед.

3.4. Получите решение задачи о смесях (3.1), если себестоимость смешиваемых компонент составит соответственно 40, 35, 60 и 55 ден.ед./т. Все остальные характеристики и числовые данные неизменны.

Ответ: оптимальное решение (поведение) в данной ситуации определяется вектором объемов смешиваемых компонент (0; 600 т; 100 т; 300 т), оценка затрат - 43500,0 ден.ед.

3.5. Получите решение задачи о смесях (3.1), если себестоимость смешиваемых компонент составит соответственно 40, 35, 50 и 90 ден.ед./т. Все остальные характеристики и числовые данные неизменны.

Ответ: оптимальное решение (поведение) в данной ситуации определяется вектором объемов смешиваемых компонент (0; 333,333 т; 500 т; 166,667 т), оценка затрат - 51666,67 ден.ед.

Составьте модель и получите решение следующих задач о ранце.

3.6-3.10. Постановка задачи. Организация арендует баржу грузоподъемностью В. На этой барже предполагается перевозить груз n типов. Вес и стоимость единицы груза соответственно равны p₁, р₂, ..., р_n и c₁, с₂, ..., с_n. Необходимо погрузить на баржу груз максимальной стоимости.

Числовые данные для задач 3.6-3.10 представлены в таблице (в усл. ед. измер.):

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

Задача 3.6. Оптимальное решение — 2, 2, 0, 0, 2, максимальная стоимость груза - 174 у.е.

Задача 3.7. Оптимальное решение - 1, 12, 0, 0, максимальная стоимость груза - 1060 у.е.

Задача 3.8. Оптимальное решение - 0, 0, 3, 0, 7, максимальная стоимость груза - 330 у.е.

Задача 3.9. Оптимальное решение - 0, 7, 0, 1, максимальная стоимость груза - 449 у.е.

Задача 3.10. Оптимальное решение - 0, 0, 1, 12, максимальная стоимость груза - 1388 у.е.

Составьте модель и получите решение следующих задач об инвестициях.

3.11-3.15. Постановка задачи. Предлагается n инвестиционных проектов, тщательная экономическая экспертиза которых позволяет получить для каждого из проектов достаточно убедительные экономические оценки ожидаемого эффекта от их реализации c₁, с₂, ..., с_n и необходимых капиталовложений p₁, р₂, ..., р_n. Общий объем возможных инвестиций ограничен величиной В. Необходимо так распорядиться имеющимися финансовыми ресурсами, чтобы максимизировать суммарный эффект от инвестиций.

Числовые данные для задач 3.11—3.15 представлены в таблице (в усл.ед. измер.):

Ответ: оптимальное решение определяется вектором, компоненты которого задаются булевыми переменными: 1 или 0 (1-соответствующий проект следует финансировать, 0 — не следует).

Задача 3.11. Оптимальное решение - 0, 1, 1, 1, 1, максимальный эффект - 210 у. е.

Задача 3.12. Оптимальное решение - 1, 1, 0, 1, 1, максимальный эффект - 215 у.е.

Задача 3.13. Оптимальное решение - 1, 1, 1, 0, 1, максимальный эффект - 280 у.е.

Задача 3.14. Оптимальное решение - 1, 1, 0, 0, 1, максимальный эффект - 175 у.е.

Задача 3.15. Оптимальное решение — 1, 0, 1, 0, 1, максимальная эффект - 175 у.е.

Составьте модель и получите решение следующих задач об оптимальном распределении выпуска продукции по технологиям производства.

3.16-3.20. Постановка задачи. Предприятие располагает двумя способами производства данного вида продукции. В течение рассматриваемого периода времени необходимый объем продукции равен В = Х₁ + Х₂, где Х₁ и Х₂ — объемы производства по соответствующему технологическому способу. Затраты производства S при каждом способе зависят от объемов нелинейно:

Необходимо так распределить объем производства между технологическими способами, чтобы минимизировать общие затраты производства.

Числовые данные для задач 3.16-3.20 представлены в таблице (в условных ед. измерения):

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

Задача 3.16. Оптимальное решение - 66,5; 33,5, минимальные затраты производства составят 6841,25 у.е.

Задача 3.17. Оптимальное решение - 39,9; 60,1, минимальные затраты производства составят 12147,95 у.е.

Задача 3.18. Оптимальное решение - 49,75; 50,25, минимальные затраты производства составят 5157,875 у.е.

Задача 3.19. Оптимальное решение - 50,0; 50,0, минимальные затраты производства составят 5102,0 у.е.

Задача 3.20. Оптимальное решение - 50,25; 49,75, минимальные затраты производства составят 5181,875 у.е.

Составьте модель и получите решение следующих задач о назначениях [16].

3.21. Постановка задачи. В распоряжении некоторой компании имеется 6 торговых точек и 6 продавцов. Из прошлого опыта известно, что эффективность работы продавцов в различных торговых точках неодинакова. Коммерческий директор компании произвел оценку деятельности каждого продавца в каждой торговой точке. Результаты этой оценки представлены в таблице.

Как коммерческий директор должен осуществить назначение продавцов по торговым точкам, чтобы достичь максимального объема продаж?

Ответ: Оптимальное решение определяется матрицей назначений Х = (x_ij), результаты решения содержатся в следующей таблице

3.22. Решите задачу 3.21 при условии, что назначение х₁₄ недопустимо, т.е. вместо элемента 83 в матрице объемов продаж можно принять, например, число (-100).

Ответ: Оптимальное решение определяется матрицей назначений Х = (x_ij), результаты решения содержатся в следующей таблице

3.23. Решите задачу 3.21 при условии, что имеется только 5 продавцов, т.е. шестая строка в матрице объемов продаж отсутствует.

Ответ: оптимальное решение определяется матрицей назначений Х = (x_ij), результаты решения содержатся в следующей таблице