Теория двойственности в задачах линейного программирования
Утверждение 1. Если X и Y − допустимые точки задач (1) и (2), соответственно, то
При этом, если для каких то допустимых точек 
Доказательство. Запишем взвимно двойственные задачи (1) и (2) в матричном виде.
Исходная задача:
где 
Сделаны также следующие обозначения:
Двойственная задача:
где 
Имеем:
(5b) и (5c) можно записать так:
Легко показать, что
Действительно:
Множители в правой части выражения (9) неотрицательны. Тогда их произведение не отрицательно, т.е. выполнено условие (8).
Учитывая (7) и (8) упростим выражение 6:
С другой стороны:
(4b) и (4c) можно записать так
Учитывая (12) и Y1 упростим выражение (11):
Из (9) и (13) получим:
т.е. выполнено условие (3).
Докажем вторую часть утверждения 1. Для любой допустимой точки x задачи (1) 
С другой стороны для любой допустимой точки y задачи (2)
т.е. 
Теорема 1 (первая теорема двойственности). Если исходная задача имеет решение
Если в исходной задаче целевая функция неограничена, то в двойственной задаче допустимая область пуста.
Отметим, что обратное утверждение неверно. Из несовместности системы системы ограничений одной из задач не следует неограниченность целевой функции для другой. В этом случае системы ограничений обеих задач могут быть несовместными. Приведем пример.
Представленные задачи взаимно двойственные, и в этих задачах допустимые области пусты.
Теорема 2 (вторая теорема двойственности или условие дополняющей нежесткости). Планы 
или выполняется условие:
Докажем эквивалентность условий (15) и (16) с условием (17).
Из (4с) и (5с) имеем:
Откуда:
Из (15) и (16) имеем:
Подставляя (19),(20) в (21),(22) соответственно и упрощая получим:
Выразив, например, 
или
А Запись (25) − это другой вид записи равенства (17).
Примеры задач линейного программирования 1 задача об
Примеры задач линейного программирования
1. Задача об использовании ресурсов (задача планирования производства)
1. 1. Для изготовления двух видов продукции P 1 и P 2 используют четыре вида ресурсов S 1, S 2, S 3 и S 4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в табл. 1 (цифры условные).
Таблица 1. Вид ресурса Запас ресурса S 1 S 2 S 3 S 4 18 16 5 21 Число единиц ресурсов, затрачиваемых на изготовление единицы продукции P 1 P 2 1 2 3 3 1 1 – Прибыль, получаемая от единицы продукции P 1 и P 2 , – соответственно 2 и 3 руб.
Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Решение. Составим экономикоматематическую модель задачи.
Обозначим x 1 и x 2 — число единиц продукции соответственно P 1 и P 2, запланированных к производству. Для их изготовления (см. табл. 1) потребуется (1 x 1 3 x 2) единиц ресурса S 1, (2 x 1 1 x 2) единиц ресурса S 2, (1 x 2) единиц ресурса S 3 и 3 x 1; единиц ресурса S 4.
Так как потребление ресурсов S 1, S 2, S 3 и S 4 не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств: (1)
По смыслу задачи переменные (2) Суммарная прибыль F составит 2 x 1 руб. от реализации продукции P 1 и 3 x 2 руб. — от реализации продукции , т. е. (3)
Итак, экономико-математическая модель задачи: найти такой план выпуска продукции Х=(x 1, x 2), удовлетворяющий системе (1) и условию (2), при котором функция (3) принимает максимальное значение. Задачу легко обобщить на случай выпуска п видов продукции с использованием т видов ресурсов.
Обозначим хj (j = 1, 2, . . . , п) — число единиц продукции Pj, запланированной к производству; bi (i =1, 2, . . . , т) — запас ресурса Si, aij – число единиц ресурса Si , затрачиваемого на изготовление единицы продукции Pj (числа aij часто называют технологическими коэффициентами); cj— прибыль от реализации единицы продукции Pj.
Тогда экономикоматематическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план Х=(x 1, x 2, …xn) выпуска продукции, удовлетворяющий системе
(4)
и условию (5) при котором функция (6) принимает максимальное значение.
2. Задача составления рациона (задача о диете, задача о смесях) Имеется два вида корма I и II, содержащие питательные вещества (витамины) S 1, S 2 и S 3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в табл. 2 (цифры условные).
Таблица 2. Вид ресурса Запас ресурса S 1 S 2 S 3 9 8 12 Число единиц питательных веществ в 1 кг корма I II 3 1 1 1 2 6
Стоимость 1 кг корма I и II соответственно равна 4 и 6 руб. Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержание каждого вида питательных, веществ было бы не менее установленного предела.
Решение. Составим экономико-математическую модель задачи. Обозначим x 1 и x 2 — количество кормов I и II, входящих в дневной рацион. Тогда этот рацион (см. табл. 2) будет включать (3 x 1 1·x 2) единиц питательного вещества S 1, (1·x 1 2·x 2) единиц вещества S 2 и (1·x 1 6·x 2) единиц питательного вещества S 3.
Так как содержание питательных веществ S 1, S 2, и S 3 в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим систему неравенств: (7)
Кроме того, переменные (8) Общая стоимость рациона составит (в руб. ) (9) Итак, экономико-математическая модель задачи: составить дневной рацион , удовлетворяющий системе (7) и условию (8), при котором функция (9) принимает минимальное значение.
Для формулировки задачи в общей постановке обозначим: — число единиц корма п-го вида; — необходимый минимум содержания в рационе питательного вещества ; — число единиц питательного вещества
в единице корма j-го вида; — стоимость единицы корма j-го вида. Тогда экономико-математическая модель задачи примет вид:
найти такой рацион удовлетворяющий системе (10)
и условию (11) при котором функция (12) принимает максимальное значение.
Геометрический метод решения задач линейного программирования
Рассмотрим задачу в стандартной форме (4)—(6) с двумя переменными (n=2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных п больше числа уравнений т на 2, т. е. п — т = 2.
Рисунок 1.
Пусть геометрическим изображением системы ограничений является многоугольник ABCDE (рис. 1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F= с1 х1 с2 х2 принимает максимальное (или минимальное) значение.
Рассмотрим так называемую линию уровня линейной функции F, т. е. линию, вдоль которой эта функция принимает одно и то же фиксированное значение а, т. е. F = а, или (1)
Уравнение линии уровня функции (1) есть уравнение прямой линии. При различных уровнях а линии уровня параллельны, так как их угловые коэффициенты определяются только соотношением между коэффициентами с1 и с2 и, следовательно, равны. Таким образом, линии уровня функции F — это своеобразные “параллели”, расположенные обычно под углом к осям координат.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону — только убывает.
Пусть имеются три линии уровня (I) (III) причем линия II заключена между линиями I и III. Тогда или
Рисунок 2.
Для определения направления возрастания рекомендуется изобразить две линии уровня и определить, на которой из них уровень больше. Например, одну из линий можно взять проходящей через начало координат (если линейная функция имеет вид т. е. без свободного члена, то это соответствует нулевому уровню).
Другую линию можно провести произвольно, так, например, чтобы она проходила через множество решений системы ограничений. Далее, определив направление возрастания линейной функции (обозначим его вектором q),
найдем точку, в которой функция принимает максимальное или минимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 1 — это точка С или А).
Решить геометрически задачу 1 При ограничениях (I) (III) (IV) (V, VI)
Рисунок 3.
Решение. Изобразим многоугольник решений на рис. 3. Очевидно, что при F=0 линия уровня 2 x 1 3 x 2=0 проходит через начало координат (строить ее не обязательно). Зададим, например, F=6 и построим линию уровня 2 x 1 3 x 2=6.
Ее расположение указывает на направление возрастания линейной функции (вектор q ). Так как рассматриваемая задача—на отыскание максимума, то оптимальное решение — в угловой точке С, находящейся на пересечении прямых I и II, т. е. координаты точки С определяются решением системы уравнений :
Откуда x 1=6, x 2=4, т. е. С(6; 4) Максимум (максимальное значение) линейной функции равен.
Итак, Fmax=24 при оптимальном решении x 1=6, x 2=4, т. е. максимальная прибыль в 24 руб. может быть достигнута при производстве 6 единиц продукции Р 1 и 4 единиц продукции Р 2.
Решить геометрически задачу при ограничениях: (I) (III) (IV, V)
Рисунок 4.
Решение. Многоугольник решений представляет собой неограниченную многоугольную область (рис 4). По расположению линии уровня, например, F=12 или 4 х1 6 x 2=12, находим направление вектора q (этот вектор указывает на направление возрастания линейной функции).
Очевидно, что точка минимума — это точка В “входа” в многоугольник решений, ибо при дальнейшем перемещении линии уровня в направлении вектора q значения линейной функции увеличиваются. Находим координаты точки В(2; 3), при этом Fmin =4*2 6*3 = 26.
Итак, Fmin=26 при оптимальном решении х1=2, x 2= 3, т. е. минимальная стоимость рациона 26 руб. , если в него включить 2 единицы корма I и 3 единицы корма II.
В рассмотренных задачах максимум и минимум линейной функции достигался в одной точке, так что задачи имели единственное оптимальное решение. На практике нередко встречаются задачи, которые этим условиям не удовлетворяют. В подобных случаях геометрический метод также позволяет получить ответ.
Решить геометрически следующие задачи: а) при ограничениях: (I) (III) (IV, V)
Рисунок 5. а
Решение : а) Геометрическое решение задачи показано на рис. 5, а, из которого следует, что линия уровня с максимальным уровнем совпадает с граничной линией АВ многоугольника решений ABCD, т. е. с линией х1 х2 = 8. Следовательно, на всем отрезке АВ линейная функция F=3 x 1 3 х2 принимает одно и то же максимальное значение, равное 3(x 1 х2)=3 • 8 = 24.
Это означает, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптимальных решений два — соответственно в угловых точках A(3; 5) и B(6; 2). Точки отрезка АВ задаются уравнением x 2=8 –x 1, где 3 x 1 6. Итак, Fmin= 24 при бесконечном множестве оптимальных решений х1=с, x 2=8 -c, где 3 с 6.
б) при ограничениях: (I) (III) (IV, V)
Замечание. При геометрическом решении подобных задач важно точно установить, действительно ли совпадает линия уровня с границей многоугольника решений или это связано с неточностью построений, мелким масштабом рисунка и т. п. Ответ на этот вопрос будет положительным, если линия уровня и граничная прямая параллельны, т. е. их коэффициенты при переменных пропорциональны. В рассматриваемом примере коэффициенты при переменных линии уровня F=3 х1 3 x 2 пропорциональны соответствующим коэффициентам граничной прямой x 1 x 2=6.
Решение : б) Геометрическое решение задачи показано на рис. 4. 5, б, из которого следует, что если линию уровня перемещать в направлении убывания линейной функции (т. е. в направлении, противоположном вектору q), то она всегда будет пересекать многоугольник решений, следовательно, линейная функция неограниченно убывает.
5.
Итак, конечного оптимума функции нет, т. е. Fmin=- линейной При геометрическом решении задач линейного программирования возможны случаи, когда условия задач противоречивы, т. е. область допустимых решений системы ограничений представляет пустое множество. Очевидно, в таких задачах нет оптимальных решений и нет смысла строить линию уровня.
Решение задачи линейного программирования в excel
Ранее я писал, что для принятия решений с учетом ограничивающих факторов может использоваться линейное программирование. Напомню, что этот метод решает проблему распределения ограниченных ресурсов между конкурирующими видами деятельности с тем, чтобы максимизировать или минимизировать некоторые численные величины, такие как маржинальная прибыль или расходы.
При решении задач линейного программирования, во-первых, необходимо составить модель, то есть сформулировать условия на математическом языке. После этого решение может быть найдено графически (см., например, здесь), с использованием надстройки Excel «Поиск решения» (рассмотрено в настоящей заметке) или с помощью специализированных компьютерных программ (см., например, здесь).
Рассмотрим линейное программирование в Excel на примере задачи, ранее решенной графическим методом.
Задача. Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно. Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд. На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц. Необходимо определить количество единиц продуктов А и В, которые Николай доложен производить в следующем месяце для максимизации маржинальной прибыли.
Скачать заметку в формате Word, пример в формате Excel
1. Воспользуемся математической моделью построенной в упомянутой заметке. Вот эта модель:
Максимизировать: Z = 2500 * х1 3500 *х2
При условии, что: 3 * х1 10 * х2 ≤ 330
16 * х1 4 * х2 ≤ 400
6 * х1 6 * х2 ≤ 240
х2 ≥ 12
х1 ≥ 0
2. Создадим экранную форму и введем в нее исходные данные (рис. 1).
Рис. 1. Экранная форма для ввода данных задачи линейного программирования
Обратите внимание на формулу в ячейке С7. Это формула целевой функции. Аналогично, в ячейки С16:С18 введены формулы для расчета левой части ограничений.
3. Проверьте, если у вас установлена надстройка «Поиск решения» (рис. 2), пропустите этот пункт.
Рис. 2. Надстройка Поиск решения установлена; вкладка «Данные», группа «Анализ»
Если надстройки «Поиск решения» вы на ленте Excel не обнаружили, щелкните на кнопку Microsoft Office, а затем Параметры Excel (рис. 3).
Рис. 3. Параметры Excel
Выберите строку Надстройки, а затем в самом низу окна «Управление надстройками Microsoft Excel» выберите «Перейти» (рис. 4).
Рис. 4. Надстройки Excel
В окне «Надстройки» установите флажок «Поиск решения» и нажмите Ok (рис. 5). (Если «Поиск решения» отсутствует в списке поля «Надстройки», чтобы найти надстройку, нажмите кнопку Обзор. В случае появления сообщения о том, что надстройка для поиска решения не установлена на компьютере, нажмите кнопку Да, чтобы установить ее.)
Рис. 5. Активация надстройки «Поиск решения»
После загрузки надстройки для поиска решения в группе Анализ на вкладке Данные становится доступна команда Поиск решения (рис. 2).
4. Следующим этапом заполняем окно Excel «Поиск решения» (рис. 6)
Рис. 6. Заполнение окна «Поиск решения»
В поле «Установить целевую ячейку» выбираем ячейку со значением целевой функции – $C$7. Выбираем, максимизировать или минимизировать целевую функцию. В поле «Изменяя ячейки» выбираем ячейки со значениями искомых переменных $C$4:$D$4 (пока в них нули или пусто). В области «Ограничения» с помощью кнопки «Добавить» размещаем все ограничения нашей модели. Жмем «Выполнить». В появившемся окне «Результат поиска решения» выбираем все три типа отчета (рис. 7) и жмем Ok. Эти отчеты нужны для анализа полученного решения. Подробнее о данных, представленных в отчетах, можно почитать здесь.
Рис. 7. Выбор типов отчета
На основном листе появились значения максимизированной целевой функции – 130 000 руб. и изменяемых параметров х1 = 10 и х2 = 30. Таким образом, для максимизации маржинального дохода Николаю в следующем месяце следует произвести 10 единиц продукта А и 30 единиц продукта В.
Если вместо окна «Результат поиска решения» появилось что-то иное, Excel`ю найти решение не удалось. Проверьте правильность заполнения окна «Поиск решения». И еще одна маленькая хитрость. Попробуйте уменьшить точность поиска решения. Для этого в окне «Поиск решения» щелкните на Параметры (рис. 8.) и увеличьте погрешность вычисления, например, до 0,001. Иногда из-за высокой точности Excel не успевает за 100 итераций найти решение. Подробнее о параметрах поиска решения можно почитать здесь.
Рис. 8. Увеличение погрешности вычислений
Решение комбинаторных задач. размещения
Размещения. Формула для числа размещений
1) Размещения с повторениями
Если все элементы 
кортежа 
принадлежат одномуи тому же множеству Х, то говорят о кортеже из элементов множества Х.
Пусть множество Х состоит из n элементов.
Определение.Кортеж длины k, составленный из элементов множества Х, называется размещением с повторениями из n элементов по k (в кортеже его элементы могут повторяться).
Число всех размещений с повторениями из n элементов по k зависит от nи от k (а не от природы множества Х). Это число обозначается 
. Формула для его нахождения выводится с помощью правила произведения:
(1)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр?
Решение.Х = {1, 3, 5, 7, 9}, 
.
Трёхзначное число – это кортеж 
длины 3, составленный из элементов множества X, причем цифры в числе могут повторяться. Значит, этих чисел будет столько, сколько существует размещений с повторениями из 5 элементов по 3:
.
Заметим, что эту задачу можно было решить и с помощью правила произведения, которое работало бы и в том случае, если в условии поменять нечётные цифры на чётные. А вот понятие размещений и формула (1) в этом случае не сработали бы!
Замечание. Если повторения допускаются, то длина кортежа k может быть больше числа элементов множества Х.
2) Размещения без повторений
Пусть множество Х состоит из n элементов.
Определение.Кортеж длины k, в котором все элементы различны, составленный из элементов множества Х, называется размещением без повторений из n элементов по k (в кортеже элементы не повторяются!).
Так как повторения в кортеже не допускаются, то теперьk должно быть не больше n.
Найдём 
– число всех размещений без повторений из n элементов по k.
Для выбора элемента 
имеется n возможностей. После выбора элемента , элемент 
можно выбрать 
-м способом и так далее. Тогда
(2)
Пример. Сколько трёхзначных чисел может быть составлено из нечётных цифр так, чтобы цифры в каждом числе не повторялись?
Решение.Х = {1, 3, 5, 7, 9}, .
Трёхзначное число – это кортеж длины 3 без повторений, составленный из элементов множества X. Значит, этих чисел будет столько, сколько существует размещений без повторений из 5 элементов по 3:
.
Задачи
1. Ф. Из трех стаканов сока – ананасового (а), брусничного (б) и виноградного (в) – Иван решил последовательно выпить два. Перечислить все варианты, которыми это можно сделать.
Решение.
Это задача о выборе двух элементов из трех с учетом порядка выбора. Перечислим эти варианты:
аб, ба, ва,
ав, бв, вб.
Если учащимся известна формула для числа размещений, то количество вариантов равно: А
вариантов.
Ответ: 6 вариантов.
2.Ф. Сколькими способами могут быть заняты первое, второе и третье места (по одному человеку на место) на соревнованиях, в которых участвуют: 1) 5 человек; 2) 6 человек?
Решение.
Это задача о выборе трех элементов из 5 или 6 с учетом порядка выбора.
1)По правилу произведения 5 • 4 • 3 = 60 способов.
2)По правилу произведения 
= 120 способов. Если учащиеся знают формулу для числа размещений, то получаем соответственно:
A
A
Ответ: 1) 60 способов; 2) 120 способов.
М-задачи из уч. пособия А.Г.Мордковича
Т- под ред. С.А.Теляковского
Ф- М.В.Ткачевой
3. Т. Сколькими способами может разместиться семья из трех человек в четырехместном купе, если других пассажиров в купе нет?
Решение.
Пронумеруем места в купе (с № 1 по № 4) и будем «выдавать» каждому из трех членов семьи номер места. Из 4 элементов (номеров мест) будут делаться выборки по 3 элемента, при этом важен не только состав выборки, но и порядок расположения в ней элементов (кто именно и на каком месте поедет). Число способов равно числу размещений из 4 по 3:
Можно рассуждать, непосредственно применяя правило произведения: для первого члена семьи можно выбрать любое из 4 мест, для второго – любое из 3 оставшихся, для третьего – любое из двух оставшихся, всего 
способа рассадить семью в купе.
Ответ: 24 способа.
4. Т. Из 30 участников собрания надо выбрать председателя и секретаря. Сколькими способами это можно сделать?
Решение.
Из 30 элементов выбираем 2, причем порядок выбора имеет значение. Количество способов выбора равно A
= 30 • 29 = 870 способов.
Ответ: 870 способов.
5. Т. Сколькими способами могут занять первое, второе и третье места 8 участниц финального забега на дистанции 100 м?
Решение.
Выбор из 8 по 3 с учетом порядка: A
= 336 способов.
Ответ: 336 способов.
6. Т. На станции 7 запасных путей. Сколькими способами можно расставить на них 4 поезда?
Решение.
Выбираем из 7 запасных путей 4 пути для размещения на них поездов; порядок выбора имеет значение: A
= 
840 способов.
Ответ: 840 способов.
7. Т. Сколькими способами можно изготовить трехцветный флаг с горизонтальными полосами, если имеется материал 7 различных цветов?
Решение.
Выбираем из 7 разноцветных материалов 3 полосы для флага; порядок выбора имеет значение (флаги из трех одинаковых цветов, расположенных в разном порядке, – разные).
A
= 210 способов.
Ответ: 210 способов.
8. Т. На соревнования по легкой атлетике приехала команда из 12 спортсменок. Сколькими способами тренер может определить, кто из них побежит в эстафете 4×100 м на первом, втором, третьем и четвертом этапах?
Решение.
Выбор из 12 по 4 с учетом порядка: A
= 11 880 способов.
Ответ: 11880 способов.
9. М. Сколькими способами могут быть распределены первая, вторая и третья премии между 15 участниками конкурса?
Решение.
Выбираем 3 призеров из 15 участников конкурса с учетом порядка (кому какая премия):
A
= 2 730 способов.
10. Т. Сколькими способами 6 студентов, сдающих эк. замен, могут занять места в аудитории, в которой стоит 20 одноместных столов?
Решение.
Выбираем 6 столов для студентов из 20 имеющихся: порядок выбора учитывается (кто сидит у окна, кто около преподавателя и т. п.):
А
= 27 907 200 способов.
Ответ: 27 907 200 способов.
11. Т. На странице альбома 6 свободных мест для фотографий. Сколькими способами можно вложить в свободные места: а) 2 фотографии; б) 4 фотографии; в) 6 фотографий?
Решение.
а) Выбираем 2 места для фотографий из 6 свободных мест в альбоме: А
= 30 способов.
б) Выбираем 4 места для фотографий из А
= 360 способов.
в) Выбираем 6 мест из 6 (делаем всевозможные перестановки из 6 фотографий):
А
= 6! = 720 способов.
Ответ: а) 30 способов; б) 360 способов; в) 720 способов.
12. М. На плоскости отметили 5 точек. Их надо обозначить латинскими буквами. Сколькими способами это можно сделать (в латинском алфавите 26 букв)?
Решение.
Выбираем 5 букв для обозначения точек из 26 букв в алфавите; порядок выбора имеет значение (какую точку какой буквой обозначим): А
= 7 893 600 способов.
Ответ: 7 893 600 способов.
13. Т. Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1, 3, 5, 7, 9; б) 0, 2, 4,
6,8?
Решение.
а) Выбираем 4 цифры из 5 данных; порядок выбора имеет значение: А
= 120 чисел.
б) Выбираем 4 цифры из 5, но на первое место нельзя выбирать ноль.
Используем метод исключения лишних элементов: если на первое место выбран ноль, то после этого выбираем еще на 3 места цифры из 4 оставшихся, получаем А
= 24 «нулевых» комбинаций, которые недопустимы.
Количество четырехзначных чисел, которые можно составить из данных 5 чисел, равно:
А
= 120 – 24 = 96 чисел.
Можно рассуждать, непосредственно используя правило произведения: первый выбор – 4 варианта, второй выбор – 4 варианта (включая ноль), третий выбор – 3 варианта, четвертый выбор -2 варианта. Всего 4 • 4 • 3 • 2 = 96 чисел.
Ответ: а) 120 чисел; б) 96 чисел.
14. Т. Из трехзначных чисел, записанных с помощью цифр 1, 2, 3, 4, 5, 6, 7, 8, 9 (без повторения цифр), сколько таких, в которых:
а) не встречаются цифры 6 и 7;
б) цифра 8 является последней?
Решение.
а) Выбираем 3 цифры из 7 (без 6 и без 7) с учетом порядка выбора; число вариантов: А
=
= 210 чисел.
б) Фиксируем цифру 8 на последнем месте; на остальные два места перед ней можно выбрать любые 2 цифры из 8 оставшихся ( с учетом порядка выбора). Количество вариантов: А
= 56 чисел.
Ответ: а) 210 чисел; б) 56 чисел.
15. М. Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?
Решение.
Выбираем из 10 цифр семь, причем первый выбор делается из 9 цифр (без нуля). Используя метод исключения лишних вариантов, получаем: А
А
544 320 номеров.
Ответ: 544 320 телефонных номеров.
16. Т. Сколько различных трехзначных чисел (без повторения цифр) можно составить из цифр 1, 2, 3, 4, 5, таких, которые являются: а) четными; б) кратными 5?
Решение.
Выбираем 3 цифры из 5 данных, причем:
а) последней цифрой должна быть 2 или 4; количество вариантов А
(фиксирована 2) А (фиксирована 4) = 
= 24 числа;
б) последней цифрой должна быть 5; количество вариантов равно А (фиксирована 5) = 
= 12 чисел.
Ответ: а) 24 числа; б) 12 чисел.
17. Т. Номер машины в некотором городе состоит из двух различных букв, взятых из набора М, Н, К, Т, С, и трех различных цифр. Сколько машин можно обеспечить такими номерами?
Решение.
Выбираем (без повторений) 2 буквы из 5 и 3 цифры из 10; порядок выбора учитывается (номера 012 КТ и 102 ТК – разные). Количество способов: выбор букв: А
= 20; выбор цифр: А
= 720.
Каждый вариант выбора букв может сочетаться с каждым вариантом выбора цифр, поэтому по правилу произведения общее число способов равно: А
720 = 14 400 способов.
Ответ: 14 400 способов.
18.Т. Сколько команд участвовало в финале первенства, если известно, что каждая команда сыграла с каждой из остальных по одной игре на своем поле и по одной игре на поле соперника, причем всего было сыграно 30 игр?
Решение.
Поскольку каждая пара команд сыграла между собой по две игры (на своем и на чужом поле), то выбор пары осуществляется с учетом порядка, т. е. составляются всевозможные размещения из n по 2. По условию задачи А
n
= 
, n = 6.
Ответ: 6 команд.
19. Т. Из группы туристов требуется выбрать дежурного и его помощника. Если туристов было бы на одного больше, то возможностей выбора было бы в 1,25 раза больше. Сколько туристов в группе?
Решение.
Выбор пары из совокупности с учетом порядка (размещения). По условию задачи: По условию задачи А
(n – 1) , n 1=1,25
; 4(n 1)=5(n-1); n=9
Ответ: 9 туристов.
20. Ф. Сколькими способами четыре пассажира -Алексеев, Смирнов, Федоров и Харитонов – могут разместиться в Девяти вагонах поезда, если:
а) все они хотят ехать в разных вагонах;
б) Алексеев и Смирнов хотят ехать в одном вагоне, а Федоров и Харитонов – в других вагонах, причем различных?
Решение.
Вагоны поезда пронумерованы; осуществляется выбор 4 из 9 вагонов для размещения пассажиров; порядок выбора имеет значение (каждому пассажиру сообщаем номер вагона).
б) Двое едут в одном вагоне, а двое – в других, причем различных. «Склеиваем» два элемента из 4; количество способов размещения равно: А
= 504.
Ответ: а) 3 024 способа; б) 504 способа.
21. Ф. Высказать гипотезу о числе всевозможных разбиений п элементов на 3 группы.
Решение.
Поступим следующим образом. Сопоставим каждому из п элементов свою ячейку, в которую будем записывать номер группы, в которую будет помещен этот элемент. Получим линейку из п ячеек, в каждой из которых может быть записана либо 1, либо 2, либо 3:
n ячеек
Подсчитаем, сколько есть вариантов заполнения этой линейки ячеек.
Первую ячейку можно заполнить одним из трех способов (записать 1, или записать 2, или записать 3). Точно так же можно заполнить вторую, третью и все последующие ячейки до конца линейки.
По комбинаторному правилу произведения общее число способов равно: 
Фактически мы привели уже доказательство гипотезы. Саму гипотезу лучше формулировать на основе перечисления способов разбиения одного, двух, трех элементов на 3 группы:
при п = 1 есть 3 способа, т. е. З1;
при п= 2 есть 9 способов, т. е. 32;
при п=3 есть 27 способов, т. е. З3.
При больших значениях п перечисление сп3особов становится громоздким. Трех рассмотренных случаев будет достаточно, чтобы сделать предположение (выдвинуть гипотезу) о характере наблюдаемой закономерности.
Ответ: 3п способов.
Замечание. Полученная формула – это формула для числа размещений из п элементов по 3 с повторениями: А
= 3п.
Литература
Афанасьев В.В. Теория вероятностей в примерах и задачах, – Ярославль: ЯГПУ , 1994.
Баврин И. И. Высшая математика: Учебник для студентов химико-математических специальностей педагогических вузов-2-е издание, переработанное. – М.:Просвещение, 1993.
Бунимович Е. А., Булычёв В.А. Вероятность и статистика. 5-9 классы: Пособие для общеобразовательных учебных заведений, – М.:Дрофа , 2005.
Виленкин Н. Я. и другие. Алгебра и математический анализ для 10 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики. – М.:Просвещение,1992.
Виленкин Н. Я. и другие. Алгебра и математический анализ для 11 класса: Учебное пособие для учащихся школ и классов с углублённым изучением математики – М.:Просвещение, 1990.
Глейзер Г.И. История математики в школе: 9-10 класс. Пособие для учителей. – М.: Просвещение 1983.
Дорофеев Г.В., Суворова С.Б., Бунимович Е.А. Математика 9:Алгебра. Функции. Анализ данных – М.: Дрофа, 2000.
Колягин и другие. Алгебра и начала анализа 11 класс. Математика в школе – 2002 – №4 – с.43,44,46.
Люпшкас В.С. Факультативные курсы по математике: теория вероятностей: Учебное пособие для 9-11 классов.- М.,1991.
Макарычев Ю.Н., Миндюк Н.Г. Элементы статистики и теории вероятностей: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.
Мордкович А.Г., Семенов П.В. Алгебра и начала анализа 10 класс: Учебник для общеобразовательных учреждений (профильный уровень) – М.: Мнемозина, 2005.
Ткачева М.В., Федорова Н.Е. Элементы статистики и вероятность: Учебное пособие для учащихся 7-9 классов.- М.: Просвещение, 2005.
