§3 Упражнения по матричным играм

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

Найти оптимальный состав патронной ленты, если в ней 100патронов.

3.2.Найти седловые точки и значения следующих матричных игр:

а) б)в)

г) д)

3.3. 0пределить выигрыш первого игрока в ситуации (х, у):

а) x= (1/4, 3/4),y= (4/5, 1/5);

б) x= (1/9, 1/9, 5/9, 2/9),y= (0, 0, 1);

3.4.Решить симплекс-методом следующие игры:

а) б)в)

3.5.При каких условиях следующая матричная игра имеет седловую точку(в чистыхстратегиях)?

§4. Ответы к упражнениям §§ 1-3.

1. a₁x₁ + a₂x₂+p*x₃ → max,

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

c₁x₁ ≤ b₁,

c₂x₂ ≤ b₂,

c₁x₁ ≤ b₁,

c₁x₁ + c₂x₂ + c₃x₃ = b,

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

где x_j -количество акцийi-го АП, р*=р (с₃*- с₃) -ожидаемый доход от акций 3-го АП.

1.2.

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

где x_j -количество предметовj-го вида, погружаемых на корабль.

1.3.

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

x_ij ≥ 0для всехi,j,

где x_ijплощадь подj-ю культуру на i-мучастке.

1.4.

а) 32х₁ + 15х₂ +12х₃→max,

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

x₁ + 2x₂+ 2x₃≤ 10,

2x₁+x₂+ 2x₄≤ 15,

x_j≥ 0,j=1,2,3 (целые),

где x_i.-количество использованияi-го варианта технологического процесса.

1.5.

-матричная игра (с природой). Так как седловая точка есть (3,3),то следует купить 20тонн угля.

2.1.а.Четырехугольник с вершинами (-5,-6), (-5,-3), (2,4),(5,-2).

2.1.б.Отрезок с концами (-2.3), (8,-2).

2.1.в.Луч с началом в точке (2,3).

2.1.г.Единственная точка (2,3).

2.2.а) x* = (2,3); б) х* = (3,2); в) x* = (1,2); г) x* = (1,-2).

2.4.а) x* = (0,3,0,2,0); б) x* = (1,0,0,0).

2.5.а) x* = (0,9,0,8,5); б) x* = (0,3,8,0,0).

2.6.а)

б)

3.1. 25патронов 1-го типа, 75патронов 2-го типа.

3.2.а) (1,1),v = 2:б) (1,3),v = 3;в) (1,2), (2,2), (3,2), (4,2),v= 3;г) (2,1)бv = 1/2; д)(2,2),v=3.

3.3.а) 0,55; б)1/3.

3.4.а) х* = (1/7, 2/7, 4/7),v= 15/7;

у* = (1/7, 2/7, 4/7).

б) x* = (2/5, 1/9, 22/45),v= 142/5;

y* = (5/9, 1/5, 11/45).

в) x* = (1/3, 2/3, 0),v= 1.

y* =α(1/5, 3/5, 1/5) + (1-α)(0, 2/3, 1/3), 0 ≤α≤ 1.

3.5.Если 0 < а < в < с, то (i*,j*) =(1, 1),v=a;

если 0 > a> в> с, то (i*,j*) = (1, 2),v= в;

и т.д.

Раздел V. Контрольная работа

§1.Указания по выполнению контрольной работы.

§2. Правила выбора задач контрольной работы

Контрольная работа состоит из пяти заданий:

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

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

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

4. Решение транспортной задачи методом потенциалов.

5. Решение матричных игр.

§3. Условия контрольной работы

Задание №1.Составление математической модели задачи принятия решения.

1. Фирма "Лесная пилорама"' столкнулась с проблемой наиболее рационального использования ресурсов лесоматериалов, имеющихся в одном из принадлежащих этой фирме лесных массивов. В районе данного массива имеется лесопильный завод и фабрика, на которой изготовляется фанера. Таким образом, лесоматериалы можно использовать как для производства пиломатериалов, так и для изготовления фанеры.

Чтобы получить 2,5м³коммерчески реализуемых комплектов пиломате­риалов, необходимо израсходовать 2,5м³еловых и 7,5м³пихтовых лесомате­риалов. Для приготовления 100м³фанеры требуется 5м³еловых и 10м³пихтовых лесоматериалов. Лесной массив содержит 80м³еловых и 180м³пихтовых лесома­териалов.

Согласно условиям поставок, в течение планируемого периода необходимо произвести, по крайней мере, 10м³пиломатериалов и 1200м³фанеры. Доход с 1м³ пиломатериалов составляет 16долл., а со 100м³фанеры - 60долл.

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

Предположим, что запасы чистой стали ограничены и не превышают 4т,aзапасы металлолома не превышают 6т.Отношение веса металлолома к весу чистой стали в процессе получения сплава не должно превышать 7 : 8. Производственно-технологические, условия таковы, что на процессы плавки и литья не может быть отведено более 18ч; при этом на 1т стали уходит 3ч,а на 1 металлолома- 1ч производственного времени.

3.Фирма "Лакомка" выпускает четыре вида пищевых полуфабрикатов: полуфабрикат 1,полуфабрикат 2,полуфабрикат 3и полуфабрикат 4.Каждый полуфабрикат состоит из ряда ингредиентов (таких, как крахмал, сахар, витамины и т.д.). Пусть индексiуказывает на порядковый номер ингредиента (i=1,2,…I). Обозначим черезa_ijколичество ингредиента iв одном килограмме полуфабрикатаj. Предположим, что максимальное количество ингредиентаi, которым данная фирма располагает в течение ближайшего месяца, равняетсяM_i.

Доход, получаемый с одного килограмма полуфабриката j,обозначим черезp_j. Черезx_jобозначим число килограммов полуфабриката j,произведенного фирмой "Лакомка" в течение ближайшего месяца. Пусть за этот период должно быть произведено не менее 100000килограммов полуфабриката 1, 125000 килограммов полуфабриката 2, 30000килограммов полуфабриката 3и 500000 килограммов полуфабриката 4.

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

4.Фирмой "Супертранзистор" выпускаются радиоприемники трех различных моделей: модель А, модель В и модель С.Каждое изделие указанных моделей приносит доход в размере 8, 15и 25соответственно. Необходимо, чтобы фирма выпускала за неделю не менее 100приемников модели А, 150моделей приемников модели В и 75приемников модели С.

Каждая модель характеризуется определенным временем, необходимым для изготовления соответствующих деталей, сборки изделия и его упаковки. Так, в частности, в расчете на 10приемников модели А требуется 3ч для изготовления соответствующих деталей, 4ч на сборку и 1ч на упаковку. Соответствующие показатели в расчете на 10приемников модели В равняются 3.5, 5и 1.5ч, а на 10 приемников модели С - 5, 8и 3.В течение ближайшей недели фирма может израсходовать на производство радиодеталей 150ч, на сборку 200ч и на упаковку 60ч.

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

5.Управляющий фирмы "Свежие нефтепродукты" пытается определить оптимальное распределение имеющейся в его распоряжении сырой нефти (различного сорта) по двум возможным технологическим процессам составления смесей. Технологический процесс 1характеризуется следующими показателями: из одной единицы объема сырой нефти А и трех единиц объема сырой нефти В получается пять единиц объема бензина Х и две единицы объема бензинаY.

Технологический процесс 2характеризуется другими показателями: из четырех единиц объема сырой нефти А и двух единиц объема сырой нефти В получается три единицы объема бензина Х и восемь единиц объема бензинаY. Объемы продукции, выпускаемой при реализации технологических процессов 1и 2, обозначим соответственно через х₁ и x₂.

Максимальное количество запасов сырой нефти А равняется 100единицам объема, а сырой нефти В - 150единицам объема. По условиям поставок требуется произвести не менее 200единиц объема бензина Х и 75единиц объема бензина Y. Доходы с единицы объема продукции, получаемой с помощью технологических процессов 1и 2,составляютp₁и р₂соответственно.

6. Авиакомпания "Небесный грузовик", обслуживающая периферийные районы страны, располагает 8самолетами типа 1, 15самолетами типа2, 12 самолетами типа 3,которые она может использовать для выполнения рейсов в течение ближайших суток. Грузоподъемность (в тысячах тонн) известна: 45для самолетов типа 1, 7для самолетов типа 2, 4для самолетов типа 3.

Авиакомпания обслуживает города А и В. Городу А требуется тоннаж в 20000т, а городу В -в 30000т. Избыточный тоннаж не оплачивается. Каждый самолет в течение дня может выполнить только один рейс.

Расходы, связанные с перелетом самолетов по маршруту "Центральный аэродром -пункт назначения", указаны в приведенной ниже таблице:

	тип 1	тип 2	тип 3
город А	23	5	1,4
город В	58	10	3,8

Обозначим через x_i(i = 1, 2, 3)число самолетовi-го Типа, отправленных в город А, а черезy_j(j= 1, 2, 3)число самолетов j-готипа, отправленных в город В. Построить модель оптимальных перевозок.

7.Авиакомпании "'Ночной полет" необходимо решить, какое количество топлива для реактивных самолетов следует закупить у фирм поставщиков, если число последних равно трем и имеют место следующие требования и ограничения:

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

2. Нефтяные компании констатируют следующие возможности поставки топлива в течение ближайшего месяца: а) 2500000 л -нефтяная компания 1;б) 5000000 л - нефтяная компания 2;в) 6000000 л -нефтяная компания 3.

3. Авиакомпании требуется следующее количество топлива: а) 1000000 л в аэропорту 1;б) 2000000 л в аэропорту 2;в) 3000000л в аэропорту 3;г) 4000000 л в аэропорту 4.

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

	компания I	компания 2	компания 3
аэропорт 1	12	9	10
аэропорт 2	10	11	14
аэропорт 3	8	11	13
аэропорт 4	11	13	9

Построить модель оптимизации управляющего решения.

8.Фирма "Нитроткань" производит определенного типа мелкие детали для промышленных изделий и продает их через своих посредников-оптовиков по фиксированной поставочной цене 2,50долл. за штуку. Число посредников-оптовиков равняется пяти. Коммерческие прогнозы указывают на то, что объем месячных поставок, составит: посреднику 1 - 3000штук, посреднику 2 - 3000штук, посреднику 3 - 10 000штук, посреднику 4 - 5000штук, посреднику 5 - 4000штук.

Фирма располагает следующими производственными мощностями: завод 1 - 5000деталей в месяц, завод 2 - 10000деталей в месяц, завод 3 - 12500деталей в месяц. Себестоимость одной детали, изготовленной на заводе 1,равняется 1долл., на заводе 2 -0,90долл., на заводе 3 - 0,80долл.

Транспортные расходы (в долларах), связанные с доставкой одной детали в точки оптовой продажи, приведены ниже:

	компания 1	компания 2	компания 3	компания 4	компания 5
завод 1	0.05	0.07	0.10	0.15	0.15
завод 2	0.08	0.06	0.09	0.12	0.14
завод 3	0.10	0.09	0.08	0.10	0.15

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

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

время суток часы	порядковый номер периода	минимальное число полицейских, требуемое в указан­ный период
2-6	1	20
6-10	2	50
10-14	3	80
14- 18	4	100
18-22	5	40
22-2	6	30

При этом нужно иметь в виду, что период 1следует сразу же за периодом 6.

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

10.Авиакомпании "Перманентный рейс" требуется определить, сколько стюардесс следует принять на работу в течение шести месяцев при условии, если каждая из них, прежде чем приступить к самостоятельному выполнению обязанностей стюардессы, должна пройти предварительную подготовку. Потребности в количестве стюардессо-часов (с.-ч.) летного времени известны: в январе требуется 8000с.-ч.. в феврале - 9000,в марте - 8000,в апреле - 10000,в мае- 9000,в июне - 12 000с.-ч.

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

Каждая полностью обученная стюардесса в течение месяца может иметь налет до 150ч. Авиакомпания "Перманентный рейс" в начале января уже имеет 60 опытных стюардесс. Если ресурсы стюардессо-часов (летного времени) превышают месячные потребности авиакомпании, то стюардессы работают в режиме налета менее 150ч в месяц. При этом ни одну из них не снимают с работы. Установлено также, что приблизительно 10%обученных стюардесс увольняются по собственному желанию, по семейным или другим причинам.

Опытная стюардесса обходится авиакомпании в 800долл., а обучаемая -в400долл. в месяц.

11.Фирма "Комфорт" производит холодильники, газовые плиты и кухонные раковины. В наступающем году ожидается следующий уровень сбыта:

		кварталы
	1	2	3	4
холодильники	2000	1500	3000	1000
газовые плиты	1500	1500	1000	1500
кухонные раковины	1000	3000	1500	3000

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

В течение квартала фирма может израсходовать не более 8000"приведенных часов" (п. ч.) рабочего времени. На изготовление холодильника требуется 0,5п.ч., газовой плиты - 2п.ч., а кухонной раковины - 1,5п.ч. В четвертом квартале холодильники не могут изготовляться, так как фирма планирует произвести в это время частичное переоборудование предприятия в связи с введением в действие новой конвейерной линии.

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

12.Фирма "Всякая всячина", выпускающая лезвия для бритв, объявила о переходе к производству совершенно новых лезвий улучшенного качества. Реакция потребителей на проведенную фирмой рекламную кампанию оказалась вполне удовлетворительной. Фирма имеет два предприятия и три оптовых склада, размещенных в различных географических пунктах. Лезвия на склады доставляются по железной дороге партиями. Выпуск лезвий в течение одного месяца на предприятиях 1и 2составляетS₁=100иS₂⁼200соответственно. Возможности сбыта на складах 1, 2и 3в течение этого месяца равны соответственноD₁=150,D₂⁼200иD₃=250.Как видно, возможный сбыт, т.е. спрос, значительно превышает поставки, вследствие чего часть потребностей останется неудовлетворенной.

Предположим, что транспортные расходы на доставку одного вагона лезвий с предприятия iна складjравныt_ijи что доход от сбыта этого вагона на складе jравен р_j. (Фирма может продавать свои лезвия по различным ценам в различных пунктах страны).

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

13.Фирма "С дальним прицелом" должна выполнять обязательства по поставке D₁,D₂,...,D_nединиц своей продукции в течение периодов 1, 2, ..., соответственно. При условии односменной работы объем продукции фирмы в течение периодаtсоставляетm_tединиц. При этом прямые затраты на производство одной единицы равныp_t. Пользуясь сверхурочными, фирма может выпустить дополнительноe_tединиц при прямых затратахqtна единицу, гдеq_t>p_t. Поскольку обязательства по поставкам меняются в значительных пределах, руководство фирмы полагает, что в отдельные периоды может потребоваться создание запасов с целью удовлетворения спроса в последующие периоды. Затраты на хранение единицы запаса к концу периода tсоставляютh_tденежных единиц. Постройте транспортную модель, позволяющую найти программу производства и хранения минимальной стоимости.

14.Фирма "Микродеталь" является владельцем мелкосерийного металлообрабатывающего завода. Дневной портфель заказов включаетnдеталей, каждая из которых может обрабатываться наnразличных станках. Пустьt_ij-общая продолжительность обработки деталиiна станке j(включая время наладки станка). Постройте оптимизационную модель, минимизирующую общую продолжительность выполнения всех заказов.

15.Требуется составить расписание занятий на факультете. В частности, нужно назначитьnпреподавателей вnгрупп. Ранее студенты заполнили анкеты с оценками преподавателей, И поэтому известно, в какой степени студентам нравятся преподаватели, которые вели у них занятия. (В некоторых случаях преподаватель никогда не проводил занятий в какой-либо группе, и поэтому приходится оценить, насколько этот преподаватель понравится студентам этой группы. В других случаях преподаватель не хочет или не может вести, занятия в конкретной группе, так что следует исключить возможность назначения этого преподавателя в данную группу).

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

16.Фирма имеет запасы продуктов, качество которых ухудшается при хранении, причем ухудшенное качество оценивается недельными периодами хранения. Предположим, что текущие запасы фирмы составляют четыре единицы, занумерованные индексамиi=1,2, 3, 4,срок хранения обозначается символомA_i. Фирма заключила следующий контракт на продажу этих продуктов. Одна партия должна быть поставлена черезt₁недель с начала отсчета, другая -черезt₂недель, третья -черезt₃недель и четвертая -черезt₄недель. Доход, получаемый фирмой за каждую партию, является функцией продолжительности хранения с момента поставки. Эта функция обозначаетсяR(A), где А -соответствующая продолжительность хранения.

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

17.Отдел стипендий и оказания материальной помощи студентам одного из университетов готовит предложения относительно назначения стипендий на следующий год. В качестве будущих стипендиатов выбраноnстудентов, причем студентуiпредполагается назначить стипендию не менееM_iдолл., i == 1, 2,...,n. В распоряжении отдела имеетсяsразличных стипендий. Стипендияjдает стипендиату а_j, долл. Отдел может оказаться вынужденным назначить отдельным студентам по несколько стипендий, чтобы они получали не менее чем поM_iдолл., но руководство отдела не имеет права уменьшить размер каждой стипендии ниже фиксированной суммы а_j,. Если стипендия jна рассматриваемый год вообще не назначается, то к величинеa_j, прибавляются проценты, и эта стипендия может быть назначена в увеличенном размере в следующем году.

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

18.Администрация штата объявила торги наnстроительных подрядов дляnфирм. Ни с одной фирмой не заключается более одного контракта. По политическим соображениям чиновники администрации стремятся не заключать более Nкрупных контрактов с фирмами, расположенными за пределами штата. Обозначим через 1, 2,...,sкрупные контракты, а через 1,2,...,t -фирмы, расположенные за пределами штата. Целью является минимизация общих затрат при указанном условии.

19.Фирма снабжает своими изделиями сеть небольших ресторанов, отпускающих обеды на дом. Фирма стремится обеспечить каждому владельцу такого домового ресторана достаточную прибыль. Рассматривается возможность размещенияnновых точек подобного типа в крупном микрорайоне. По имеющейся оценке, размещение ресторана в пункте jобеспечит получение приемлемого доходаR_j при условии, что в радиусе 5миль от него аналогичная торговая точка отсутствует. Примемd_ij=1,если пунктыiи jразмещения домовых ресторанов находятся в пределах радиуса 5миль, иd_ij=0в противном случае. Фирма рассчитала все возможныеd_ijи стремится выбрать схему размещения новых домовых ресторанов, обеспечивающую максимизацию общего дохода.

20.Задача о доставке грузов (задача о покрытии). Фирма "Автопегас" должна доставить грузы пяти своим клиентам в течение рассматриваемого дня. Клиенту А нужно доставить груз весом в 1единицу, клиенту В -в 2единицы, клиенту С -в 3единицы, клиентуD -в 5единиц и клиенту Е -в 8единиц. Фирма располагает четырьмя автомашинами следующей грузоподъемности: машина 1 - 2 единицы, машина 2 - 6единиц, машина 3 - 8единиц, машина 4 - 8единиц. Стоимость эксплуатации автомашины jсоставляетc_j. Предположим, что одна машина не может доставлять груз обоим клиентам А и С, аналогично одна машина не может использоваться для доставки груза обоим клиентамBиD.

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

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

1. –x₁+x₂≤ 3, 2. 3x₁–x₂≥ 9,

5x₁+ 3x₂≤ 97, 2x₁+ 3x₂≤ 50,

x₁+ 7x₂≥ 77; -x₁+ 4x₂≥ 19;

f = 3x₁ + 4x₂ → extr f= x₁ + 5x₂ → extr

3. x₁ + 4x₂ ≤ 53, 4. 6x₁ – 5x₂ ≥ 17,

x₁ – x₂ ≤ 3, x₁ + 2x₂ ≤ 34,

7x₁ + 3x₂ ≥ 71; -4x₁ + 9x₂ ≥ 17;

f = 9x₁ + 2x₂ → extr f = 5x₁ + 3x₂ → extr

5. –3x₁ + 14x₂ ≤ 78, 6. 11x₁ – 3x₂ ≥ 24,

5x₁ – 6x₂ ≤ 26, 9x₁ + 4x₂ ≤ 110,

x₁ + 4x₂ ≥ 26; -2x₁ + 7x₂ ≥15;

f = 5x₁ + 7x₂ → extr f = 9x₁ + 2x₂ → extr

7. –4x₁ + 5x₂ ≤ 29, 8. 2x₁ – x₂ ≥ 4,

3x₁ - x₂ ≤ 14, x₁ + 3x₂ ≤ 37,

5x₁ + 2x₂ ≥ 38; -4x₁ + 9x₂ ≥ 20;

f = 3x₁ + 2x₂ → extr f = 4x₁ + 3x₂ → extr

9. 10x₁ – x₂ ≥57, 10. 4x₁ – x₂ ≥ 6,

2x₁ + 3x₂ ≤ 53, 9x₁ + 8x₂ ≤ 157,

6x₁ – 7x₂ ≤ 15; -3x₁ + 11x₂ ≥ 16;

f = 5x₁ + x₂ → extr f = x₁ + x₂ → extr

11. –x₁ + x₂ ≤ 3, 12. 3x₁ – x₂ ≥ 9,

5x₁ + 3x₂ ≤ 97, 2x₁ + 3x₂ ≤ 50,

x₁ + 7x₂ ≥ 77; -x₁ + 4x₂ ≥ 19;

f = 7x₁ + 2x₂ → extr f = 6x₁ + x₂ → extr

13. x₁ + 4x₂ ≤ 53, 14. 6x₁ – 5x₂ ≥ 17,

x₁ – x₂ ≤ 3, x₁ + 2x₂ ≤ 34,

7x₁ + 3x₂ ≥ 71; -4x₁ + 9x₂ ≥ 17;

f = x₁ + 7x₂ → extr f = x₁ + 9x₂ → extr

15. –3x₁ + 14x₂ ≤ 78, 16. 11x₁ – 3x₂ ≥ 24,

5x₁ – 6x₂ ≤ 26, 9x₁ + 4x₂ ≤ 110,

x₁ + 4x₂ ≥ 26; -2x₁ + 7x₂ ≥ 15;

f = x₁ + 8x₂ → extr f = 7x₁ + x₂ → extr

17. –4x₁ + 5x₂ ≤ 29, 18. 2x₁ – x₂ ≥ 4,

3x₁ – x₂ ≤ 14, x₁ + 3x₂ ≤ 37,

5x₁ + 2x₂ ≥ 38; -4x₁ + 9x₂ ≥ 20;

f = 3x₁ + x₂ → extr f = x₁ + 3x₂ → extr

19. 10x₁ – x₂ ≥ 57, 20. 4x₁ – x₂ ≥ 6,

2x₁ + 3x₂ ≤ 53, 9x₁ + 8x₂ ≤ 157,

6x₁ – 7x₂ ≤ 15; -3x₁ + 11x₂ ≥ 16;

f = 2x₁ + 3x₂ → extr f = 8x₁ + 5x₂ → extr

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

1. –2x₁ + x₂ – x₃ + x₅ → min, 2. –8x₁ – 2x₂ + 5x₃ – 15x₄ → min,

-2x₂ + x₄ + x₅ = -3, -x₁ + 3x₂ + x₃ + 10x₄ ≤ 25,

x₃ – 2x₄ = 2, 2x₁ + x₂ + x₃ + 5x₄ ≤ 10,

x₁ + 3x₂ – x₄ ≤ 5, 10x₁+2x₂ + 2x₃ – 5x₄ ≤26,

x₁ + x₂ ≥ -3 x_j ≥ 0, j=1,…,4.

x_j ≥ 0, j=1,…,5.

3. 3x₁ + 2x₂ + x₃ → min, 4. –2x₁ – x₂ – x₃ → min,

x₁ + 3x₂ + x₃ ≥ 10 x₁ + 2x₂ + 2x₃ = 16,

2x₁ + 4x₃ ≥14, x₁ + x₂ ≤ 7,

2x₂ + x₃ ≥ 7, 3x₁ + 2x₃ ≥ 18,

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

5. x₁ + 2x₂ + x₃ → min, 6. –x₁ – 2x₂ – 3x₃ → min,

x₁ + x₂ + 2x₃ ≥ 3, 6x₁ + 4x₂ + 3x₃ ≤ 25,

2x₁ + x₂ ≥ 1, 5x₁ + 3x₂ + 2x₃ ≤ 15,

2x₂ + 3x₃ ≥ 4, x_j ≥ 0, j=1,2,3.

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

7. x₁ + 3x₂ – x₃ → min, 8. x₁ + 3x₂ – x₃ → min,

x₁ + x₂ + x₃ = 4, x₁ – x₂ + x₃ ≤ 1,

x₁ – x₂ + x₃ ≤ 2, x₁ + x₂ + x₃ ≤ 4,

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

9. x₁ – 2x₂ + x₃ → min, 10. –x₁ + 3x₂ + 2x₃ → min,

2x₁ – x₂ + x₃ ≥ 2, x₁ + x₂ + 2x₃ ≥ -5,

x₁ + x₂ – x₃ ≤ 1, 2x₁ – 3x₂ + x₃ ≤ 3,

x_j ≥ 0, j = 1,2,3. 2x₁ – 5x₂ + 6x₃ ≤ 3,

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

11. x₁ + 5x₂ + 4x₃ – 6x₅ → max, 12. 5x₁ + 2x₂ – x₃ → max,

2x₁ + 3x₂ – 4x₃ – 5x₄ ≤ 1, 2x₁ + x₂ + x₃ ≤ 5,

5x₁ – 6x₂ + x₃ – x₄ ≤ 2, 3x₁ + 2x₂ + x₃ = 6,

4x₁ + x₂ – 2x₃ + 3x₄ ≤ 2, 5x₁ + 3x₂ + 4x₃ ≥ 1,

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

13. 2x₁ + 3x₂ + 5/2x₃ → min, 14. 4x₁ + 5x₂ + 6x₃ → min,

2x₁ + x₂ + 3x₃ ≥ 6, x₁ + x₂ + x₃ ≥ 5,

2x₁ + 4x₂ + 3x₃ ≥ 16, x₁ – x₂ + 2x₃ ≥ 1,

3x₁ + 4x₂ + 2x₃ ≥ 12, x₁ – x₂ – 4x₃ ≤ -3,

x_j ≥ 0, j = 1,2,3. x₁ – x₂ + 8x₃ ≥ 4,

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

15. 2x₁ + 4x₂ + 12x₄ → min, 16. 2x₁ – 2x₂ + 3x₃ → max,

x₁ + 2x₂ + x₃ + 4x₄ ≥ 10, 2x₁ + x₂ + x₃ + x₄ ≤ 2,

2x₁ + x₂ – 2x₃ + 3x₄ ≥ 4, 2x₁ – x₂ + 2x₃ – 3x₄ ≥ 3,

x_j ≥ 0, j = 1,…,4. 3x₁ + 4x₂ – 5x₃ + 2x₄ ≤ 4,

x_j ≥ 0, j = 1,…,4.

17. 5x₁ – x₂ – 4x₃ → max, 18. 4x₁ + 6x₂ + 3x₃ → min,

-x₂ + 2x₃ ≥ 9, 3x₁ + x₂ + 2x₃ ≥9,

-x₁ + x₂ ≥ 1, x₁ + 2x₂ + 2x₃ ≥ 8,

x₁ + x₂ – 3x₃ ≥ 8, x₁ + 6x₂ ≥ 12,

x₁ – x₃ ≤ 4, x_j ≥ 0, j = 1,2,3.

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

19. x₁ – x₂ – x₃ → min, 20. –x₁ – 2x₂ + x₃ → min,

2x₁ – x₂ + x₃ ≤ 1, -x₁ + 4x₂ – 2x₃ ≤ 6,

4x₁ – 2x₂ + x₃ ≥ -2, x₁ + x₂ + 2x₃ ≥ 6,

3x₁ + x₃ ≤ 5, 2x₁ – x₂ + 2x₃ = 4,

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

Задание № 4.Решение транспортной задачи методом потенциалов.

a1 = 200, b1 = 90, a2 = 150, b2 = 100, a3 = 150, b3 = 70, b4 = 130, b5 = 110;
a1 = 300, b1 = 180, a2 = 280, b2 = 140, a3 = 220, b3 = 190, b4 = 120, b5 = 170;
a1 = 250, b1 = 180, a2 = 200, b2 = 120, a3 = 150, b3 = 90, b4 = 105, b5 = 105;
a1 = 400, b1 = 200, a2 = 250, b2 = 170, a3 = 350, b3 = 230, b4 = 225, b5 = 175;
a1 = 150, b1 = 160, a2 = 200, b2 = 70, a3 = 150, b3 = 90, b4 = 80, b5 = 100;
a1 = 280, b1 = 170, a2 = 300, b2 = 120, a3 = 220, b3 = 190, b4 = 140, b5 = 180;
a1 = 150, b1 = 180, a2 = 250, b2 = 120, a3 = 200, b3 = 90, b4 = 105, b5 = 105;
a1 = 250, b1 = 300, a2 = 400, b2 = 160, a3 = 350, b3 = 220, b4 = 180, b5 = 140;
a1 = 150, b1 = 100, a2 = 150, b2 = 70, a3 = 200, b3 = 130, b4 = 110, b5 = 90;
a1 = 280, b1 = 190, a2 = 220, b2 = 140, a3 = 300, b3 = 180, b4 = 120, b5 = 170;
a1 = 200, b1 = 120, a2 = 250, b2 = 180, a3 = 150, b3 = 105, b4 = 90, b5 = 105;
a1 = 350, b1 = 120, a2 = 400, b2 = 110, a3 = 250, b3 = 230, b4 = 170, b5 = 200;
a1 = 250, b1 = 120, a2 = 250, b2 = 110, a3 = 200, b3 = 85, b4 = 195, b5 = 190;
a1 = 250, b1 = 160, a2 = 180, b2 = 120, a3 = 270, b3 = 100, b4 = 150, b5 = 170;
a1 = 350, b1 = 160, a2 = 300, b2 = 160, a3 = 350, b3 = 180, b4 = 220, b5 = 280;
a1 = 250, b1 = 150, a2 = 350, b2 = 170, a3 = 300, b3 = 190, b4 = 210, b5 = 180;
a1 = 220, b1 = 160, a2 = 400, b2 = 180, a3 = 280, b3 = 170, b4 = 200, b5 = 190;
a1 = 160, b1 = 170, a2 = 400, b2 = 190, a3 = 240, b3 = 140, b4 = 180, b5 = 120;
a1 = 300, b1 = 190, a2 = 330, b2 = 150, a3 = 370, b3 = 240, b4 = 200, b5 = 220;
a1 = 280, b1 = 170, a2 = 340, b2 = 160, a3 = 280, b3 = 190, b4 = 200, b5 = 180;

Задание № 5.Решение матричной игры: а) показать существование или отсутствие чистых оптимальных стратегий; б) выполнить доминирование; в) свести исходную матричную игру к паре двойственных задач линейного программирования.

1. 2.

3. 4.

5. 6.

7. 8.

9. 10.

11. 12.

13. 14.

15. 16.

17. 18.

19. 20.