Высшая математика. 4

Контрольная работа.

Вариант 4.

      1. Составить математическую  модель задачи

      Фирма производит два вида продукции А  и В. Объем сбыта продукции  А составляет не менее 60% объема общего сбыта. Для изготовления продукции А и В используется одно и то же сырье, суточный объем которого ограничен величиной 100 ден. ед. Расход сырья на единицу продукции вида А – 2 ден. ед., на единицу продукции вида В – 4 ден. ед. Цены на продукцию А и В – 20 и 40 ден. ед. соответственно. Определить оптимальное распределение сырья для изготовления продукции А и В.

      Решение: Пусть Х1 – количество продукции вида А, необходимого для решения задачи оптимального распределения сырья, Х2 – количество продукции вида В. Определить оптимальное распределение сырья для изготовления продукции А и В – это значит найти такое количество продукции каждого вида, чтобы при ограниченном количестве сырья получать наибольшую прибыль от сбыта продукции. Математически это означает, что целевую функцию стоимости продукции F=20*Х1+40*Х2 нужно максимизировать.

     Первое из ограничений задачи указывает на то, что объем продукции А составляет не менее 60% объема общего сбыта. Математически это можно записать так: Х1≥0,6*(Х1+Х2) или, упростив выражение: 0,4*Х1≥0,6*Х2. Из ограничения по количеству сырья следует, что 2*Х1+4*Х2≤100. Ну и, конечно, количество продукции не должно быть отрицательным, т. е. Х1≥0, Х2≥0.

     Следовательно, математическая модель задачи принимает  вид:

     F=20*Х1+40*Х2 → МАХ

     0,4*Х1≥0,6*Х2;

     2*Х1+4*Х2≤100. 

      2. Решить графически.

     1) z=-x1+2x2 → max

     2x1+3x2≤6

     -x1+2x2≥2

     x1+3x2≥3

     x1-x2≥-2

     x1≥0, x2≥0

     2) z=-x1+2x2 → min

     3x1+2x2≤6

     3x1-x2≥-3

     x1-2x2≤-6

     2x1+x2≤4

     x1≥0, x2≥0

     3) z=-x1+3x2 → min

     2x1+2x2≤5

     -x1+x2≥-2

     -x1+2x2≤3

     -2x1+3x2≥6

     x1≥0, x2≥0

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

     Затем из начала координат строим вектор целевой функции (К1;К2), где К1 и К2 - коэффициенты при х₁ и х₂ в целевой функции. Перпендикулярно этому вектору через начало координат строим прямую z=0. Затем с помощью параллельного переноса перемещаем эту прямую в сторону множества точек, полученного в предыдущем абзаце. Последняя точка полученной области для задачи с максимизацией целевой функции и первая точка области для задачи с минимизацией и будет решением задачи.

     Действуя  по этому алгоритму, получим графические решения задач 1), 2) и 3): 
 
 

                                                                                         Z=-x₁+2x₂→max 

                                                                                         2x₁+3x₂ ≤6,

                                                                                         -x₁+2x₂ ≥2,

                                                                                          x₁+3x₂ ≥3,

                                                                                         x₁-x₂ ≥-2,

                                                                                           x₁0,x₂≥0 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Область допустимых значений задачи (решением системы неравенств) является т. А (0;2), т.к. лишь она удовлетворяет всем шести неравенствам.

     Zmax=Z(0;2)=-0+2*2=4.

     Ответ: Zmax= Z(0;2)=4. 
 
 
 
 

                                                                                           Z=-x₁+2x₂→min 

                                                                                                  3x₁+2x₂≤6,

                                                                                                  3x₁-x₂ ≥ -3,

                                                                                                    x₁-2x₂≤-6

                                                                                                    2x₁+x₂ ≤ 4

                                                                                                    x₁≥ 0,x₂ ≥ 0 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Область допустимых значений задачи (решением системы неравенств) является т.В(0;3), в которой значение функции Z= -x₁+2x₂ и будет минимальным.

     Zmin=Z(0;3)= -0+2*3=6

Ответ: Zmin=Z(0;3)=6 
 

                                                                                             Z=-x₁+3x₂→max

                                                                                                  2x₁+2x₂ ≤ 5,

                                                                                                 -x₁+x₂ ≥ -2,

                                                                                                  -x₁+2x₂≤ 3,

                                                                                                  -2x₁+3x₂≥6,

                                                                                                   x₁≥0, x₂≥0. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Ответ: нет решения. 
 

3. Решить симплекс-методом

     z=x2-3x3+2x5→min

     x1+3x2-x3+2x5=7

     -2x2+4x3+x4=2

     -4x2+3x3+8x5+x6=10

     xj≥0, j=1¸6

     Решение: После преобразования системы ограничений, имеем:

     х1=-3х2+х3-2х5+7

     х4=2х2-4х3+2

     х6=4х2-3х3-8х5+10

     Изменим и направление оптимизации функции:

     z=-x2+3x3-2x5→max

     Так как неизвестные х1, х4 и х6 встречаются  в уравнениях системы неравенств всего один раз, то запишем их в первую симплекс-таблицу в качестве базисных переменных. Неизвестные х2, х3 и х5 тогда будут небазисными или свободными переменными. Первая симплекс-таблица примет вид:

     Полученный  план будет опорным, так как в строке единиц нет отрицательных чисел, но не будет оптимальным, так как в Z-строке есть отрицательные элементы. Произведем улучшение опорного плана путем проведения первого шага жордановых исключений. Для этого выберем разрешающий элемент. Он будет находиться в строке х3, так как под ней в Z-строке отрицательный элемент. Этот столбец будет называться разрешающим. Найдем разрешающую строку по наименьшему симплексному отношению -

min (2/4, 10/3) = 2/4=1/2, значит, разрешающей строкой будет вторая, а разрешающим элементом – 4. Проводим с ним шаг жордановых исключений по следующему алгоритму:

1. Разрешающий элемент заменяем обратным;
2. Все элементы разрешающей строки делим на разрешающий элемент;
3. Все элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком;
4. Остальные элементы новой симплекс-таблицы вычисляем по формуле: bi(новый)=(bi(старый)*ark-br(старый)*aik)/ark
5. Базисная и свободная переменные, озаглавливающие разрешающие строку и столбец меняются местами.

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

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

      Из  последней симплекс-таблицы находим: х2=10/3, х3=13/6, х6=101/6, х1=х4=х5=0, тогда –Z=19/6 – max, а, значит, Z=-19/6-min.

      Ответ: Zmin=-19/6, х2=10/3, х3=13/6, х6=101/6, х1=х4=х5=0. 

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

     z=4x1-x2+x3+x4→min

     2x1-x2+4x3+x4=1

     2x1+2x2-3x3-x4=0

     xj≥0, j=1¸4

     Решение: Решим данную задачу с помощью двухфазного симплекс-метода.

     Первая  фаза (цель: при помощи искусственного базиса и симплекс-метода определить базисные переменные из числа исходных переменных). В первоначальную систему вводим искусственные переменные х5 и х6, новую целевую функцию, как сумму всех искусственных переменных, а старую присоединяем к ограничениям:

     Φ=х5+х6→min, при ограничениях:

     z-4x1+x2-x3-x4=0

     2x1-x2+4x3+x4+x5=1

     2x1+2x2-3x3-x4+x6=0

     xj≥0, j=1¸6

     Искусственные переменные х5 и х6 выбираем в качестве базисных, а все остальные х1, х2, х3, х4 в качестве небазисных. По правилу  симплекс-метода исключаем базисные переменные из целевой функции Φ, при помощи уравнений системы, содержащих эти переменные:

     х5=1-2х1+х2-4х3-х4, х6=-2х1-2х2+3х3+х4, тогда:

     Ф=(1-2х1+х2-4х3-х4)+(-2х1-2х2+3х3+х4)=-4х1-х2-х3+1, или:

     Ф+4х1+х2+х3=1

     Начальное допустимое базисное решение: х0=(х1-0, х2-0, х3-0, х4-0, х5-0, х6-0)=(0,0,0,0,1,0) называется искусственным базисом. При помощи этого базиса и записанных выше выражений строим первую симплекс-таблицу:

     До  конца первой фазы роль нулевой строки играет строка Ф, все остальное как в симплекс-методе. Строка Z не участвует в выборе ведущей строки. Ясно, что минимального значения, равного нулю Ф достигает при х5=х6=0, т.е. задача минимизации функции Ф будет решена, если все искусственные переменные будут вытеснены из базиса таблицы 1, а Ф=0. В результате соответствующих преобразований по правилу прямоугольника получим симплексную таблицу 2, записав строку с х6 с противоположным знаком и введя в число базисных переменную х1:

     Далее введем в число базисных переменную х2, проведя симплексное преобразование с элементом 2, выделенным полужирным шрифтом:

     Вторая  фаза (цель: применяя обычный симплекс-метод к полученной в результате первой фазы таблице, получить оптимальное решение исходной задачи). Допустимое базисное решение. для последней таблицы есть x⁰=(0,1/3,0,0), а этому решению соответствует z=-1/3, значение которой будет минимальным.

     Ответ: x⁰=(0,1/3,0,0), а этому решению соответствует z min=-1/3 

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

     z=2x1+3x2+4x3→min

     2x1-3x2+x3≥2

     -x1+3x2≤3

     2x1-4x2+3x3≥1

     -x1-x2+4x3≤4

     xj≥0, j=1¸3

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

     z=2x1+3x2+4x3→min

     2x1-3x2+x3+x4=2

     -x1+3x2+x5=3

     2x1-4x2+3x3+x6=1

     -x1-x2+4x3+x7=4

     xj≥0, j=1¸7

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

     Исходя  из условия исходной задачи можно  составить двойственную ей, в каноническом виде она будет выглядеть так:

     g=2y1+3y2+y3+4y4→max

     2y1-y2+2y3-y4-y5=2

     -3y1+3y2-4y3-y4-y6=3

     y1+3y3+4y4-y7=4

     yj≥0, j=1¸7 

      6. Решить транспортную  задачу

     а^Т=(22, 11, 15), b^T=(16, 10, 10)

     C= (2  3  2

2. 3  3
3. 4  5)

      Решение: Данные задачи говорят о том, что нужно найти оптимальный план перевозок со складов аi (i=1,3) потребителям вj (j=1,3), при котором транспортные расходы на перевозку будут минимальными. Т.е., z=ΣΣcij*xij, cij – стоимость перевозок со склада аi (i=1,3) потребителю вj (j=1,3), xij - количество перевозимого товара. Найдем первоначальный опорный план по критерию минимальной стоимости. Для этого начнем заполнять таблицу с клетки (1,1) имеющей наименьшую стоимость перевозки, равную 2. Значение х11 будет равно минимальному среди а1 и в1 (16). Потребности потребителя в1 мы удовлетворили полностью, а на складе а1 осталось еще 6 единиц товара. Отправим их потребителю в3 из-за минимальной стоимости перевозки. Действуя далее тем же образом, получим таблицу 1:

      На  складе а3 осталось 12 единиц невостребованного товара. Для проверки оптимальности полученного опорного плана, обозначим строки через u1, u2, u3, а столбцы через v1, v2 и v3 и проверим оптимальность опорного плана с помощью метода потенциалов.

      Составим  систему уравнений по заполненным  клеткам:

      U1+v1=2

      U1+v3=2

      U2+v2=3

      U2+v3=3

      U3+v2=4

      Так как неизвестных в системе 6, а  уравнений всего 5, то выберем в  качестве свободной переменную u1. Пусть u1=0, тогда далее находим: v1=2, v3=2, u2=1, v2=2, u3=2.

      Оценки незаполненных клеток будут равны: с12=3-(u1+v2)=3-(0+2)=1, c21=2-(1+2)=-1<0, c31=3-(2+2)=-1<0, c33=5-(2+2)=1. Так как среди оценок незаполненных клеток есть отрицательные, то полученный опорный план неоптимален. Для его улучшения введем в число заполненных клетку (2,1) как имеющую среди отрицательных минимальную стоимость перевозки. Для этого составим замкнутый контур (см. таблицу 1), и проведем по нему смещение по клеткам (1,1)-(1,3)-(2,3)-(2,1), уменьшив значение в первой и третьей клетках, увеличив во второй и четвертой. Величина смещения = минимальному значению для клеток с отрицательным смещением (в данном случае – 4). Получим в результате таблицу 2:

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

      U1+v1=2

      U1+v3=2

      U2+v1=2

      U2+v2=3

      U3+v2=4

      Пусть u1=0, тогда далее находим: v1=2, v2=3, u2=0, v3=2, u3=1. Оценки незаполненных клеток будут равны: с12=3-(u1+v2)=3-(0+3)=0, c23=3-(0+2)=1, c31=3-(1+2)=0, c33=5-(1+2)=2. Так как среди оценок нет отрицательных, то мы достигли оптимального плана перевозок со складов аi потребителям bj: (12   0   10

                   4    7     0

                   0    3     0), тогда транспортные  затраты будут минимальными и  составят: zmin=2*12+2*10+2*4+3*7+4*3=85 ден. ед. 
 
 

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

     В зависимости от погодных условий (мягкая зима, обычная зима, суровая зима) хозяин может заготовить 7, 9 или 11 единиц топлива. Если топлива окажется недостаточно, он сможет закупить недостающее количество по цене 2 денежных единицы за единицу топлива. Излишки топлива он сможет хранить, арендуя склад, по цене 1 денежная единица за единицу топлива.

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

1. вероятности наступления мягкой, обычной и суровой зимы равны соответственно 0,2; 0,6; 0,2;
2. три типа зимы равновероятны;
3. с использованием критерия Гурвица с γ=0,6

      Решение: Обозначим через А – сознательного игрока матричной игры – хозяина дома, заинтересованного в минимизации затрат на покупку и хранение топлива зимой. Тогда второй игрок П – природа, безразличная к результатам тех или иных действий игрока А. Заготавливая летом уголь хозяин может ориентироваться либо на мягкую (первая его чистая стратегия А1), либо на обычную (вторая чистая стратегия А2), либо на суровую зиму (третья чистая стратегия А3), покупая соответственно 7, 9 или 11 единиц топлива. Таким образом, платежная матрица статистической игры будет иметь размер 3х3 и иметь вид (таблица 1):