Имеется два вида корма i и ii содержащие питательные вещества

1. Имеется два вида корма I и II, содержащие питательные вещества (витамины) S1 S2 и S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице

Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.

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

Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум и почему?

Решение:

1. Построим ЭММ задачи. Введем необходимые обозначения.

Пусть:

х1 – количество корма первого вида подлежащего включению в дневной рацион (кг)

х2 – количество корма второго вида подлежащего включению в дневной рацион (кг)

Таким образом дневной рацион представляет собой вектор Х (х1;х2).

В данной задаче критерий оптимальности – минимум затрат на дневной рацион.

С учетом введенных обозначений ЭММ задачи имеет вид:

min f (х1,; х 2, ) = 4х1 + 6х2

3х1 + х2 ? 9 – ограничение по содержанию питательного вещества S1

х1 + 2х2 ? 8 – ограничение по содержанию питательного вещества S2

х1 + 6х2 ? 12 – ограничение по содержанию питательного вещества S3

х1 ? 0; х2 ? 0 – прямые ограничения

• 2. Приведенная задача линейного программирования (ЗЛП) – задача с двумя переменными, а значит мы ее можем решить графическим методом.
• 2.1. Построим область определения этой задачи (ОДР). Прямые ограничения задачи говорят о том, что ОДР будет находится в I четверти прямоугольной системы координат.

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

I 3х1 + х2 = 9, проходящей через точки (3;0) и (0;9)

II х1 + 2х2 = 8, проходящей через точки (8;0) и (0;4)

III х1 + 6х2 = 12, проходящей через точки (12;0) и (0;2)

Пересечение указанных выше полуплоскостей в первой четверти системы координат представляет собой область с вершинами АВСD – заштрихованную область на рисунке.

• 2.2. Для определения направления движения к оптимуму построим вектор-градиент, координаты которого являются частными производными целевой функции. Соединим его вершину с началом координат О (0; 0). При минимизации целевой функции необходимо двигаться в противоположном направлении вектора-градиента.
• 2.3. Построим некоторую линию уровня: 4х1 + 6х2 = а.

Положим, например, а=0. Линии уровня 4х1 + 6х2 = 0 отвечает прямая ОХ (всегда перпендикулярная вектору градиенту).

• 2.4. При минимизации целевой функции (ЦФ) необходимо перемещать линию уровня ОХ в противоположном направлении вектора-градиента. Предельной точкой при таком движении является точка В и точка О. Для определения координат точки В необходимо решить систему уравнений:
• 3х1 + х2 = 9

х1 + 2х2 = 8

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

х1 = 2, х2 = 3

Соответственно минимальное значение ЦФ равно:

min f (х1; х2) = 4*2 + 6*3 = 26

Вывод: В дневной рацион должно входить 2 кг корма I вида и 3 кг корма II вида. С таким дневным рационом связаны затраты в 26 ден. ед.

Задача на максимум не разрешима, т.к. не существует конечного максимума на неограниченном множестве допустимых решений (вследствие неограниченности целевой функции на ОДР).

Задача 1.

Имеется два вида корма I и II, содержащие
питательные вещества (витамины)
,
и
. Содержание числа единиц питательных
веществ в 1 кг каждого вида корма и необходимый
минимум веществ приведены в таблице.

Стоимость 1 кг корма I и II соответственно
равна 4 и 6 ед.

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

Построить экономико-математическую
модель задачи, дать необходимые комментарии
к ее элементам и получить решение графическим
методом. Что произойдет, если решать задачу
на максимум, и почему?

Решение:

1. Пусть
   – количество корма 1-го вида, а
   – количество корма 2-го вида, которые необходимо включить в рацион, обеспечив при этом минимальную его стоимость.

Поскольку стоимость корма I и II соответственно
составляет – 4  и 6  ед., то стоимость
всего рациона можно записать следующим
образом:

Тогда количество питательного вещества
в кормах I и II составят
.

Поскольку необходимые минимум вещества
это 9, то ограничение по питательным
веществам первого вида можно записать
следующим образом:

Аналогично рассуждая относительно питательных
веществ
и
, получим еще два ограничения:

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

Найти минимум целевой функции
,

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

2. Строим множество допустимых решений.
   Для этого строим прямые
   ,
   и
   :

3. Штриховкой выделяем область, соответствующую
   знакам неравенств. На пересечении всех
   полуплоскостей получаем ограниченную
   область.

Изображаем линию уровня целевой функции:

И вектор градиента, перпендикулярный
линии уровня –
.

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

Видно, что выход из области (минимум
целевой функции) произойдет в точке пересечения
прямых
и
– точка А.

5. Найдем координаты точки А – точка пересечения прямой
   и
   . Для этого решим систему уравнений:

6. Найдем минимум целевой функции, для этого подставим найденную точку в целевую функцию:

Стоимость рациона будет минимальной
и составит 24 ед., если включить в рацион
2 ед. корма I и 3 ед. корма II.

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

Ответ: Стоимость рациона будет минимальной 
и составит 24 ед., если включить в рацион 2 ед. корма I и
3 ед. корма II.

.

Задача 2.

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

Требуется:

1. Сформулировать прямую оптимизационную
   задачу на максимум выручки от реализации
   готовой продукции, получить оптимальный 
   план выпуска продукции.
2. Сформулировать двойственную задачу
   и найти её оптимальный план с помощью
   теорем двойственности.
3. Пояснить нулевые значения переменных
   в оптимальном плане.
4. На основе свойств двойственных оценок и теорем двойственности:

–  проанализировать использование 
ресурсов в оптимальном плане 
исходной задачи;

– определить, как изменятся выручка
от реализации продукции и план ее выпуска,
если запас сырья I вида увеличить  на
5 ед., а II – уменьшить на 5 ед.;

–  оценить целесообразность включения
в план изделия четвертого вида ценой
7  у.е., если нормы затрат сырья 2, 4 и
3 единицы.

Решение:

1. Составим ЭММ задачи.

Обозначим количество выпускаемых
изделий А, Б, В соответственно как х1, х2, х3.  Имея ограничения
по запасам сырья и зная нормы расхода
ресурсов на изготовление изделий, а также
цены готовых изделий и задачу максимизации
прибыли – мы можем сформулировать математическую
модель задачи линейного программирования.

Решаем задачу линейного программирования
на ЭВМ с помощью табличного процессора
MS Excel.

Для этого заполним в Exel следующую таблицу:

Далее введем формулы для нахождения
значении целевой функции:

=СУММПРОИЗВ(B7:D7;B6:D6)

И для ограничений:

=СУММПРОИЗВ(B3:D3;$B$7:$D$7)

=СУММПРОИЗВ(B4:D4;$B$7:$D$7)

=СУММПРОИЗВ(B5:D5;$B$7:$D$7)

И воспользовавшись надстройкой «Поиск
решения» получим значения переменных
оптимального плана выпуска изделий: Х*=(0;
100; 230). Целевая функция имеет максимальное
для данных условий задачи значение f(X*)=1350

Следовательно, для получения максимальной
выручки от реализации готовой продукции
следует производить 100 изделий Б, 230 изделий
В и не производить изделия А (x1*=0). Выпуск
изделия А  невыгоден при данных условиях
задачи.

Произведем решение задачи симплекс-методом,
для этого преобразуем ограничения в равенства:

Заполним симплекс-таблицу:

На первом шаге имеем следующее
опорное решение:

Значение целевой функции:
.

Поскольку на данном шаге в
строке
имеются отрицательные оценки, (решаем
задачу на максимум) то решение не является
оптимальным,  выбираем минимальное
значение, оно соответствует переменной
, следовательно ее будем вводить в
базис. Определяем переменную вместо которой
будем вводить
. Для этого в столбце
находим отношения
(отношение находим только для неотрицательных
значений третьего столбца) и выбираем
из них минимальное, минимальное значение
соответствует переменной
. Таким образом выводим из базиса
переменную
. Переходим к новому опорному плану
с помощью элементарных преобразований
– ШАГ 2.

На данном шаге имеем следующее
опорное решение:

Значение целевой функции:
.

Аналогично определяем, что
данный опорный план не является оптимальным,
поскольку в строке оценок
есть отрицательное значение 
-2. Определяем какая из переменных вводится
в базис, а какая выводится, в данном случае
вводим
вместо
. Переходим к новому опорному плану
с помощью элементарных преобразований
– ШАГ 3.

На данном шаге имеем следующее
опорное решение:

Значение целевой функции:
.

Данное опорное решение является
оптимальным, поскольку в строке оценок
все значения не отрицательные.

Таким образом, убирая дополнительные
переменные, получаем

 и 
– решение соответствует решению полученному
c помощью Exel.

2. Составим двойственную задачу. Обозначим двойственные оценки
   ресурсов I, II, III соответственно как y1, y2, y3. Целевой функцией двойственной задачи является общая стоимость используемых ресурсов в двойственных оценках, которая должна быть наименьшей. Число ограничений двойственной задачи соответствует числу переменных исходной задачи и
   равно 3. Математическая модель двойственной
   задачи имеет вид:

Z(Y) = 430y1+460y2+420y3→ min;

Используя теоремы двойственности получим
решение двойственной задачи.

Подставим полученное решение исходной
задачи в ограничения исходной задачи:

Т.к. последнее ограничение выполняется
как строгое неравенство, то

Согласно второй теореме двойственности

(1у1* +3 у2* + 1у3* -3) ∙ х1* = 0;

(2у1* + 0у2* + 4у3* -2) ∙ х2* = 0;

(1у1* + 2у2* + 0у3* -5) ∙ х3* = 0;

х1* = 0, х2*  = 100, х3*  = 230 (из
решения исходной задачи)

Следовательно

2у1* + 0у2* + 4у3* -2=0

1у1* + 2у2* + 0у3* -5=0

Так как y3*  = 0, то

2у1*  -2=0

Имеются два вида корма I и II, содержащие питательные вещества (витамины) S1, S2, S3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма необходимый минимум питательных веществ приведены в таблице 7.2 (цифры условные).

Таблица 7.2

Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб.

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

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

Обозначим x1, x2 – количество кормов I и II, входящих в дневной рацион. Тогда этот рацион будет включать (3* x1+1* x2) единиц питательного вещества S1, (1* x1+2* x2) единиц веществ S2, (1* x1+6* x2) единиц питательного вещества S3. Так как содержание питательных веществ S1, S2, S3 в рационе должно быть не менее, соответственно 9, 8 и 12 единиц, то получим систему неравенств:

,                                                  (1)

Переменные неотрицательные x1 ³ 0, x2 ³ 0.

Общая стоимость рациона F составит:

.                                         (2)

Обозначим xj (j=1,2,…, n) – число единиц корма n- го вида; bi (i=1,2,…, m) – необходимый минимум содержания в рационе питательного вещества Si; aij – число единиц питательного вещества Sij в единице корма j-го вида; cj– стоимость единицы корма j-го вида. Математическая модель задачи составления рациона в общей постановке примет вид. Найти такой рацион X=(x1, x2,…,xj,…,xn), удовлетворяющий системе:

и условию

,

при котором функция

принимает минимальное значение.

Пример 3. Задача оптимизации транспортных затрат. Имеются три поставщика и четыре потребителя. Мощность поставщиков и спрос потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик – потребитель» сведены в таблицу поставок (таблица 7.3).

Таблица 7.3

В левом верхнем углу произвольной (i,j) клетки стоит коэффициент затрат – затраты на перевозку единицы груза от i –го поставщика к j-му потребителю. Задача формулируется следующим образом: найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы, спросы всех потребителей были удовлетворены, суммарные затраты на перевозку были бы минимальны. Обозначим через xijобъем перевозки от i –го поставщика к j-му потребителю. Заданные мощности поставщиков и спросы потребителей накладывают ограничения на значения неизвестных xij. Чтобы мощность каждого из поставщиков была реализована, необходимо составить уравнения баланса для каждой строки таблицы поставок:

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

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

xij ≥0.

Суммарные затраты F на перевозку выражаются через коэффициенты затрат следующим образом:

Для математической постановки транспортной задачи в общей постановке обозначим через сij коэффициенты затрат, через Mi – мощности поставщиков, через Nj – мощности потребителей, (i=1,2,…,m)., (j=1,2,…,n), m – число поставщиков, n – число потребителей. Тогда система ограничений примет вид:

                                             (7)

Система (7) включает в себя уравнения баланса по строкам и по столбцам.

При этом суммарная мощность поставщиков равна суммарной мощности потребителей, т.е.

Целевая функция в данном случае следующая:

                             (8)

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

Реализация задач планирования экономических процессов средствами пакета Microsoft Excel

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

Для формирования ограничений задачи в ячейку Е5 вводим функцию: СУММПРОИЗВ ($C$10:$D$10;C5:D5).

Вызов функции осуществляется следующими командами: Вставка – Функция – Математические – СУММПРОИЗВ – Массив 1 (C5:D5) (ресурсы единицы продукции) – Массив 2 ($C$10:$D$10) (искомые значения плана производства). Копируем функцию в ячейки С6:С8 с помощью маркера копирования.

В ячейку С11 вводим целевую функцию СУММПРОИЗВ (C9:D9;C10:D10).

Рис. 7.1 – Формульный вид документа

Перейдем теперь к постановке задачи для надстройки «Поиск решения». Для решаемой задачи целевой функцией будет функция в ячейке $С$11, изменяемыми данными – диапазон $С$10:$D$10, содержащий план производства, диапазон $Е$5:$Е$8 – используется для определения ограничений задачи.

Для обращения к надстройке «Поиск решения» используется команда меню Сервис. Но может быть так, что команда Поиск решения в этом меню отсутствует. Тогда необходимо выполнить следующую команду: Сервис – Надстройки, напротив Поиск решения поставить галочку. После активации команды Поиск решения, необходимо заполнить окно диалога по образцу (рис. 7.2).

Установить целевую ячейку $С$11 равной максимальному значению. Изменяя ячейки $С$10:$D$10. Для ввода ограничений нужно нажать кнопку Добавить.

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

Ссылка на ячейку: = $Е$5:$Е$8, вид ограничения: <=, ограничение: ссылка на ячейку: = $В$5: $В$8. Добавить.

2. Ограничение на не отрицательность переменных:

Ссылка на ячейку: = $С$10:$D$10, вид ограничения: >=, ограничение 0. Добавить.

3. Ограничение на целостность переменных:

Ссылка на ячейку: = $С$10:$D$10, вид ограничения: цел. OК.

Рис. 7.2 – Окно диалога «Поиск решения»

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

Рис. 7.3 – Результаты решения задачи

В результате решения задачи можно сделать следующий вывод. Максимальная прибыль составит 24, продукции типа P1 необходимо производить 6, продукции типа P2 – 4 (рис.7.3)

Прокомментируем решение задачи оптимизации транспортных затрат. Представим данные для решения задачи в матричной форме. Формируется матрица 3:4. Шаблон представления данных для реализации задачи представлен на рис. 7.4.

Рис.  7.4 – Шаблон с исходными данными для решения задачи оптимизации транспортных затрат

Вводим в диапазон B2:E4 коэффициенты затрат на перевозку, в диапазон B5:E5 вводим потребности в грузах, в диапазон F2:F4 вводим мощности поставщиков.

В ячейку F5 вводим формулу (=СУММ(F2:F4)) для проверки типа транспортной задачи. Если задача закрытая, то сумма мощностей поставщиков равна сумме спросу потребителей. Если баланса не соблюдается, то необходимо добавить фиктивного поставщика или потребителя, в качестве коэффициентов затрат в добавленном столбце или строки вводится значение – 0.

Для формирования шаблона решения задачи необходимо ввести следующие расчетные формулы.

Вводим в ячейку В10 формулу =СУММ(В7:В9), в ячейки C10:E10 копируем данную формулу методом протягивания (таким образом, сформировано ограничение по спросу потребителей).

Вводим в ячейку F7 формулу =СУММ(B7:E7), в ячейки F8:F9 копируем данную формулу методом протягивания (таким образом, сформировано ограничение по мощности поставщиков).

Вводим в ячейку В11 формулу для расчета значения целевой функции (=СУММПРОИЗВ(В2:Е4;В7:Е9)).

Далее обращаемся к надстройке Поиск решения. Заполняем окно диалога как показано на рис. 7.5.

Рис. 7.5 – Окно диалога «Поиск решения»

Устанавливаем целевую ячейку $B$11 равной минимальному значению. Изменяя ячейки $B$7:$E$9. Далее приступаем к вводу ограничений, нажимая кнопку Добавить.

1. Ограничение по спросу:

Ссылка на ячейку: =$B$10:$E$10, вид ограничения: =, Ограничение $B$5:$E$5. Добавить.

2. Ограничение на целостность переменных:

Ссылка на ячейку: =$B$7:$E$9, вид ограничения: = цел. Добавить.

3. Ограничение на не отрицательность переменных:

Ссылка на ячейку: =$B$7:$E$7, вид ограничения: >=, Ограничение 0. Добавить.

4. Ограничение по мощностям поставщиков:

Ссылка на ячейку: =$F$2:$F$4, вид ограничения: =, Ограничение $F$7:$F$9. ОК.

Оптимальное решение получено после нажатия кнопки Выполнить. На рис. 7.6 в диапазоне B7:E9 указано оптимальное распределение перевозок грузов для каждой пары «поставщик – потребитель».

Рис. 7.6 – Решение задачи оптимизации транспортных затрат

Контрольные вопросы по теме

“Табличный процессор MS Exсel”

1. Табличный процессор MS Excel. Основные понятия.

2. Что такое адрес ячейки? Где отображается адрес активной ячейки?

3. Маркер заполнения. Создание автосписков. Автозаполнение.

4. Работа с листами. Перемещение по листу.

5. Понятие диапазона. Виды диапазонов? Выделение диапазонов. Выделение несмежных диапазонов.

6. Типы данных в ячейках. Как выравниваются разные типы данных в ячейках?

7. Форматирование ячеек.

8. Редактирование содержимого ячеек.

9. Работа с формулами. Диагностика ошибок в формулах.

10.  Типы ссылок в формулах.

11.   Как вывести таблицу в режиме формул?

12.   Диаграммы. Создание диаграмм.

13.  Форматирование диаграмм. Как добавить легенду к созданной диаграмме? Как изменить вид диаграммы?

14. Что такое сводная таблица? Для чего нужны сводные таблицы? Создание сводных таблиц. Как выбрать математическую операцию для вычисляемого поля? Как восстановить данные в сводной таблице?

15. Как построить диаграмму по сводной таблице? Как изменить вид диаграммы?

16.  Функция. Виды функций. Форматы логических функций.

17.  Найдите в формуле ошибки =ЕСЛИ ((В3 “доллар;S4*5,05;S4*6,2

18. Печать таблиц. Изменение ориентации таблицы. Как центрировать таблицу для печати. Как добавить колонтитулы.

19. Перечислите основные типы задач экономического планирования.

20. Какие общие свойства присущи оптимизационным моделям задач экономического планирования?

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

22. Для чего формируется шаблон решения задач экономического планирования?

23. С помощью какого инструмента Microsoft Excel можно решить задачи экономического планирования?

24. Какие действия необходимо выполнить для активации надстройки «Поиск решения»?

25. Какие свойства должен иметь шаблон задач планирования экономических процессов?

26. Какую ссылку должна иметь целевая ячейка в надстройке «Поиск решения»?

27. Какие типы ограничений реализует надстройка «Поиск решения»?

28. Что означают изменяемые ячейки в надстройке «Поиск решения»?

29. Каким позициям в надстройке «Поиск решения» может равняться целевая ячейка?

Литература

1. Холи, Д. Excel 2007. Трюки / Д. Холи, Р. Холи ; пер. с англ. А. Струсевич . ─ СПб. : Питер, 2008 . ─ 363 с. : ил. ─ 978-5-91180-494-7

1.

***Полоса выделения – левое поле документа. На полосе выделения указатель мыши принимает вид белой стрелки, направленной вправо.

Реакцией на неправильный ввод формул является сообщения Excel об ошибках, то есть значение в ячейках, которые начинаются со знака #. Чтобы легче было находить и отстранять ошибки в формулах, в Excel предусмотренная простейшая диагностика ошибок, а именно: ошибки разделяются по категориям, и каждой категории отвечает свое сообщение. Список возможных значений ошибок:

† ##### –появляется, когда ширина ячейки недостаточна для размещения в ней числа, даты или времени. Чтобы отстранить ошибку, нужно расширить каморку или изменить формат числа.

† #ИМЯ? – невозможность распознать имя, которое используется. Это значение ошибки возникает, когда неправильно указано имя объекта или имеются ссылки на имя, которое было изъято; когда неверно записана функция; когда при записи адресов вместо латыни использована кириллица и т.д.

† #ЗНАЧ! – попытка некорректного использования функции. Обычной ошибкой является несоответствие данных установленному формату, например, вместо числа или даты в аргументе записан текст. Это же значение ошибки будет появляться, когда для функции или оператора, которые требуют одного значения аргумента, записывают несколько.

† #ЧИСЛО! – значение ошибки, которые означает проблему, связанную с представлением или с использованием чисел. Не исключено, что в функции с числовым аргументом используется аргумент нечислового формата. Возможно также, что в ячейку введена формула, которая возвращает слишком большое значение по модулю ( свыше 1037).

† #ССЫЛКА! – означает наличие проблемы с интерпретацией ссылок, которые имеются в формуле. Возможно, что формула содержит ссылку на ячейку, которая уже изъята, или ссылку на ячейку, в которую скопировано содержимое других ячеек.

† #ДЕЛ/0! – попытка деления на нуль. Такая ситуация чаще возникает не из-за того, что в ячейке записано явное деление на нуль (оператор /0), а как следствие использования ссылки на пустую ячейку или ячейку, которая содержит нулевое значение.

† #ПУСТО! – значение ошибки, которое появляется в случае задания в ссылке пустого множества ячеек.

† #Н/Д – сокращение от термина «неопределенные дани». Это значения ошибки обычно специально вводится в ячейки, чтобы предотвратить вычисления, которые не могут быть сделаны из-за отсутствия да?