Построение математических моделей в программировании

15

Контрольная работа №3

Задание 1. Построить одноиндексную математическую модель задачи линейного программирования

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

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

1 ед. вида А + 2 ед. вида В = 2 ед. техн. Жира + 3 ед. мед жира;

2 ед. вида А + 1 ед. вида В = 5 ед. техн. Жира + 1 ед. мед жира;

2 ед. вида А + 2 ед. вида В = 2 ед. техн. Жира + 1 ед. мед жира;

Допустим, что цена технического жира 1 рубль, а медицинского - 10 руб. за ед. продукции.

Найти наиболее выгодный производственный план, если имеется 10 ед. жира вида А и 15 ед вида В.

Решение:

Сырье Схема производства Запасы сырья

1 2 3

А 1 2 10

В 2 1 15

Прибыль, руб. 32 15 12

Таким образом, приходим к следующей математической задаче: дана система

х1+2х2+2х3<=10

2х1+х2+2х3<=15

двух линейных неравенств с тремя неизвестными и линейная функция относительно этих же переменных

F = 32х1+15х2+12х3 (руб.)

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

х1>0 ед.

x2>0 ед.

A<10 ед.

B<15 ед.

Задание 2. Для модели ЛП, соответствующей номеру Вашего варианта, найдите оптимальное решение в табличном редакторе МS Excel и продемонстрируйте его преподавателю

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

1 ед. вида А + 2 ед. вида В = 2 ед. техн. Жира + 3 ед. мед жира;

2 ед. вида А + 1 ед. вида В = 5 ед. техн. Жира + 1 ед. мед жира;

2 ед. вида А + 2 ед. вида В = 2 ед. техн. Жира + 1 ед. мед жира;

Допустим, что цена технического жира 1 рубль, а медицинского - 10 руб. за ед. продукции. Найти наиболее выгодный производственный план, если имеется 10 ед. жира вида А и 15 ед вида В.

Решение:

Сырье

Схема производства

Запасы сырья

1

2

3

А

1

2

2

10

В

2

1

2

15

Прибыль, руб.

671120,65

838875,8

167784,1625

x1

53687092

x2

25165825

F =

6,05195E+13

x3

20132659

ЛОЖЬ

Задание 3. Решить одноиндексную задачу линейного программирования графическим методом.

х1+2х2 <= 14

-5х1+3х2 <= 15

4х1+6х2 >= 24

х1 <= 0

х2 <= 0

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

х1+2х2 = 14

-5х1+3х2 = 15

4х1+6х2 = 24

х1 = 0

х2 = 0

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

Как видно на рисунке, многоугольником решений является пятиугольник АВСДЕ. Координаты любой точки, принадлежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую пятиугольнику АВСДЕ, в которой функция L(X) принимает максимальное значение. Чтобы найти указанную точку, построим вектор С= (1; 1) и прямую х1+х2=h, где h -- некоторая "постоянная такая, что прямая имеет общие точки с многоугольником решений. Например, h=480 и построим прямую x1+x2=10.

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

Если теперь взять какую-нибудь точку, принадлежащую построенной прямой и многоугольнику решений, то ее координаты определяют такие значения х1 и х2, при которых функция L(X) равна 10 руб. Далее, полагая h равным некоторому числу, большему чем 10, мы будем получать различные параллельные прямые.

Перемещая построенную прямую х1 + х2 = 10 в направлении вектора С, видим, что последней общей точкой ее с многоугольником решений задачи служит точка Е. Координаты этой точки и определяют максимальное значение функции L(X).

Найдем координаты точки Е как точки пересечения прямой (1) и оси абсцисс.

х1+2х2=14

х1=0

Решив эту систему уравнений, получим х1 = 14, х2 = 0. Следовательно, максимальное значение функции L(X) =14 + 0 = 14.

Задание 4. Не привязываясь к конкретным данным, проиллюстрируйте графически ситуации из таблицы 2. Для каждой ситуации на графике изобразить: ограничения, ЦФ в виде одной из линий уровня, вектор 2, ОДР, оптимальное решение.

Данные таблицы 2: Многоугольная незамкнутая, ЦФ не ограничена сверху.

Задание №5. Рассмотрим следующую ситуацию, с которой вы сталкиваетесь каждый день. Предположим, что вы собрались в магазин канцелярских товаров. Ваша задача сделать как можно больше покупок при условии, что вы покупаете только 3 разновидности товара, а именно ручки, карандаши и блокноты (если рассматривать весь ассортимент товара, размерность задачи значительно увеличится, при наличии достаточного количества свободного времени можете попытаться ее решить). В кармане у вас 50 у.е. и, кроме всего прочего, вам необходимо купить хотя бы 3 ручки и 2 блокнота. Вполне закономерно, что вам известна цена товаров: 10 - ручка, 5 - карандаш и 20 у.е. - блокнот.

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

Решение:

Если обозначить за Х1 - количество приобретаемых в магазине ручек, за Х2 - карандашей, а за Х3 - блокнотов, то исходную задачу можно представить в следующем виде:

Максимизировать

L(X)=X1+X2+X3

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

10* X1+5* X2+20*X3 <= 50,

X1 >= 3,

X3 >= 2,

X1, X2, X3 >= 0.

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

максимизировать

L(X)=X1+X2+X3

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

При определении начального опорного плана сталкиваемся с отсутствием единичной подматрицы и, следовательно, вводим искусственные переменные и переходим к М-задаче (M>? ):

максимизировать

L(X)=X1+X2+X3-M*X7-M*X8

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

Отыскав таким образом единичный начальный базис Б0=(А4, А7, А8), переходим к построению симплексных таблиц.

Если принять во внимание, что М - это большое положительное число, то из данной таблицы видно, что опорный план не оптимален (не все *k>0 и хотя бы одно из значений Zjk >0).

Рассчитываем

Вводя в базис А1 вместо А7, получаем новую симплексную таблицу.

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

Если вспомнить о происхождении решенной задачи, то при указанном количестве денег в кармане вам необходимо "умерить свой аппетит".

Предприятие планирует закупить четыре вида сырья, которое должно использоваться на производство продукции А, Б, В в следующих пропорциях:

У предприятия имеются заказы на поставку этих видов продукции в размерах до 10, 30 и 20 единиц соответственно. В договоре предусмотрены цены поставок за единицу продукции - 10, 8 и 20 условных единиц. Рыночная цена требуемого предприятию сырья равна 2, 5, 8 и 3 у.е. за единицу сырья соответственно.

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

Решение:

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

1 этап. Математическая постановка задачи

В начале определим, какие величины в задаче неизвестны и что нужно найти. Так как нам необходимо определить оптимальное количество закупаемого сырья, обозначим за Х1 , Х2 , Х3 и Х4 - объемы закупки сырья соответствующих видов. В этом случае количество произведенной продукции будет равняться:

- продукции А - 0,5Х1+0,1Х2+0,2Х3;

- продукции Б - 0,2Х1+0,5Х4;

- продукции В - 0,3Х2+0,2Х3+0,2Х4.

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

Максимизировать

L(X)=10(0,5X1+0,1X2+0,2X3)+8(0,2Х1+0,5Х4)+

+20(0,3Х2+0,2Х3+0,2Х4)-(2X1+5X2+8X3+3X4)

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

Условия (4.1)-(4.3) - это ограничения на объем производства продукции типа А, Б, В. При их построении мы исходили из предположения, что не имеет смысла производить больше продукции, чем мы можем реализовать.

Условия (4.4)-(4.7) - естественные условия неотрицательности переменных (объемы закупки сырья не могут быть отрицательны).

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

2 этап. Приведение задачи к каноническому виду

В соответствии с требованиями, которые были описаны выше, нам необходимо представить ограничения (4.1)-(4.3) в виде равенств. Для этого введем ослабляющие переменные со знаком (+), так как в ограничениях знак (<=), и для простоты последующей работы приведем подобные члены в целевой функции. Тогда задача примет вид:

Максимизировать

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

Таким образом, получена задача с 7 неизвестными и 10 ограничениями, допускающая решение стандартным симплекс-методом.

3 этап. Выбор начального опорного плана

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

С = {4,6, 2, -2, 5, 0, 0, 0} - вектор коэффициентов при переменных задачи в целевой функции.

В = {10, 30, 20} - вектор значений правых частей ограничений задачи.

- матрица коэффициентов при переменных в ограничениях задачи.

Как мы видим, в матрице А присутствует единичная подматрица, которая соответствует векторам А5, А6, А7, следовательно, начальный опорный план будет выглядеть так: Х0 ={0, 0, 0, 0, 10, 30, 20}.

4 этап. Решение задачи симплекс-методом

Строим начальную симплексную таблицу и проверяем начальный опорный план Х0 на оптимальность. Начальный базис Б0=(А5, А6, А7)

Из таблицы видно, что начальный опорный план не оптимален (для нашей задачи на максимум обнаруживаются отрицательные Дk и к тому же имеются значения Zjk >0). Следовательно, можно найти более хороший план. Для этого определяем вектор, вводимый в базис, и вектор, выводимый из базиса.

Так как при переходе к новому опорному плану значение целевой функции изменится и будет равно

,

то очевидно желание вводить в базис вектор, для которого Дk<0 и величина /И*Дk/ наибольшая (последнее необязательно, но часто ускоряет достижение поставленной цели). Напомним, что

Разумно ввести в базис A4 вместо A6 (выражаем X4 из второго уравнения и исключаем из остальных).

Новая симплексная таблица для Б1=(А5, А4, А7) будет выглядеть следующим образом:

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

В результате в базис войдут векторы: Б2=(А5, А4, А2). Строим новую симплексную таблицу.

Очевидно, что найденный опорный план не оптимален, следовательно, необходимо его улучшить за счет ввода в базис вектора A1. Здесь

и из базиса выводится A5. Строим новую симплексную таблицу.

Из полученной таблицы видно, что найденный опорный план оптимален для данной задачи (все Дk >=0), т.е.

Хопт=(1100/79; 2400/79; 0; 4300/79) и Lmax = 31360/79.

Ответ для нашей задачи будет выглядеть следующим образом: для того, чтобы прибыль от производства и реализации продукции трех видов была максимально возможной при данных условиях, необходимо заку-пить сырье 1-го вида в объеме - ~ 13,92 единицы; сырье 2-го вида - ~ 30,38 единицы; сырье 3-го вида не закупать вовсе; сырье 4-го вида - ~ 54,43 единицы. В результате подобной политики мы получим прибыль в размере ~396,96 у.е.

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

Следовательно, получив оптимальный план и обнаружив существование Дk=0, не соответствующего базисным векторам, можно сделать вывод, что найденный оптимальный план не единственный (можно перейти к другому плану с тем же значением целевой функции).