Министерство образования и науки Российской Федерации Сибирский федеральный университет
ОСНОВЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ Учебно-методическое пособие по самостоятельной работе для бакалавров по направлению 080200.62«Менеджмент» профиля подготовки 080200.62.00.08 «Управление проектами»
Электронное издание
Красноярск СФУ 2013
УДК 51.77(07) ББК 22.18я73 О 753
Составитель: Бабина Ольга Ивановна О 753 Основы экономико-математического моделирования: учеб.-метод. пособие[Электронный ресурс] / сост. О.И. Бабина. – Электрон. дан. – Красноярск: Сиб. федер. ун-т, 2013. – Систем. требования: PC не ниже класса Pentium I; 128 Mb RAM; Windows 98/XP/7; Adobe Reader V8.0 и выше. – Загл. с экрана. Методические указания содержат основные цели и задачи изучения дисциплины, контрольные вопросы, темы сообщений для самостоятельного изучения, перечень вопросов к экзамену и экзаменационные билеты. Предназначены для бакалавров по направлению 080200.62 «Менеджмент» профиля подготовки 080200.62.00.08 «Управление проектами».
УДК 51.77(07) ББК 22.18я73 © Сибирский федеральный университет, 2013 Учебное издание Подготовлено к публикации Издательским центром БИК СФУ Подписано в свет 22.07.2013 г. Заказ 2811. Тиражируется на машиночитаемых носителях. Издательский центр Библиотечно-издательского комплекса Сибирского федерального университета 660041, г. Красноярск, пр. Свободный, 79 Тел/факс (391)206-21-49. E-mail
[email protected] http://rio.sfu-kras.ru
2
Содержание Введение ................................................................................................................... 4 1. Цель и задачи изучения дисциплины ................................................................ 5 2. Контрольно-измерительные материалы ........................................................... 6 3. Контрольная работа............................................................................................. 6 Контрольная работа № 1 ................................................................................... 6 Контрольная работа № 2 ............................................................................... 177 4. Тестовое задание ............................................................................................... 26 5. Вопросы к зачету ............................................................................................... 40 Список использованных источников .................................................................. 42
3
Введение Математические модели широко используются для описания и операционного анализа задач, возникающих в различных областях целенаправленной человеческой деятельности. Многие экономические ситуации, связанные с вопросами планирования, прогнозирования и управления, также могут быть адекватно описаны в терминах задач математического моделирования. В курсе «Основы экономико-математического моделирования» бакалаврами изучаются вопросы, связанные с методологией математического моделирования и особенностями описания ситуации линейными моделями. Рассматриваются вопросы использования теории двойственности в операционном анализе экономических систем, описаны схемы анализа на чувствительность решения линейной модели при изменении внутренних и внешних условий функционирования экономических систем. Приведены специальные методы решения задач указанных типов.
4
1. Цель и задачи изучения дисциплины Цель преподавания дисциплины Целью изучения дисциплины «Основы экономико-математического моделирования» является формирование у будущих специалистов в области экономики и управления теоретических знаний и практических навыков для решения прикладных экономических задач с целью принятия управленческих решений средствами количественного анализа и экономико-математического моделирования. Задачи изучения дисциплины: – изучение методологических основ использования экономикоматематических моделей экономических систем и систем управления; – изучение основных методов экономико-математического анализа субъектов экономики и построения на их основе моделей; – развитие способностей к проектной деятельности в профессиональной сфере на основе системного подхода, умения строить и использовать экономико-математические модели для описания и прогнозирования различных явлений, осуществлять их качественный и количественный анализ. Требования к результатам освоения дисциплин: Процесс изучения дисциплины «Основы экономико-математического моделирования» направлен на формирование следующих компетенций: ОК-5, ОК-15, ОК-17, ПК-31, ПК-32. В результате изучения дисциплины бакалавр должен: знать: – основы теории решения прикладных экономических задач с целью обоснования и принятия управленческих решений; – основные методы количественного анализа; – основные типы экономико-математических моделей, применяющихся для разработки и принятия управленческих решений; – основные методы подготовки и анализа исходной информации для построения экономико-математических моделей. уметь: – выделять основные взаимосвязи между различными блоками производственно-экономических систем; – проводить расчеты по основным типам экономико-математических моделей; – формализовывать экономические ситуации в виде экономикоматематических моделей; – проводить анализ полученного решения с целью выявления области его устойчивости.
5
владеть: – навыками постановки задачи управления с целью дальнейшей формализации; – методами решения основных типов линейных экономикоматематических моделей; – навыками использования основных программных продуктов в данной области; – основными методами принятия управленческих решений в условиях неопределенности и риска. Межпредметная связь При изучении дисциплины «Основы экономико-математического моделирования» предполагается, что бакалавр владеет основами матричной алгебры, математического анализа, теории вероятностей, экономической теории, экономики и статистики фирмы, основами экономико-математического моделирования, в объеме, предусмотренном Государственным образовательным стандартом. 2. Контрольно-измерительные материалы Контрольно-измерительные материалы, используемые для промежуточного и итогового контроля знаний, умений и навыков в соответствии с реализуемыми компетенциями по дисциплине «Основы экономико-математического моделирования», включают: • контрольные вопросы и задачи; • тестовые задания; • задания для самостоятельной работы (темы сообщений); • вопросы к экзамену. Итоговый контроль по дисциплине «Основы экономико-математического моделирования» осуществляется в виде зачета (7 семестр). Промежуточный контроль знаний осуществляется на основе выполнения и проверки текущих заданий. 3. Контрольная работа Контрольная работа № 1 Билет № 1 1) Экономическая интерпретация основных переменных в задаче о диете и раскрое. 2) Переход от КЗЛП к СЗЛП. 3) Дайте определение целевой функции.
6
4) Составить двойственную задачу по отношению к прямой задаче линейного программирования: F ( X ) = 12 x1 + 15 x 2 → max
⎧6 x1 + 6 x 2 ≤ 36, ⎪4 x +2 x ≤ 20, ⎪ 1 2 ⎨ ⎪4 x1 + 8 x 2 ≤ 40, ⎪⎩ x1 , x 2 ≥ 0.
(1)
5) Для задачи (1) составить симплекс-таблицу, определить переменную входящую в базис на следующей симплекс итерации. Билет № 2 1) Экономическая интерпретация основных переменных в задаче о диете и карамели. 2) Вторая теорема двойственности. 3) Дайте определение критерию оптимальности. 4) Привести ЗЛП к канонической форме: F ( X ) = −2 x1 − x 2 + x3 → min
⎧2 x1 − x 2 + 6 x3 ≤ 12, ⎪3x +5 x − 12 x = 14, ⎪ 1 2 3 ⎨ ⎪− 3 x1 + 6 x 2 + 4 x3 ≤ 18, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(2)
5) Для задачи (2) составить симплекс-таблицу, определить переменную выходящую из базис на следующей симплекс итерации. Билет № 3 1) Экономическая интерпретация основных переменных в задаче о диете и оптимального планирования производства. 2) Третья теорема двойственности. 3) Дайте определение понятию плана. 4) Привести ЗЛП к канонической форме: F ( X ) = −2 x1 + x 2 + 5 x3 → max
⎧− x1 + x 2 + x3 ≥ 4, ⎪2 x − x + x ≤ 16, ⎪ 1 2 3 ⎨ ⎪3 x1 + x 2 + x3 ≥ 18, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(3)
5) Для задачи (3) найти число возможных базисных наборов в методе прямого перебора. Билет № 4 1) Экономическая интерпретация основных переменных в задаче о диете и оптимального планирования производства. 2) Основная теорема двойственности. 7
3) Дайте определение допустимого плана ЗЛП. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = 4 x1 − 2 x 2 + x3 − x 4 → max
⎧ x1 − x 2 + 4 x3 − 2 x 4 ≤ 4, ⎪ ⎨3 x 1 +2 x 2 − x3 + 4 x 4 ≤ 3, ⎪ x , x , x , x ≥ 0. ⎩ 1 2 3 4
(4)
5) Для задачи (4) составить симплекс-таблицу, определить переменную входящую в базис на следующей симплекс итерации. Билет № 5 1) Экономическая интерпретация основных переменных в задаче о раскрое и оптимального планирования производства. 2) Переход от СЗЛП к КЗЛП. 3) Дайте определение оптимального плана ЗЛП. 4) Привести ЗЛП к стандартной форме: F ( X ) = −2 x1 − x 2 + x3 → min
⎧2 x1 − x 2 + 6 x3 ≤ 12, ⎪3 x +5 x − 12 x = 14, ⎪ 1 2 3 ⎨ ⎪− 3 x1 + 6 x 2 + 4 x3 ≤ 18, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(5)
5) Для задачи (5) составить симплекс-таблицу, определить переменные входящую в базис и выходящую из базиса на следующей симплекс итерации. Билет № 6 1) Экономическая интерпретация основных переменных в задаче о раскрое и карамели. 2) Важность двойственной ЗЛП. 3) Дайте определение опорного плана ЗЛП. 4) Привести ЗЛП к канонической форме: F ( X ) = 2 x1 − 5 x 2 − 3 x3 → min
⎧4 x1 + 2 x 2 + 5 x3 ≤ 12, ⎪6 x −3 x + 4 x = 18, ⎪ 1 2 3 ⎨ 3 3 2 ⎪ x1 + x 2 − x3 ≥ 16, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(6)
5) Для задачи (6) найти число возможных базисных наборов в методе прямого перебора. Билет № 7 1) Экономическая интерпретация основных переменных в задаче о раскрое и о диете. 8
2) Принцип оптимальности Канторовича. 3) Что понимается под системой ограничений в ЗЛП. 4) Привести ЗЛП к стандартной форме: F ( X ) = 2 x1 − 5 x 2 − 3 x3 → min
⎧4 x1 + 2 x 2 + 5 x3 ≤ 12, ⎪6 x −3 x + 4 x = 18, ⎪ 1 2 3 ⎨ ⎪3 x1 + 3 x 2 − 2 x3 ≥ 16, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(7)
5) Для задачи (7) составить симплекс-таблицу, определить переменную входящую в базис на следующей симплекс итерации. Билет № 8 1) Экономическая интерпретация основных переменных в задаче о раскрое и оптимального планирования производства. 2) Критерий оптимальности по методу Гаусса. 3) Дайте определение ОДР. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = x1 + 2 x 2 → max
⎧2 x1 + 3 x 2 ≤ 6, ⎪2 x +2 x ≤ 4, 2 ⎪⎪ 1 ⎨ x1 ≤ 1, ⎪− x + x ≤ 1, 2 ⎪ 1 ⎪⎩ x1 , x 2 ≥ 0.
(8)
5) Для задачи (8) найти число возможных базисных наборов в методе прямого перебора. Билет № 9 1) Экономическая интерпретация основных переменных в задаче о карамели и оптимального планирования производства. 2) Основная идея симплексного метода. 3) Дайте определение линии уровня. 4) Привести ЗЛП к стандартной форме: F ( X ) = x1 + 2 x 2 → min
⎧2 x1 + 3 x 2 ≤ 6, ⎪2 x +2 x ≤ 4, 2 ⎪⎪ 1 ≤ x 1 , ⎨ 1 ⎪− x + x ≤ 1, 2 ⎪ 1 ⎪⎩ x1 , x 2 ≥ 0.
(9)
5) Для задачи (9) составить симплекс-таблицу, определить переменные входящую в базис и переменную, выходящую из базиса на следующей 9
симплекс итерации. Билет № 10 1) Экономическая интерпретация основных переменных в задаче о диете и оптимального планирования производства. 2) Основная теорема двойственности. 3) Дайте определение градиенту. 4) Построить область допустимых решений для ЗЛП: F ( X ) = 2 x1 + x 2 → max
⎧ x1 − x 2 ≤ 10, ⎪ ⎨2 x1 ≤ 40, ⎪ x , x ≥ 0. ⎩ 1 2
(10)
5) Для задачи (10) найти число возможных базисных наборов в методе прямого перебора. Билет № 11 1) Экономическая интерпретация дополнительных переменных в задаче о диете и раскрое. 2) Критерий нежесткости в третьей теореме двойственности. 3) Координаты градиента. 4) Привести ЗЛП к канонической форме: F ( X ) = −3 x1 − 5 x 2 − 6 x3 → min
⎧2 x1 + 5 x 2 − 7 x3 ≤ 12, ⎪− 4 x +3 x + 8 x ≥ 15, ⎪ 1 2 3 ⎨ x x x 3 2 10 − + 2 3 ≤ 17, ⎪ 1 ⎪⎩ x1 , x 2 , x3 ≥ 0.
(11)
5) Для задачи (11) составить симплекс-таблицу, определить переменную, выходящую из базиса на следующей итерации. Билет № 12 1) Экономическая интерпретация дополнительных переменных в задаче о диете и оптимального планирования производства. 2) Переход от СЗЛП к КЗЛП. 3) Алгоритм решения ЗЛП графическим методом. 4) Построить область допустимых решений для ЗЛП: F ( X ) = 3 x1 + 2 x 2 → max
⎧ x1 + 2 x 2 ≤ 6, ⎪2 x + x ≤ 8, ⎪⎪ 1 2 ⎨− x1 + x 2 ≤ 1, ⎪ x ≤ 2, ⎪ 2 ⎩⎪ x1 , x 2 ≥ 0.
(12)
10
5) Для задачи (12) найти число возможных базисных наборов в методе прямого перебора. Билет № 13 1) Экономическая интерпретация дополнительных переменных в задаче о диете и назначениях. 2) Решение ЗЛП методом прямого перебора (определение базисных наборов). Принцип определения оптимального плана. 3) Дайте определение целевой функции. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = 3 x1 − 2 x 2 − 7 x3 + x5 → max
⎧ x1 + x 2 − x5 ≤ 40, ⎪2 x −2 x + x ≤ 28, ⎪ 1 2 3 ⎨ ⎪ x 2 − 3 x3 − x 4 + 2 x5 ≤ 18, ⎪⎩ x1 , ..., x5 ≥ 0.
(13)
5) Для задачи (13) составить симплекс-таблицу. Билет № 14 1) Экономическая интерпретация дополнительных переменных в задаче о диете и оптимального планирования производства. 2) Алгоритм решения ЗЛП методом прямого перебора. 3) Дайте определение градиенту. 4) Привести ЗЛП к стандартной форме: F ( X ) = −7 x1 − 2 x 2 → min
⎧2 x1 + 3 x 2 ≥ 6, ⎪2 x +2 x ≤ 4, 2 ⎪⎪ 1 ⎨ x1 ≤ 1, ⎪− x + x ≤ 1, 2 ⎪ 1 ⎪⎩ x1 , x 2 ≥ 0.
(14)
5) Для задачи (14) составить симплекс-таблицу, определить переменную входящую в базис на следующей симплекс итерации. Билет № 15 1) Экономическая интерпретация дополнительных переменных в задаче о раскрое и оптимального планирования производства. 2) Определения целевой функции и её графическое изображение. 3) Формула для нахождения числа возможных вариантов базисных наборов в методе прямого перебора.
11
4) Построить область допустимых решений для ЗЛП: F ( X ) = 3 x1 + 2 x 2 → max
⎧2 x1 + x 2 ≤ 2, ⎪3 x +4 x ≤ 12, ⎪ 1 2 ⎨ ⎪ x1 ≥ 2, ⎪⎩ x1 , x 2 ≥ 0.
(15)
5) Для задачи (15) найти число возможных базисных наборов в методе прямого перебора. Билет № 16 1) Экономическая интерпретация дополнительных переменных в задаче о раскрое и карамели. 2) Основная идея графического метода. 3) Нахождение оптимального плана ЗЛП в методе прямого перебора. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = 3 x1 − 2 x3 + 2 x 4 → max
⎧2 x1 + 2 x 2 + x3 + 3 x 4 ≤ 20, ⎪− x − x + 4 x + 2 x ≤ 45, ⎪ 1 2 3 4 ⎨ ⎪2 x1 − 2 x 2 + 2 x3 − x 4 ≤ 35, ⎪⎩ x1 , ..., x 4 ≥ 0.
(16)
5) Для задачи (16) составить симплекс-таблицу. Билет № 17 1) Экономическая интерпретация дополнительных переменных в задаче о раскрое и оптимального планирования производства. 2) Основная идея анализа на чувствительность. 3) Прямая задача линейного программирования. 4) Привести ЗЛП к стандартной форме: F ( X ) = x1 + 2 x 2 − 3 x3 → max
⎧2 x1 + 3 x 2 + 4 x3 ≤ 6, ⎪2 x +2 x ≥ 4, ⎪ 1 2 ⎨ ⎪ x1 = 1, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(17)
5) Для задачи (17) составить симплекс-таблицу, определить переменные входящую в базис и переменную, выходящую из базиса на следующей симплекс итерации. Билет № 18 1) Экономическая интерпретация дополнительных переменных в задаче о карамели и раскрое. 2) Определение дефицитного ресурса и его графическое изображение. 12
3) Двойственная задача линейного программирования. 4) Построить область допустимых решений для ЗЛП: F ( X ) = 6 x1 − 2 x 2 → max
⎧2 x1 − x 2 ≤ 2, ⎪ ⎨ x1 ≤ 4, ⎪ x , x ≥ 0. ⎩ 1 2
(18)
5) Для задачи (18) составить симплекс-таблицу, определить переменную выходящую из базиса на следующей итерации. Билет № 19 1) Экономическая интерпретация дополнительных переменных в задаче о диете и оптимального планирования производства. 2) Определение недефицитного ресурса и его графическое изображение. 3) Алгоритм решения ЗЛП методом прямого перебора. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = x1 + 2 x 2 − 3 x3 + 5 x 4 → max
⎧ x1 + x 2 + 2 x3 + 2 x 4 ≤ 40, ⎪− x −4 x + 2 x + 3 x ≤ 25, ⎪ 1 2 3 4 ⎨ ⎪ x1 − x 2 + 2 x3 − x 4 ≤ 30, ⎪⎩ x1 , ..., x 4 ≥ 0.
(19)
5) Для задачи (19) найти число возможных базисных наборов в методе прямого перебора. Билет № 20 1) Экономическая интерпретация дополнительных переменных в задаче о раскрое и оптимального планирования производства. 2) Определение избыточного ресурса и его графическое изображение. 3) Алгоритм решения ЗЛП графическим методом. 4) Привести ЗЛП к стандартной форме: F ( X ) = x1 − 2 x 2 − x3 → min
⎧2 x1 − 3 x 2 + 3 x3 ≤ 6, ⎪2 x +2 x ≥ 4, ⎪ 1 2 ⎨ x x 2 + 7 x3 ≤ 10, 2 − + 1 ⎪ ⎪⎩ x1 , x 2 , x 3 ≥ 0.
(20)
5) Для задачи (20) составить симплекс-таблицу. Билет № 21 1) Экономическая интерпретация коэффициентов целевой функции в задаче о диете и раскрое. 2) Основные вопросы, решаемые в третьей задаче анализа на чувствительность. 13
3) Переход от СЗЛП к КЗЛП. 4) Построить область допустимых решений для ЗЛП: F ( X ) = x1 + 2 x 2 → max
⎧ x1 + 2 x 2 ≥ 6, ⎪2 x + x ≤ 20, ⎪ 1 2 ⎨ ⎪ x1 ≤ 16, ⎪⎩ x1 , x 2 ≥ 0.
(21)
5) Для задачи (21) составить симплекс-таблицу, определить переменную входящую в базис на следующей итерации. Билет № 22 1) Экономическая интерпретация коэффициентов целевой функции в задаче о диете и карамели. 2) Участки, на которых может находиться точка оптимума. 3) Основная идея симплекс метода. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = 8 x 2 + 7 x 4 − x6 → max
⎧ x1 − 2 x 2 − 3 x 4 − 2 x 6 ≤ 12, ⎪4 x + x − 4 x − 3 x ≤ 12, ⎪ 2 3 4 6 ⎨ ⎪5 x 2 + 5 x 4 + x6 ≤ 25, ⎪⎩ x1 , ..., x6 ≥ 0.
(22)
5) Для задачи (22) составить симплекс-таблицу, определить переменную выходящую из базиса на следующей итерации. Билет № 23 1) Экономическая интерпретация коэффициентов целевой функции в задаче о диете и карамели. 2) Определение точки оптимума. 3) Основные вопросы, решаемые второй задачей анализа на чувствительность. 4) Построить область допустимых решений для ЗЛП: F ( X ) = x1 + x 2 → max
⎧ x1 + 2 x 2 ≤ 16, ⎪ x + x ≥ 2, ⎪ 1 2 ⎨ ⎪ x 2 ≤ 2, ⎪⎩ x1 , x 2 ≥ 0.
(23)
5) Для задачи (23) найти число возможных базисных наборов в методе прямого перебора.
14
Билет № 24 1) Экономическая интерпретация коэффициентов целевой функции в задаче о диете и оптимального планирования производства. 2) Основная теорема двойственности. 3) Основные вопросы, решаемые третьей задачей анализа на чувствительность. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = x1 + 3 x 2 → max
⎧ x1 − x 2 ≤ 1, ⎪2 x + x ≤ 2, ⎪ 1 2 ⎨ ⎪5 x1 + 2 x 2 ≤ 10, ⎪⎩ x1 , x 2 ≥ 0.
(24)
5) Для задачи (24) составить симплекс-таблицу. Билет № 25 1) Экономическая интерпретация коэффициентов целевой функции в задаче о раскрое и оптимального планирования производства. 2) Леммы теории двойственности. 3) Основные вопросы, решаемые первой задачей анализа на чувствительность. 4) Привести ЗЛП к канонической форме: F ( X ) = −2 x1 − 4 x 2 + 5 x3 → min
⎧2 x1 − x 2 + 6 x3 ≥ 12, ⎪3 x +5 x = 14, ⎪ 1 2 ⎨ ⎪− 3 x1 + 6 x 2 + 4 x3 ≤ 18, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(25)
5) Для задачи (25) составить симплекс-таблицу, определить переменную входящую в базис на следующей симплекс итерации. Билет № 26 1) Экономическая интерпретация коэффициентов целевой функции в задаче о раскрое и диете. 2) Определение двойственной задачи. 3) Переход от ПЗЛП к ДЗЛП. 4) Построить область допустимых решений для ЗЛП: F ( X ) = 15 x1 + 30 x 2 → max
⎧12 x1 + 2 x 2 ≤ 200, ⎪4 x +4 x ≤ 80, ⎪ 1 2 ⎨ ⎪3 x1 + 12 x 2 ≤ 120, ⎪⎩ x1 , x 2 ≥ 0.
15
(26)
5) Для задачи (26) найти число возможных базисных наборов в методе прямого перебора. Билет № 27 1) Экономическая интерпретация коэффициентов целевой функции в задаче о раскрое и о карамели. 2) Формы записи ЗЛП. 3) Преимущества и недостатки графического метода. 4) Построить область допустимых решений для ЗЛП: F ( X ) = x1 + x 2 → max
⎧2 x1 + 4 x 2 ≤ 16, ⎪− 4 x +2 x ≤ 8, ⎪ 1 2 ⎨ ⎪ x1 + 3 x 2 ≥ 9, ⎪⎩ x1 , x 2 ≥ 0.
(27)
5) Для задачи (27) составить симплекс-таблицу. Билет № 28 1) Экономическая интерпретация коэффициентов целевой функции в задаче о карамели и диете. 2) Основные вопросы, решаемые первым анализом на чувствительность. 3) В чем состоит геометрическая интерпретация симплекс-метода? 4) Привести ЗЛП к канонической форме: F ( X ) = −2 x1 − x 2 → min
⎧2 x1 − x 2 ≤ 12, ⎪3 x = 14, ⎪ 1 ⎨ ⎪− 3 x1 + 6 x 2 ≤ 18, ⎪⎩ x1 , x 2 ≥ 0.
(28)
5) Для задачи (28) найти число возможных базисных наборов в методе прямого перебора. Билет № 29 1) Экономическая интерпретация коэффициентов целевой функции в задаче о карамели и оптимального планирования производства. 2) Основные методы оптимизации ЗЛП. 3) Экономическая интерпретация объективно-обусловленных оценок. 4) Построить область допустимых решений для ЗЛП: F ( X ) = 2 x1 + 3 x 2 → max
⎧2 x1 + x 2 ≤ 10, ⎪− 2 x +3 x ≤ 6, ⎪ 1 2 ⎨ ⎪2 x1 + 4 x 2 ≥ 8, ⎪⎩ x1 , x 2 ≥ 0.
16
(29)
5) Для задачи (29) составить симплекс-таблицу, определить переменную выходящую из базиса на следующей симплекс итерации. Билет № 30 1) Экономическая интерпретация коэффициентов целевой функции в задаче о диете и оптимального планирования производства. 2) Виды решений графическим методом. 3) Критерий оптимальности Канторовича. 4) Составить двойственную задачу по отношению к прямой задачи линейного программирования: F ( X ) = 2 x1 + x 2 + 3 x3 → max
⎧− x1 + 3 x 2 − 5 x3 = 12, ⎪2 x − x + 4 x = 24, ⎪ 1 2 3 ⎨ ⎪3 x1 + x 2 + x3 = 18, ⎪⎩ x1 , x 2 , x3 ≥ 0.
(30)
5) Для задачи (30) найти число возможных базисных наборов в методе прямого перебора. Контрольная работа № 2 Билет № 1 1) Общая постановка транспортной задачи. 2) Примеры построения циклов в транспортной задаче. 3) Решить задачу о назначениях: ⎛4 6 8⎞ ⎜ ⎟ ⎜13 9 11 ⎟ ⎜14 12 15 ⎟ ⎝ ⎠
4) Привести транспортную модель к закрытому типу. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 50, A2 =10, A3 = 60 B1 = 60, B2 = 60, B3 = 50
⎛ 2 3 2⎞ ⎟ ⎜ C ij = ⎜ 2 4 5 ⎟ ⎜6 5 7⎟ ⎠ ⎝
Билет № 2 1) Общая постановка задачи о назначениях. 2) Определение опорного плана транспортной задачи методом северозападного угла. 17
3) Решить задачу о назначениях: ⎛3 5 7⎞ ⎜ ⎟ ⎜12 8 10 ⎟ ⎜13 11 14 ⎟ ⎝ ⎠
4) Построить транспортную модель задачи. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 50, A2 = 70, A3 = 60 B1 = 60, B2 = 60, B3 = 50 ⎛ 2 3 2⎞ ⎟ ⎜ C ij = ⎜ 2 4 5 ⎟ ⎜6 5 7⎟ ⎠ ⎝
Билет № 3 1) Математическая модель транспортной задачи. 2) Определение оптимального плана транспортной задачи. 3) Решить задачу о назначениях: ⎛1 ⎜ ⎜9 ⎜4 ⎜ ⎜8 ⎝
4 6 3⎞ ⎟ 7 10 9 ⎟ 5 11 7 ⎟ ⎟ 7 8 5 ⎟⎠
4) Привести транспортную модель к закрытому типу. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 200, A2 = 300, A3 = 50, B1 = 150, B2 = 250, B3 = 100, B4 = 100 ⎛6 4 4 5⎞ ⎜ ⎟ C ij = ⎜ 6 9 5 8 ⎟ ⎜ 8 2 10 6 ⎟ ⎝ ⎠
Билет № 4 1) Математическая модель задачи о назначениях. 2) Определение потенциалов пунктов назначения и отправления и их экономический смысл.
18
3) Решить задачу о назначениях: ⎛3 ⎜ ⎜4 ⎜4 ⎜ ⎜3 ⎜1 ⎝
4 2 2 1⎞ ⎟ 5 3 1 3⎟ 3 1 1 1⎟ ⎟ 1 2 2 2⎟ 3 1 2 1 ⎟⎠
4) Построить транспортную модель задачи. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 200, A2 = 300, A3 =100 B1 =150, B2 = 250, B3 =100, B4 = 100 ⎛ 6 4 4 5⎞ ⎜ ⎟ C ij = ⎜ 6 9 5 8 ⎟ ⎜ 8 2 10 6 ⎟ ⎝ ⎠
Билет № 5 1) Экономический смысл дополнительных переменных в транспортной задаче. 2) Алгоритм решения задачи о назначениях венгерским методом. 3) Составить математическую модель задачи о назначениях: ⎛1 ⎜ ⎜1 ⎜8 ⎜ ⎜3 ⎝
2 4 5 5
7 6 7 8
5⎞ ⎟ 7⎟ 8⎟ ⎟ 7 ⎟⎠
4) Привести транспортную модель к закрытому типу. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 18, A2 = 10, A3 = 20 B1 = 25, B2 = 8, B3 = 13 ⎛ 4 1 5⎞ ⎜ ⎟ C ij = ⎜ 2 3 6 ⎟ ⎜ 5 7 4⎟ ⎝ ⎠
Билет № 6 1) Экономическая интерпретация дополнительных переменных в задаче о назначениях. 2) Определение фиктивного пункта назначения.
19
3) Решить задачу о назначениях: ⎛ 68 ⎜ ⎜ 56 ⎜ 38 ⎜ ⎜ 47 ⎝
72 60 40 42
75 58 35 40
83 ⎞ ⎟ 63 ⎟ 45 ⎟ ⎟ 45 ⎟⎠
4) Построить транспортную модель задачи. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 18, A2 = 10, A3 = 20 B1 = 25, B2 = 10, B3 =13 ⎛ 4 1 5⎞ ⎜ ⎟ C ij = ⎜ 2 3 6 ⎟ ⎜ 5 7 4⎟ ⎝ ⎠
.
Билет № 7 1) Экономическая интерпретация основных переменных в задаче о назначениях. 2) Определение невырожденного плана транспортной задачи. 3) Решить задачу о назначениях: ⎛2 ⎜ ⎜1 ⎜7 ⎜ ⎜9 ⎜3 ⎝
4 6 8 3⎞ ⎟ 3 2 7 6⎟ 2 4 5 8⎟ ⎟ 1 3 4 6⎟ 2 1 4 5 ⎟⎠
4) Построить транспортную модель задачи. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 20, A2 = 40, A3 = 30 B1 = 30, B2 = 40, B3 = 20 ⎛7 5 3⎞ ⎜ ⎟ C ij = ⎜ 4 6 1 ⎟ ⎜ 3 2 4⎟ ⎝ ⎠
Билет № 8 1) Экономическая интерпретация основных переменных в транспортной задаче. 2) Алгоритм решения целочисленной задачи методом Гомори.
20
3) Решить задачу о назначениях. ⎛ 6 8 10 ⎞ ⎜ ⎟ ⎜15 11 13 ⎟ ⎜16 14 17 ⎟ ⎝ ⎠
4) Построить транспортную модель задачи. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 40, A2 = 50, A3 = 60, A4 = 30, B1 = 60, B2 = 80, B3 = 40 ⎛4 ⎜ ⎜6 C ij = ⎜ 7 ⎜ ⎜5 ⎝
3 5⎞ ⎟ 2 1⎟ 4 2⎟ ⎟ 6 3 ⎟⎠
Билет № 9 1) Экономическая интерпретация коэффициентов целевой функции в задаче о назначениях. 2) Метод Гомори. 3) Решить задачу о назначениях: ⎛9 ⎜ ⎜4 ⎜7 ⎜ ⎜8 ⎝
8 6 2 3
9 3 1 5
7⎞ ⎟ 2⎟ 4⎟ ⎟ 6 ⎟⎠
4) Привести транспортную модель к закрытому типу. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 20, A2 = 40, A3 = 30 B1 = 30, B2 = 30, B3 = 20 ⎛7 5 3⎞ ⎜ ⎟ C ij = ⎜ 4 6 1 ⎟ ⎜ 3 2 4⎟ ⎝ ⎠
Билет № 10 1) Экономическая интерпретация коэффициентов целевой функции в транспортной задаче. 2) Венгерский метод.
21
3) Составить математическую модель задачи о назначениях: ⎛4 6 8⎞ ⎜ ⎟ ⎜13 9 11 ⎟ ⎜14 12 15 ⎟ ⎝ ⎠
4) Привести транспортную модель к закрытому типу. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 40, A2 = 50, A3 = 60, A4 = 30, B1 = 60, B2 = 80, B3 = 30 ⎛4 ⎜ ⎜6 C ij = ⎜ 7 ⎜ ⎜5 ⎝
3 5⎞ ⎟ 2 1⎟ 4 2⎟ ⎟ 6 3 ⎟⎠
Билет № 11 1) Определение плана транспортной задачи. 2) Математическая модель целочисленной задачи. 3) Решить задачу о назначениях. ⎛5 7 9⎞ ⎜ ⎟ ⎜14 10 12 ⎟ ⎜15 13 16 ⎟ ⎝ ⎠
4) Найти опорный план методом минимальной стоимости. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 40, A2 = 50, A3 = 60, A4 = 30, B1 = 60, B2 = 80, B3 = 30 ⎛4 ⎜ ⎜6 C ij = ⎜ 7 ⎜ ⎜5 ⎝
3 5⎞ ⎟ 2 1⎟ 4 2⎟ ⎟ 6 3 ⎟⎠
Билет № 12 1) Определение плана задачи о назначениях. 2) Алгоритм решения транспортной задачи методом потенциалов. 3) Составить математическую модель задачи о назначениях: ⎛5 1 7⎞ ⎜ ⎟ ⎜ 3 4 3⎟ ⎜ 4 1 3⎟ ⎝ ⎠
22
4) Найти опорный план методом северо-западного угла. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 =18, A2 =10, A3 = 20 B1 = 25, B2 = 8, B3 =13 ⎛ 4 1 5⎞ ⎜ ⎟ C ij = ⎜ 2 3 6 ⎟ ⎜ 5 7 4⎟ ⎝ ⎠
Билет № 13 1) Определение допустимого плана транспортной задачи. 2) Схожесть симплекс-метода и методов решения транспортной задачи. 3) Решить задачу о назначениях: ⎛3 8 ⎜ ⎜8 7 ⎜6 4 ⎜ ⎜8 4 ⎜ 9 10 ⎝
2 10 2
9
2 2
7 3
6
9
3⎞ ⎟ 7⎟ 5⎟ ⎟ 5⎟ 10 ⎟⎠
4) Привести транспортную модель к закрытому типу и найти опорный план методом минимальной стоимости. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 20, A2 = 40, A3 = 30 B1 = 30, B2 = 30, B3 = 20 ⎛7 5 3⎞ ⎜ ⎟ C ij = ⎜ 4 6 1 ⎟ ⎜ 3 2 4⎟ ⎝ ⎠
Билет № 14 1) Определение закрытой транспортной задачи. 2) Условие оптимальности в транспортной задаче по распределительному методу. 3) Решить задачу о назначениях: ⎛ 7 9 11 ⎞ ⎜ ⎟ ⎜16 12 14 ⎟ ⎜17 15 18 ⎟ ⎝ ⎠
4) Найти опорный план методом минимальной стоимости. Обозначения: 23
– запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. Ai
A1 = 50, A2 = 10, A3 = 60 B1 = 60, B2 = 60, B3 = 50 ⎛ 2 3 2⎞ ⎜ ⎟ C ij = ⎜ 2 4 5 ⎟ ⎜6 5 7⎟ ⎝ ⎠
Билет № 15 1) Сдвиг по циклу пересчета. 2) Определение оптимального плана транспортной задачи методом потенциалов. 3) Решить задачу о назначениях: ⎛ 8 10 12 ⎞ ⎜ ⎟ ⎜17 13 15 ⎟ ⎜18 16 19 ⎟ ⎝ ⎠
4) Найти опорный план методом северо-западного угла. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 200, A2 = 300, A3 = 50, B1 =150, B2 = 250, B3 =100, B4 =100 ⎛6 4 4 5⎞ ⎜ ⎟ C ij = ⎜ 6 9 5 8 ⎟ ⎜ 8 2 10 6 ⎟ ⎝ ⎠
Билет № 16 1) Определение открытой транспортной задачи. 2) Определение оптимального плана распределительным методом. 3) Решить задачу о назначениях: ⎛3 ⎜ ⎜6 ⎜9 ⎜ ⎜2 ⎜9 ⎝
транспортной
задачи
7⎞ ⎟ 6⎟ 4 7 10 3 ⎟ ⎟ 5 4 2 1⎟ 6 2 4 6 ⎟⎠
9 2 1 5
3 6
4) Найти опорный план методом минимальной стоимости. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт 24
назначения. A1 = 200, A2 = 300, A3 = 50, B1 =150, B2 = 250, B3 =100, B4 =100 ⎛6 4 4 5⎞ ⎜ ⎟ C ij = ⎜ 6 9 5 8 ⎟ ⎜ 8 2 10 6 ⎟ ⎝ ⎠
Билет № 17 1) Необходимое условие разрешимости транспортной задачи. 2) Алгоритм решения транспортной задачи распределительным методом. 3) Составить математическую модель задачи о назначениях: ⎛ 7 9 11 ⎞ ⎜ ⎟ ⎜16 12 14 ⎟ ⎜17 15 18 ⎟ ⎝ ⎠
4) Найти опорный план методом северо-западного угла. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 40, A2 = 50, A3 = 60, A4 = 30, B1 = 60, B2 = 80, B3 = 30 ⎛4 ⎜ ⎜6 C ij = ⎜ 7 ⎜ ⎜5 ⎝
3 5⎞ ⎟ 2 1⎟ 4 2⎟ ⎟ 6 3 ⎟⎠
Билет № 18 1) Определение фиктивного пункта отправления. 2) Условие оптимальности в транспортной задаче по методу потенциалов. 3) Составить математическую модель задачи о назначениях: ⎛5 7 9⎞ ⎜ ⎟ ⎜14 10 12 ⎟ ⎜15 13 16 ⎟ ⎝ ⎠
4) Найти опорный план методом минимальной стоимости. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 =18, A2 =10, A3 = 20 B1 = 25, B2 = 8, B3 =13 ⎛ 4 1 5⎞ ⎜ ⎟ C ij = ⎜ 2 3 6 ⎟ ⎜ 5 7 4⎟ ⎝ ⎠ 25
Билет № 19 1) Методы нахождения опорного и оптимального планов транспортной задачи. 2) Определение цикла. 3) Составить математическую модель задачи о назначениях: ⎛ 4 1⎞ ⎜⎜ ⎟⎟ ⎝ 5 3⎠
4) Найти опорный план методом северо-западного угла. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 20, A2 = 40, A3 = 30 B1 = 30, B2 = 30, B3 = 20 ⎛7 5 3⎞ ⎜ ⎟ C ij = ⎜ 4 6 1 ⎟ ⎜ 3 2 4⎟ ⎝ ⎠
Билет № 20 1) Определение опорного плана транспортной задачи минимальной стоимости. 2) Чему равно число переменных транспортной задачи? 3) Составить математическую модель задачи о назначениях: ⎛ 8 10 12 ⎞ ⎜ ⎟ ⎜17 13 15 ⎟ ⎜18 16 19 ⎟ ⎝ ⎠
4) Найти опорный план методом северо-западного угла. Обозначения: Ai – запасы в i-м пункте отправления; B j – запасы в j -м пункте назначения; Cij – тарифы перевозок из i-го пункта отправления в j -м пункт назначения. A1 = 50, A2 = 10, A3 = 60 B1 = 60, B2 = 60, B3 = 50 ⎛ 2 3 2⎞ ⎜ ⎟ C ij = ⎜ 2 4 5 ⎟ ⎜6 5 7⎟ ⎝ ⎠
4. Тестовое задание 1. Условный образ объекта (в качестве которого могут выступать системы или понятия), формирующий представление о нем в некоторой форме, отличной от реального существования данного объекта – это 26
а) б) в) г)
Модель; Целевая функция; Система ограничений; Градиент.
Верно (В) или неверно (Н) 2. Отличительным признаком оптимизационной модели является наличие одного или нескольких критериев оптимальности 3. Критерий оптимальности – это признак, по которому множество или одно решение задачи признается а) Наилучшим; б) Наихудшим; в) Несвязанным; г) Связанным. Верно (В) или неверно (Н) 4. Изменения уровня запаса дефицитного ресурса всегда влияют на оптимальные значения, как целевой функции, так и переменных. Верно (В) или неверно (Н) 5. Этапы исследования операций: 1. Идентификация проблемы; 2. Построение модели; 3. Решение поставленной задачи с помощью модели; 4. Проверка адекватности модели; 5. Реализация результатов исследования. Верно (В) или неверно (Н) 6. Оптимальное решение задачи линейного программирования, если оно конечно, можно всегда найти, зная все угловые точки пространства решений. Верно (В) или неверно (Н) 7. Изменения коэффициентов целевой функции могут изменить статус ресурсов (т.е. дефицитный ресурс может стать недефицитным, и наоборот). 8. а) б) в) г)
Область допустимых решений может представлять собой: Выпуклый пятиугольник; Выпуклый многоугольник; Выпуклый треугольник; Выпуклый четырехугольник.
27
9. Геометрическое место принимает одно и то же значение а) Градиент; б) Линия уровня; в) Оптимальный план; г) Допустимый план.
точек,
в
которых
целевая
функция
Верно (В) или неверно (Н) 10. Анализ моделей на чувствительность – это процесс, реализуемый после того, как оптимальное решение задачи получено. 11. Ограничение, которое не участвует в формировании пространства допустимых решений, называется а) Дефицитным; б) Недефицитным; в) Избыточным. Верно (В) или неверно (Н) 12. Оптимальное решение задачи линейного программирования можно изменить, исключая несвязывающие ограничения. 13. Ресурс, с которым ассоциировано несвязывающее ограничение называется а) Дефицитный; б) Недефицитный; в) Избыточный. 14. Допустимый план, при котором целевая функция задачи линейного программирования принимает свое максимальное значение, называется _______________. 15. а) б) в) г)
Вектор, показывающий направление возрастания целевой функции Допустимый план; Линия уровня; Градиент; Допустимый план.
Верно (В) или неверно (Н) 16. Область допустимых решений системы неравенств может быть пустой, одной точкой, выпуклым многоугольником или неограниченной выпуклой многоугольной областью. Верно (В) или неверно (Н) 28
17. Пространство допустимых решений задачи линейного программирования можно изменить, исключая избыточное ограничение. Верно (В) или неверно (Н) 18. Пространство допустимых решений задачи линейного программирования можно изменить, исключая несвязывающие ограничения. 19. а) б) в)
Вторая задача анализа на чувствительность: На сколько сократить или увеличить запасы ресурсов; В каких пределах допустимо изменение коэффициентов функции; Увеличение объема какого ресурса наиболее выгодно.
Верно (В) или неверно (Н) 20. Изменения коэффициентов целевой функции всегда приводят к изменению оптимальных значений переменных. Верно (В) или неверно (Н) 21. Любая допустимая точка ограниченного пространства решений задачи линейного программирования может быть определена, если известны допустимые экстремальные точки. 22. а) б) в)
Первая задача анализа на чувствительность: На сколько сократить или увеличить запасы ресурсов; Увеличение объема какого ресурса наиболее выгодно; В каких пределах допустимо изменение коэффициентов функции.
Верно (В) или неверно (Н) 23. Выполнение условия оптимальности всегда гарантирует, что получаемое на новой итерации значение целевой функции будет лучше, чем на итерации, непосредственно предшествующей данной. Верно (В) или неверно (Н) 24. В задачи линейного программирования возможно изменение коэффициентов целевой функции, не вызывающее изменения оптимальных значений переменных. 25. а) б) в)
Третья задача анализа на чувствительность: На сколько сократить или увеличить запасы ресурсов; Увеличение объема какого ресурса наиболее выгодно; В каких пределах допустимо изменение коэффициентов функции.
26. Величина улучшения оптимального значения целевой функции, приходящегося на единицу прироста объема данного ресурса 29
а) б) в) г)
Ценность ресурса; Целевая функция; Градиент; Оптимальный план.
Верно (В) или неверно (Н) 27. Если ценность ресурса положительна, то он обязательно является дефицитным. Верно (В) или неверно (Н) 28. Основная особенность итерационного процесса состоит в том, что на каждом шаге существует перспектива получения решения, более близкого к допустимому, чем текущее. 29. Ресурс, с которым ассоциировано связывающее ограничение называется а) Дефицитный; б) Избыточный; в) Недефицитный. Верно (В) или неверно (Н) 30. Этапы построения математической модели: 1. Идентификация переменных; 2. Ограничения на переменные; 3. Цель, для достижения которой из всех допустимых значений переменных нужно выбрать только те, которые будут соответствовать оптимальному (наилучшему) решению задачи. Верно (В) или неверно (Н) 31. Симплексный метод состоит из трех основных элементов а) Определение первоначального базисного решения; б) Правила перехода к следующему лучшему решению; в) Проверка оптимального решения. 32. а) б)
Выберите правильное утверждение: Сокращение объема дефицитного ресурса никогда не улучшает значения целевой функции; Сокращение объема дефицитного ресурса улучшает значения целевой функции.
Верно (В) или неверно (Н)
30
33. Изменение коэффициентов целевой функции оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат. 34. а) б) в)
Выберите правильные утверждения: Целевая функция перпендикулярна градиенту; Координаты градиента – частные производные целевой функции; Градиент – вектор, показывающий направление наискорейшего возрастания целевой функции.
35. Какая из точек допустимого множества Х:
x1 − x 2 + x3 = 1,
3 x1 − x 2 + x 4 = 6, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0; является его опорным планом? a ) x1 = (0,0,1,0);
б ) x 2 = (1,0,0,3);
в ) x 3 = (1,1,1,4). 35. После очередной итерации симплекс-метода каноническая задача линейного программирования (ЗЛП) имеет вид Z ( x) = −4 + x1 − 2 x3 → min,
− x1 + x 2 + x3 = 1, 2 x1 − x3 + x 4 = 3, x ι ≥ 0,ι = 1,2,3,4. Определить стратегию симплекс метода: а) текущая опорная точка является решением; б) задача не имеет решения; в) необходимо выполнить следующую итерацию. 36.
После очередной итерации симплекс метода ЗЛП имеет вид
Z ( x) = 20 − x1 + x2 → min, x1 − 2 x 2 + x3 = 1, x1 − x 2 + x 4 = 2, xι ≥ 0,ι = 1,2,3,4. На следующей итерации базисными будут переменные a) ( x1 , x4 ); b) ( x1 , x3 ); 31
в ) (x 2 , x3 ); г ) ( x1, x2 ). 37. Являются ли опорные планы оптимальными для прямой ЗЛП
x = (0,0,6,0,9,1) , u = (6,0,0,1,2,0)
Z ( x) = −5 x1 − 4 x 2 − 6 x3 → min; x1 + x 2 + x3 ≤ 6; 2 x1 − x 2 + 3 x3 ≥ 9; 3 x1 + x 2 + 2 x3 ≥ 11, x j ≥ 0, j = 1,2,3.
и двойственной к ней задачи соответственно? a) да; б) нет. 38. Какой оптимальным?
x1 =
x2 =
из
опорных
Потребители Поставщики А1 А2 Потребность 30 10 0 0
0
планов
В1 4 7 30
В2 3 6 60
транспортной
В3 6 4 50
задачи
Запас груза 40 120 160
50 50 20
0 0 20 20 30 60 30 0
а) оптимальный план − x1 ; 1
б) оптимальный план − x1 ; в) оба плана не оптимальны. 2
39. Представить в каноническом виде ЗЛП Z ( x) = x1 + 2 x 2 + 3 x3 + 2 x 4 + x5 → min ; X: − 3 x1 + x2 + 4 x3 − 2 x4 ≥ 12, x1 − 2 x2 + 3 x3 + x4 + x5 = 4, x1 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0, x 2 − любого знака 32
является
40. Построить двойственную задачу к ЗЛП, приведенной в предыдущем задании. 41. Построить исходный опорный план транспортной задачи методом «северо-западного угла». Потребители Поставщики А1 А2 А3 А4 Потребность
В1 4 7 6 2 80
В2 1 3 4 5 120
В3 2 4 7 6 70
В4 5 2 1 4 130
В5 6 5 8 7 50
Запас груза 100 70 130 150 450
42. Какая из точек допустимого множества Х: 2 x1 + x 2 − x3 = 2,
3 x1 + 4 x 2 + x 4 = 12, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0; является его опорным планом? a ) x1 = (1,0,0,9); б ) x 2 = (1,1,0,0); в ) x 3 = (1,1,1,5). 43. После очередной итерации симплекс-метода каноническая задача линейного программирования (ЗЛП) имеет вид Z ( x) = 10 + x 2 − x 4 → min, x1 − x 2 + 3x 4 = 2, − 2 x 2 + x3 − x 4 = 1, xι ≥ 0,ι = 1,2,3,4. Определить стратегию симплекс метода: а)текущая опорная точка является решением; б)задача не имеет решения; в)необходимо выполнить следующую итерацию.
44.
После очередной итерации симплекс метода ЗЛП имеет вид Z ( x) = −5 + 6 x1 − x 2 → min,
33
x1 + x 2 + x3 = 1, − x1 + 3 x 2 + x 4 = 5, xι ≥ 0,ι = 1,2,3,4. На следующей итерации базисными будут переменные
a) ( x1 , x4 ); b) ( x1 , x3 );
в ) (x 2 , x3 );
г ) ( x 2 , x4 ). 45. Являются ли опорные планы x = ( 2,0,1,8,0) , оптимальными для прямой ЗЛП Z ( x) = 2 x1 + 3 x 2 + 4 x3 → min;
u = (3,1,0,7,0)
x1 + 2 x 2 + x3 = 20; − x1 + 4 x 2 + x 4 = 16; x j ≥ 0, j = 1,2,3,4. и двойственной к ней задачи соответственно? a) да; б) нет. 46. Какой из опорных планов транспортной задачи является оптимальным? Потребители Поставщики В1 А1 4 А2 6 А3 5 Потребность 80
В2 7 2 6 170
В3 1 4 7 150 80
x1 = 0 0 80
x2 = 0 0
0 150
В4 5 1 4 180
В5 2 3 8 70
150 0 0
0
70 0
20 0 0 150
0 180 0 70
0
0
150
0
170
0
30
0
а) оптимальный план − x11 ; б) оптимальный план − x12 ; в) оба плана не оптимальны. 34
Запас груза 300 150 200 650
47. Представить в каноническом виде ЗЛП
Z ( x) = −5 x1 + 4 x 2 + 3 x3 + 6 x 4 → min ; X: x1 + 21x 2 + x3 + 2 x 4 ≤ 3, − x1 − 14 x 2 − 2 x3 + 3 x 4 ≥ 2, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 − любогознака 48. Построить двойственную задачу к ЗЛП, приведенной в предыдущем задании. 49. Построить исходный опорный план транспортной задачи методом «северо-западного угла». Потребители Поставщики А1 А2 А3 А4 Потребность
В1 5 4 1 3 1050
В2 3 2 3 4 2070
В3 1 3 7 6 2150
В4 4 6 4 7 1870
В5 2 1 5 1 1030
Запас груза 1780 2000 1530 2860 8170
50. Какая из точек допустимого множества Х: x1 − 2 x 2 − x3 = 2, − 2 x1 + 3 x 2 + x 4 = 2, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0; является его опорным планом? a) x1 = (3,0,1,8);
б ) x 2 = (2,0,0,6);
в ) x 3 = (0,0,2,2). 51. После очередной итерации симплекс-метода каноническая задача линейного программирования (ЗЛП) имеет вид
Z ( x) = 25 − x1 − x 2 → min, x1 − 2 x 2 + x3 = 1, x1 − x 2 + x 4 = 0, xι ≥ 0,ι = 1,2,3,4. Определить стратегию симплекс метода: 35
а) текущая опорная точка является решением; б) задача не имеет решения; в) необходимо выполнить следующую итерацию. 52.
После очередной итерации симплекс метода ЗЛП имеет вид
Z ( x) = −18 + x 2 − x 4 → min, x1 − x 2 + 3 x 4 = 2, 6 x 2 + x3 = 1, xι ≥ 0,ι = 1,2,3,4. На следующей итерации базисными будут переменные a ) ( x1 , x4 ); b) ( x1 , x3 ); в ) (x 2 , x3 );
г ) ( x 3 , x4 ). x = (0,0,400,500,0,0,50) , Являются ли опорные планы u = (30,15,0,0,75,0,0) оптимальными для прямой ЗЛП Z ( x ) = 75 x1 + 30 x 2 + 60 x 3 + 120 x 4 → max; 2 x1 + x 2 + 0,5 x3 + 4 x 4 ≤ 2400;
53.
x1 + 5 x 2 + 3 x3 ≤ 1200; 3x1 + 6 x3 + x 4 ≤ 3000; x j ≥ 0, j = 1,2,3,4.
и двойственной к ней задачи соответственно? a) да; б) нет. 54. Какой оптимальным?
из
Потребители Поставщики А1 А2 А3 Потребность
опорных
В1 4 3 5 70
В2 7 1 6 120
планов
В3 2 0 3 150
36
транспортной
В4 3 4 7 130
задачи
Запас груза 30 190 250 470
является
30
0
x1 = 40 120 0
0
0
0
0
30
0
120 130
0
0
30
0 90 100 x2 = 0 70 120 60 0 а) оптимальный план − x11 ; б) оптимальный план − x12 ; в) оба плана не оптимальны. 55. В задаче об оптимальном распределении средств состоянием системы на каждом шаге является а) перераспределение средств на следующий хозяйственный год; б) прибыль, полученная в прошедшем году; в) денежные средства предприятия в начале текущего года. 56. Представить в каноническом виде ЗЛП
Z ( x ) = 2 x1 − x 3 → min ; X: − 4 x1 + 2 x2 + 3x3 = 8, − 2 x1 − 2 x2 + x3 ≤ 2, − x1 − x2 + 3x3 ≥ 3, x1 ≥ 0, x2 ≥ 0, x3 − любого знака 56. Построить двойственную задачу к ЗЛП, приведенной в предыдущем задании. 57. Построить исходный опорный план транспортной задачи методом «северо-западного угла». Потребители Поставщики В1 В2 В3 В4 В5 Запас груза А1 5 1 2 3 2 300 А2 6 3 7 1 1 200 А3 4 5 3 2 5 500 А4 2 4 6 4 7 700 Потребность 230 420 650 100 300 1700
37
58. Какая из точек допустимого множества Х: 2 x1 + 7 x 2 + x3 = 21,
7 x1 + 2 x 2 + x 4 = 49, x1 ≥ 0, x 2 ≥ 0, x3 ≥ 0, x 4 ≥ 0; является его опорным планом? a ) x1 = (1,2,0,0); б ) x 2 = (5,1,4,1,2); в ) x 3 = (0,0,2,1,4,9).
59. После очередной итерации симплекс-метода каноническая задача линейного программирования (ЗЛП) имеет вид Z ( x) = 5 + x1 + x 4 → min, − 2 x1 + x 2 − x 4 = 2,
x1 + x3 = 5, xι ≥ 0,ι = 1,2,3,4. Определить стратегию симплекс метода: а) текущая опорная точка является решением; б) задача не имеет решения; в) необходимо выполнить следующую итерацию. 60.
После очередной итерации симплекс метода ЗЛП имеет вид
Z ( x) = −4 + x1 − x 2 → min, x1 + 2 x 2 + x3 = 1, x1 + x 2 + x 4 = 0, xι ≥ 0,ι = 1,2,3,4. На следующей итерации базисными будут переменные
a) ( x1 , x4 ); b) ( x1 , x3 ); в ) (x 2 , x3 );
г ) ( x 3 , x4 ). 61.
1 3 3 2 4 8
Являются ли опорные планы x = (2,0,9,0,0,0) , u = ( , , ,0,0,0)
оптимальными для прямой ЗЛП Z ( x) = 8 x1 + 5 x 2 + 6 x3 → min;
38
4 x1 + 4 x 2 + 6 x3 ≥ 62; 6 x1 + x 2 + 2 x3 ≥ 30; 4 x1 + 6 x 2 + 4 x3 ≥ 44; x j ≥ 0, j = 1,2,3.
и двойственной к ней задачи соответственно? a) да; б) нет. 62. Какой оптимальным?
из
Потребители Поставщики А1 А2 А3 Потребность
опорных
В1 9 6 8 60
60 40 0 0 x1 = 0 10 40 30 0
0
0
5
планов
В2 6 9 7 50
В3 8 13 12 40
транспортной
задачи
В4 11 15 5 35
Запас груза 100 80 40 220
В5 10 12 9 35
0 0 35
50 50 0 0 0 x 2 = 10 0 35 35 0 0 0 5 0 35
а) оптимальный план − x11 ; б) оптимальный план − x12 ; в) оба плана не оптимальны. 63. Представить в каноническом виде ЗЛП Z ( x ) = 2 x1 − x 2 − 3 x3 + x 4 − 2 x5 → min ;
X: x1 − 2 x2 − x3 + 2 x4 + x5 = 5, x2 + 4 x3 − 2 x4 ≤ 4, x1 ≥ 0, x3 ≥ 0, x4 ≥ 0, x2 − любого знака 39
является
64. Построить двойственную задачу к ЗЛП, приведенной в предыдущем задании. 65. Построить исходный опорный план транспортной задачи методом «северо-западного угла». Потребители Поставщики А1 А2 А3 А4 Потребность
В1 4 6 5 1 300
В2 1 4 2 7 400
В3 5 2 3 4 200
В4 4 7 4 3 100
В5 2 3 6 5 150
Запас груза 200 450 350 150 1150
5. Вопросы к зачету
1. Постановка и математическая модель задачи линейного программирования (ЗЛП). Понятия целевой функции, системы ограничений, допустимого 2. решения, оптимального решения ЗЛП. Задача о раскрое. 3. Задача о диете. 4. Задача о карамели. 5. Задача оптимального планирования производства. 6. Транспортная задача. 7. Задача о назначениях. 8. Общая и каноническая формы записи ЗЛП. Правила перехода к 9. канонической форме ЗЛП. 10. Векторная, матричная формы записи ЗЛП. 11. Понятия выпуклого многоугольника, выпуклого многогранника, угловых точек выпуклого множества. 12. Понятия допустимого решения (плана), допустимого базисного решения задачи линейного программирования. 13. Основная теорема линейного программирования (теорема о соотнесении оптимального решения ЗЛП и угловых точек множества допустимых решений ЗЛП). 14. Графический метод решения задачи линейного программирования. Алгоритм метода. 15. Графический метод решения ЗЛП. Понятие многоугольника решений ЗЛП. Правила его построения. 16. Графический метод решения ЗЛП. Понятие линии уровня и градиента целевой функции. Правила их построения. 40
17. Графический метод решения ЗЛП. Нахождение оптимального решения с помощью градиента и линии уровня целевой функции. 18. Графический метод решения ЗЛП. Геометрическая интерпретация единственного оптимального решения, множества оптимальных решений, отсутствия оптимальных решений. 19. Симплекс-метод решения ЗЛП. 20. Геометрический смысл симплекс-метода решения ЗЛП. 21. Обобщенный алгоритм симплекс-метода решения ЗЛП. 22. Двойственные задачи линейного программирования. Правила построения двойственной задачи. интерпретация двойственной задачи и 23. Экономическая двойственных переменных. 24. Первая теорема двойственности и ее экономическое содержание. 25. Вторая теорема двойственности и ее экономическое содержание. 26. Взаимосвязь оптимальных решений прямой и двойственной задач (на основе теорем двойственности). задача линейного программирования. 27. Транспортная Математическая модель ТЗ. Матрица системы ограничений модели ТЗ. 28. Транспортная задача. Закрытая и открытая модели ТЗ. Приведение открытой ТЗ к закрытой. 29. Транспортная задача. Понятие оптимального плана (перевозки), вырожденного и невырожденного плана. 30. Транспортная задача. Методы построения начального плана перевозок (метод северо-западного угла, метод минимальной стоимости). 31. Транспортная задача. Метод потенциалов решения ТЗ. Критерий оптимальности плана перевозок. 32. Транспортная задача. Алгоритм улучшения плана перевозок. Понятие цикла и его цены. Построение улучшенного плана перевозок и расчет его цены. 33. Транспортная задача. Правило определения максимального количества груза для переноса по циклу. 34. Транспортная задача. Признак множества оптимальных планов перевозки грузов. 35. Задача о назначениях. Венгерский метод.
41
Список использованных источников
Основная литература 1. Зандер Е.В., Злодеев В.П., Мошкович Л.И., Семенова А.Р. Исследование операций в экономике / Учебное пособие. Красноярск, КрасГУ, 2005. Акулич И.Л. Математическое программирование в примерах и 2. задачах / И.Л. Акулич. – М.: Высш. шк.,1993. Зандер Е.В. Практикум по исследованию операций: нелинейные, 3. динамические и специальные модели / Е.В. Зандер, В.П. Злодеев. – Красноярск: РИЦ КрасГУ, 1998. Косоруков О.А. Исследование операций / О.А. Косоруков, А.В. 4. Мищенко. – М.: Экзамен, 2003. Кремер Н.Ш. Исследование операций в экономике / Н.Ш. Кремер. – 5. М.: Банки и биржи, 2000. Мошкович Л.И. Ситуационный анализ в экономике / Л.И. 6. Мошкович, Е.В. Зандер, В.П. Злодеев. – Красноярск: РИЦ КрасГУ, 1996.
Дополнительная литература 1. Афанасьев М.Ю. Исследование операций в экономике: Учеб. пособие / М.Ю. Афанасьев, Б.П. Суворов. – М.: ТЕИС, 2003. 2. Замков О.О. Математические методы в экономике / О.О. Замков, А.В. Толстопятенко, Ю.Н. Черемных. – М.: Дело и сервис, 1997. 3. Кади Дж. Количественные методы в экономике / Дж. Кади. – М.: ИНФРА-М, 1997. 4. Солодовников А.С. Математика в экономике /А.С. Солодовников, В.А. Бабайцев, А.В. Браилов. – М.: Финансы и статистика, 1999. 5. Уотшен Т. Количественные методы в финансах / Т. Уотшен, К. Паррамоу – М.: ЮНИТИ, 1999. 6. Эддоус М. Методы принятия решений / М. Эддоус, Р. Стенсфилд. – М.: ЮНИТИ, 1997.
42