Задач линейного программирования

 

Графический метод используется для решения задач с двумя переменными следующего вида:

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

Область допустимых решений задачи строится как пересечение (общая часть) областей решений каждого из заданных ограничений. Областью решений линейного неравенства является одна из двух полуплоскостей, на которые прямая , соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку, если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку. Областью допустимых решений задачи является общая часть полуплоскостей – областей решений всех неравенств системы ограничений.

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

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

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

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

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

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

1. Построить область допустимых решений.

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

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

4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум – в противоположном направлении.

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

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

Пример. Решить задачу линейного программирования

Решение. Строим область допустимых решений задачи. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат (рис.) строим прямую 2 , соответствующую ограничению (1). Находим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1). Для этого достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Так как данная прямая не проходит через начало координат, подставляем координаты точки О (0,0) в первое ограничение . Получим неравенство . Следовательно, точка О не лежит в полуплоскости решений. Таким образом, стрелки на концах данной прямой должны быть направлены в полуплоскость, не содержащую точку О. Аналогично строим прямые , и области решений ограничений (2) и (3). Находим общую часть полуплоскостей, учитывая при этом условие неотрицательности переменных. Полученную область допустимых решений отметим на рис. штриховкой.

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

 

 

 

Элементы теории игр

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

Типичный конфликт характеризуется тремя основными составляющими:

1. Заинтересованными сторонами;

2. Возможными действиями этих сторон;

3. Интересами сторон.

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

Опишем некоторые основные понятия, используемые в этой теории.

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

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

- выработке принципов оптимальности, то есть того, какое поведение игроков следует считать оптимальным (разумным, целесообразным);

- выяснению реализуемости этих принципов, то есть установлению существования оптимальных в выработанном смысле ситуаций;

- отысканию этих реализаций.

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

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

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

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

Рассмотрим следующий пример.

Пример 2. Два игрока А и В, не глядя друг на друга, кладут на стол по картонному кружку красного, зеленого или синего цветов, и расплачиваются друг с другом так, как показано в матрице игры

(напомним, что у этой 3 3-матрицы строки соответствуют стратегиям игрока А, а столбцы – стратегиям игрока В.

Считая, что эта 3 3 игра повторяется многократно, попробуем определить оптимальные стратегии каждого из игроков.

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

Запишем эти минимальные выигрыши в правом столбце таблицы:

 

A1	-2		-1	-2
A2
A3		-3		-3

 

 

Если игрок А будет придерживаться этой стратегии, то ему гарантирован выигрыш, не меньший 1, при любом поведении противника в игре.

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

 

	B1	B2	B3
A1	-2		-1	-2
A2
A3		-3		-3

 

Если игрок В будет придерживаться этой стратегии, то при любом поведении противника он проиграет не больше 1.

В рассматриваемой игре числа maxmin и minmax совпали:

= =1.

Выделенные стратегии A₂ и B₃ являются стратегиями игроков А и В,

в следующем смысле:

при многократном повторении игры отказ от выбранной стратегии любым из игроков уменьшает его шансы на выигрыш (увеличивает шансы на проигрыш).

Тем самым, ситуация оказывается равновесной.

Число называется нижней ценой игры.

Число называется верхней ценой игры.

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

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

Цена игры совпадает с элементом матрицы игры А, расположенным на пересечении -й строки и -го столбца – минимальным в своей строке и максимальным в своем столбце.

Этот элемент называют Седловой точкой матрицы А, или точкой равновесия, а про игру говорят, что она имеет седловую точку.

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

Замечание. Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

Матричные игры с Седловой точкой важны и интересны, однако более типичным является случай, когда применение описанного алгоритма приводит к неравенству

.

Пример: Найдите решение следующей матричной игры .

Решение:

 

			min
		-2	-2
mах:

- нижняя цена игры

- верхняя цена игры

Т.к. , то имеет место матричная игра в смешанных стратегиях, седловой точки нет.

 

Пусть - произвольная смешанная стратегия игрока В. Если игрок А выбирает чистую стратегию, то средний выигрыш игрока В в ситуации будет равным , где . Зависимость этого выигрыша от переменной описывается прямой.

	-2

Получим,

 

 

(1)

(2)

(3)

 

Выделим верхнюю огибающую. Нижняя точка верхней огибающей является точкой пересечения прямых (1) и (2). Получим,

, значит .

Полагая , получим:

р
1- р		-2

, значит

Цена игры .

Ответ: ; ; .

 

 

Контрольные задания

Задача 1

Из перетасованной колоды (36 карт) последовательно извлекаются 3 карты. Какова вероятность события, что эти 3 карты:

1. Все одной масти?

2. Все разных мастей?

3. Содержат хотя бы одного туза?

4. Два туза и одна дама?

5. Туз, король, дама в заданном порядке?

6. Туз, король дама в произвольном порядке?

7. Одного цвета (чёрные или красные)?

8. Все пики?

9. Все картинки?

10. Не содержат картинок?

11. 6 бубей, 7 червей, дама пик в заданном порядке?

12. 6 бубей, 7 червей, дама пик в произвольном порядке?

13. Все дамы?

14. Нет дам?

15. Третья взятая карта окажется дамой?

16. Хотя бы одна дама?

17. Нет тузов и королей?

18. Все валеты?

19. Короли и валеты?

20. Сумма очков равна 21 (валет- 2, дама- 3, король-4, туз- 11, остальные 6, 7, 8, 9, 10). ((7,7,7), (9,9,3), (9,6,6), (2,8,11), (2,9,10), (3,7,11), (3,8,10), (4,6,11), (4,7,10), (4,8,9), (6,7,8)).

 

Указания к решению задачи 1

Все 20 вариантов этой задачи решаются по формуле классической вероятности: .

Если из n- элементарного множества выбирается m- элементарное подмножество, то полное число событий есть число возможных выборов, т.е. равно если имеет значение порядок выбираемых элементов, и если порядок безразличен. Напомним, что причём

В качестве примера, пусть А – событие, состоящее в том, что среди трёх карт окажется марьяж, т.е. король с дамой одной масти. Тогда полное число событий равно , а число событий, благоприятствующих А, равно (4 способа выбора марьяжной масти умножаются на 34 способа дополнить марьяж третьей картой). Поэтому

 

 

Задача 2

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

2. Документ находится в столе с вероятностью , причём с равной вероятностью в любом из 4 ящиков. После просмотра 3 ящиков документ не был обнаружен. Какова при этом вероятность, что он лежит в четвёртом ящике?

3. Имеются 2 конфетницы, в одной лежат 4 шоколадные конфеты и 8 карамелей, в другой- 8 шоколадных и 8 карамелей. Наугад вынимаются по 2 конфеты из каждой конфетницы. Найти распределение случайной величины, равной числу вынутых шоколадных конфет, и её математическое ожидание.

4. –5. В телеграфном сообщении точки составляют 60% символов, тире – 40%. Вероятность в процессе передачи быть искажённым для тире равна 0,1, для точки- 0,2. Найти вероятность того, что передавалась точка, и вероятность того, что передавалось тире, если:

4. Принята точка.

5. Принято тире.

6. Три стрелка выстрелили по мишени, причём вероятности попадания у них равны соответственно 0,5, 0,6 и 0,9. В мишени оказалось 2 пробоины. Найти вероятность промаха для каждого из стрелков.

7. Стрелок поражает цель с вероятностью 0,9. Какое минимальное число патронов ему необходимо иметь, чтобы поразить цель с вероятностью не менее 0,99?

8. Монета бросается 10 раз. Какова вероятность, что число выпадений орла превысит число выпадений решки?

9. Из партии, содержащей 30% электроламп на 127 в и 70% электроламп на 220 в, выбираются наугад 5 ламп, ввинчиваются в люстру и включаются в сеть 220 в. Какова вероятность, что останется гореть хотя бы одна лампа? Все лампы? Найти математическое ожидание числа горящих ламп.

10. –12. В лесу 60 зайцев. У охотника 100 патронов. Какова вероятность, что все зайцы будут перестреляны, если охотник попадает с вероятностью:

10. 0,5?

11. 0,6?

12. 0,7?

13. Решение «да» или «нет» принимается по большинству голосов советом из 5 человек. Какова вероятность совершить ошибку, если вероятность ошибки для каждого члена совета равна 0,1?

14. Работа прибора прекратилась вследствие выхода из строя одной из 100 однотипных деталей. Поиск неисправности ведётся последовательной проверкой деталей. Какова вероятность, что придётся произвести более 50 проверок? Найти математическое ожидание числа проверок.

15. Маршрут независимо обслуживается тремя видами общественного транспорта: трамваем с интервалом движения 3 минуты, троллейбусом с интервалом движения 4 минуты и автобусом с интервалом движения 5 минут. Какова вероятность, что на остановке придётся прождать более 2 минут? Найти математическое ожидание времени ожидания.

16. А и В играют в следующую игру. Бросается кость и А платит В столько у.е., сколько выпадает очков, если выпало 1, 2, 3 или 4. Если же выпадает 5 или 6, то В платит А число у.е., равное числу очков. Используя математическое ожидание, ответить на вопрос, кому выгодна игра, А или В?

17. А и В играют в следующую игру. А платит В 1 у.е. и тянет из перетасованной колоды (36 карт) одну карту. Если он вытянул туза, то В платит А 10 у.е. Используя математическое ожидание, установить, кому выгодна игра, А или В?

18. Кость бросается 40 раз. Воспользовавшись нормальным приближением, найти вероятность того, суммарное число очков будет не менее 120?

19. За 360 рабочих дней года магазин продал 720 холодильников. Считая, что число проданных за день холодильников подчиняется распределению Пуассона, найти вероятность продать за день не менее трёх холодильников.

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

 

 

Задача 3

 

Из изучаемой налоговыми органами обширной группы населения было случайным образом отобрано 10 человек и собраны сведения об их доходах за истекший год в тыс. рублей: х₁, х₂,..., х₁₀. Найти выборочное среднее, выборочную дисперсию, исправленную выборочную дисперсию. Считая распределение доходов в группе нормальным и используя в качестве его параметров выборочное среднее и исправленную выборочную дисперсию, определить, какой процент группы имеет годовой доход, превышающий а тыс. рублей.

 

	х1	х2	х3	х4	х5	х6	х7	х8	х9	х10	а

 

 

Задача 4

1)–5) На коробках с конфетами было подготовлено 2 варианта рисунка. В течение 30 дней ежедневно регистрировалось число проданных коробок каждого вида, которое колебалось от 0 до 8. По заданной таблице при уровне значимости 0,05 ответить на вопрос, повлиял ли рисунок на объём продаж. (1-ая строка таблицы – число проданных коробок, 2-ая и 3-я строки – количество дней с данным объёмом продаж соответственно коробок первого и второго типа).

 

1)

 

2)

 

3)

 

4)

 

5)

6)–10). Для изучения влияния курения на продолжительность жизни отслеживалась продолжительность двух групп населения по 100 человек каждая- курящих и некурящих. Пользуясь таблицей при уровне значимости 0,05 ответить на вопрос, влияет ли курение на продолжительность жизни. (1-ая строка таблицы число лет, 2-ая и 3-я строки- число человек, проживших данное число лет соответственно в группах курящих и некурящих).

6)

 

7)

 

8)

 

9)

 

10)

 

11)–15). Во второй тур президентских выборов вышли два кандидата: А и В. Накануне второго в результате проведённого опроса лиц, желающих проголосовать за одного из двух кандидатов, было получено, что 51 процент опрошенных проголосует за кандидата А и 49- за кандидата В. Какова вероятность для каждого из кандидатов быть избранным, если для опроса использовалась репрезентативная выборка объёмом

11). 2000 человек?

12). 4000 человек?

13). 6000 человек?

14). 8000 человек?

15). 10000 человек?

16)–20). На технологической линии по сборке часов средняя по множеству производимых часов скорость хода может регулироваться, а разброс в скорости, обусловленный используемой технологией, не регулируется. Результаты контрольного измерения скорости хода 100 часов, выраженные как отклонение в секундах за сутки, представлены в таблице. При уровне значимости 0,05 выяснить, есть ли основания для регулировки линии.

16)

-5	-4	-3	-2	-1

 

17)

-5	-4	-3	-2	-1

 

18)

-5	-4	-3	-2	-1

 

19)

-5	-4	-3	-2	-1

 

20)

-5	-4	-3	-2	-1

 

Задача 5

1)–10) В таблице приведены средние мировые цены на сырую нефть Х (дол. за баррель) и бензин У (центов за галлон) с 1975 по 1988 год. На графике в координатах Х, У нанести 5 точек, относящихся к годам, указанным в варианте задачи. По пяти точкам получить методом наименьших квадратов уравнение линейной регрессии У=аХ+b и представить его на графике.

 

Год	Бензин, У- центов за галлон	Сырая нефть, Х-дол. за баррель
		7,67
		8,19
		8,57
		9,00
		12,64
		21,59
		31,77
		28,52
		26,19
		25,88
		24,09
		12,51
		15,40
		12,57

 

1. 1975-1979 годы

2. 1976-1980 годы

3. 1977-1981 годы

4. 1978-1982 годы

5. 1979-1983 годы

6. 1980-1984 годы

7. 1981-1985 годы

8. 1982-1986 годы

9. 1983-1987 годы

10. 1984-1988 годы

11)–20). Желая установить цену на товар, обеспечивающую максимальную прибыль, магазин в течение 5 рабочих дней недели продавал получаемые от поставщика изделия с наценкой соответственно 1, 2, 3, 4 и 5 у.е. Количество единиц проданного товара в каждый из 5 дней приведено в таблице по вариантам. Методом наименьших квадратов получить уравнение квадратичной регрессии прибыли на наценку У= , где Х- наценка, а У- прибыль, определяемая как произведение наценки на количество единиц проданного товара. С помощью уравнения определить наценку, дающую максимальную прибыль.

 

На- ценка № варианта

 

 

Задача 6

 

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

 

Производящие отрасли	Потребляющие отрасли	Конечная продукция
I	II	III
I
II
III

 

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

 

№ вар.	а11	а12	а13	а21	а22	а23	а31	а32	а33	y1	y2	y3
	0,3	0,1	0,3	0,1	0,1	0,1	0,0	0,1	0,1
	0,2	0,0	0,4	0,4	0,1	0,4	0,4	0,0	0,4
	0,3	0,4	0,0	0,3	0,2	0,1	0,3	0,0	0,4
	0,3	0,1	0,2	0,3	0,1	0,0	0,3	0,3	0,4
	0,4	0,2	0,2	0,2	0,4	0,2	0,3	0,2	0,1
	0,3	0,1	0,3	0,2	0,1	0,3	0,3	0,1	0,0
	0,1	0,4	0,2	0,3	0,3	0,3	0,1	0,3	0,4
	0,4	0,1	0,1	0,3	0,1	0,2	0,1	0,4	0,1
	0,1	0,4	0,1	0,1	0,4	0,3	0,1	0,1	0,2
	0,2	0,4	0,0	0,1	0,2	0,0	0,2	0,2	0,2
	0,2	0,0	0,2	0,3	0,2	0,1	0,2	0,0	0,1
	0,2	0,4	0,0	0,4	0,0	0,3	0,1	0,3	0,1
	0,4	0,0	0,2	0,2	0,4	0,0	0,2	0,1	0,0
	0,3	0,1	0,0	0,1	0,2	0,1	0,4	0,0	0,1
	0,0	0,4	0,1	0,4	0,1	0,1	0,3	0,0	0,2
	0,3	0,4	0,1	0,2	0,2	0,1	0,3	0,2	0,1
	0,1	0,0	0,3	0,1	0,0	0,3	0,2	0,1	0,0
	0,1	0,1	0,2	0,1	0,2	0,3	0,1	0,2	0,3
	0,0	0,4	0,1	0,4	0,1	0,0	0,3	0,0	0,1
	0,3	0,4	0,1	0,1	0,2	0,4	0,3	0,4	0,1

 

Задача 7

 

Составить математические модели следующих задач:

 

1)–5). Кондитерский цех выпускает три вида конфет A,B,C, используя три вида сырья (какао, сахар, наполнитель). Нормы расхода сырья на производство 10 кг конфет а также прибыль от реализации 10 кг конфет каждого вида приведены в таблице:

 

Сырье	Нормы расхода сырья	Запасы сырья
A	B	C
какао
сахар
наполнитель
прибыль

 

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

 

№ вар.

а11

а12

а13

а21

а22

а23

а31

а32

а33

b1

b2

b3

c1

c2

с3

 

6)–10). В рационе бройлерных цыплят птицеводческой фермы используется два вида кормов A и B. Цыплята должны получать три вида питательных веществ (известняк, зерно, соевые бобы). Содержание единиц питательных веществ в 1 кг каждого из видов корма приведено в таблице:

 

Питательные вещества	Содержание питательного вещества в единице корма	Необходимое количество питательного вещества
A	B
известняк
зерно
соевые бобы
стоимость единицы корма

 

Составить рацион кормления, обеспечивающий минимальные затраты.

 

№ вар.	а11	а12	а21	а22	а31	а32	b1	b2	b3	c1	c2

 

11)–20). Некоторой компании принадлежат три фермы, на которой выращивают овощи, предназначенные для последующей обработки на двух холодильных заводах компании. Одним из выращиваемых овощей являются бобы, которые холодильные заводы продают. В таблице приведены максимальные значения урожая для каждой фермы, прогнозные значения спроса на следующий сезон для каждого завода и стоимость транспортировки бобов.

 

Фермы	Заводы	Урожай, т
Спрос, т

 

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

№ вар.	c11	c12	c21	c22	c31	c32	а1	а2	а3	b1	b2

 

 

Задача 8

 

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