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

      Из  последней симплекс-таблицы находим: х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):