Ответы и решения

ГПНет. Вне ОДР не может находиться не только оптимальное решение, но и любое другое.

• 2. Да. Смотрите, например, рис. 6.
• 3. Оптимальное решение всегда является допустимым, а допустимое решение не обязательно оптимально.

|~4~1 Может. Смотрите, например, рис. 30, где многоугольник решений выродился в отрезок прямой.

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

|б7|а) Симметрический вид; б) не относится к задачам ЛП, так как все переменные должны иметь степень не выше первой (см. §1.1-1.4); в) канонический вид; г) задачи со строгими неравенствами не относятся к задачам ЛП; д) стандартный вид.

ГПа) Первое и второе неравенства-ограничения заменим следующей системой:

Третье неравенство-ограничение примет вид

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

Получаем

[Ж] Нет. В разрешающем столбце должна быть ровно одна единица.

[9] Нет. Такое ограничение не имеет экономического смысла.

*

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

За базисные переменные примем х, Х2, хз.

Из последнего блока запишем:

Отбрасывая переменные хь Х2 и лу, а также учитывая их неотрицательность, приходим к задаче

• 111. | Нет. В этом случае задача не имеет решений ввиду несовместимости системы ограничений (рис.8).
• 112. |Может, Однако в этом случае целевая функция может достигать лишь одного значения — либо минимума, шзбо максимума. Если ОДР неограничена по направлению вектора N = (с,; с₂), то конечно только значение а /-’_тах = +<х>. Если же ОДР неограничена в направлении, противоположном вектору (V, то конечно только значение Е'тах, а Р_тт = -00.

• 113. [Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение.
• 114. | Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с ОДР и по отношению к которой эта область находится в одной из полуплоскостей (рис. 6, 12).
• 115. | Верхняя опорная прямая соответствует максимальному, а нижняя — максимальному значению целевой функции (рис. 12).
• 16. Нет. Они всегда перпендикулярны.
• 17. |Нет. Задача ЛП может иметь либо одно оптимальное решение (рис. 12), либо бесконечное множество (рис. 6).
• 18. Когда система ограничений несовместна (рис. 8).
• 19. Можно.
• 20. а) Отмечаем, что тривиальные неравенства-ограничения в математической модели отсутствуют.

Далее строим прямые х + Зх₂ = 18; 2х + х₂ = 16; х₂ = 5; Х[ = 7 и, как в §1.4, подставляя координаты точки О (0; 0) в систему ограничений (3.1-3.4), находим^)ДР. Видим, что система ограничений совместна. Строим вектор N. В нашем случае /7(2; 3), где 2 и 3 — коэффициенты С| и с₂ при XI и х₂ в целевой функции. Затем через точку О (0; 0) проводим прямую, перпендикулярную N. Это и будет целевая функция, соответствующая нулевому уровню, и в нашем случае одновременно и нижняя опорная прямая, соответствующая минимуму. Мысленно передвигая нижнюю опорную прямую параллельно самой себе, видим, что максимальное значение целевая функция принимает в точке В. Для нахождения ее координат решим систему

Подставляя значения х и х₂ в целевую функцию, находим ответ:

д) Методом Жордана-Гаусса приведем систему уравнений-ограничений задачи к равносильной разрешенной. Одновременно исключим разрешенные неизвестные из целевой функции. Приведенные системы дадим без описания промежуточных этапов, надеясь, что читатель внимательно ознакомился с примерами 2 и 3.

Теперь, как и в примерах 2, 3, запишем задачу ЛП в преобразованном виде:

Далее, отбрасывая неотрицательные переменныеХ,х₂ их₃и заменяя знак равенства знаками нестрогих неравенств, получим вспомогательную задачу линейного программирования с двумя переменными:

Рис. 47

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

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

Находим оптимальное решение задачи, используя для этого систему ограничений в разрешенном виде:

Откуда

Получаем

е) Отмечаем, что условия неотрицательности не распространяются на переменные хз и Хф

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

Для формализации целевой функции введем в нее дополнительные переменные *5, лу„ х-} с коэффициентами, равными нулю.

Теперь исключим переменные, на которые не распространяются условия неотрицательности. В нашем случае это и хз, и Хф Для этого опять воспользуемся методом Жордана-Гаусса. Считая, что читатель уже достаточно хорошо освоил методы работы с такими таблицами, приводим ее без комментариев.

Последняя строка третьего блока таблицы соответствует целевой функции, написанной в виде выражения со свободным членом Б + 46. Разрешим систему относительно хз и Хф Из последнего блока таблицы получаем:

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

Далее разрешаем последнюю систему относительно х$,хв,ху, получаем:

Условия приводят к неравенствам:

или

Решаем задачу графически. Предлагаем читателю проделать это самостоятельно. Находим Р_тах = Р(4/3, 0) = 34/3. Зная экстремальные значения х = 4/3; х₇ = 0, находим значения остальных неизвестных из систем (3.5), (3.6).

Опуская значения дополнительных неизвестных х₅, х₆, х₇, получаем (условие отсутствует), Таким образом,

Т’тах = (4/3; 0; -2/3; 10/3) = 34/3.

|21.| а) Среди бесчисленного множества диет, разработанных к настоящему времени, одной из последних новинок является диета по группе крови. Суть ее заключается в том, что не все питательные вещества одинаково полезны для каждого человека! И тут главная причина кроется именно в группе крови: вещества, поступающие в организм вместе с пищей, оказывают на жизнедеятельность организма либо положительное, либо отрицательное воздействие.

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

Врачами-натуропатами была предложена теория рационального питания. Основу этой теории составляет группа крови человека. Так, согласно этой теории, те или иные продукты не относятся к изначально «полезным» или «вредным» для всех людей без исключения: во главу угла ставится группа крови человека, в зависимости от которой и следует питаться. Предположим, вы являетесь сторонником этой теории, и у вас вторая группа крови. Тогда вам остается приобрести счетчик калорий, который можно купить в любом книжном магазине, составить математическую модель задачи и провести оптимизацию с помощью программы Excel. Предположим также, что начало вашего здорового образа жизни пришлось на время какого-либо поста, поэтому вы решили исключить из своего меню мясные продукты. Пусть два дня в неделю ваше меню будет состоять из масла оливкового, хлеба ржаного, орехов фундук, каши гречневой, огурцов соленых, мармелада и кваса хлебного, которые мы обозначим XI, ..., Х7 соответственно.

Калорийность приводится на 100 г/100 мл продукта.

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

Предположим, что диету составляет для себя мужчина среднего возраста. Тогда суточное потребление калорий для него при весе 70 кг составляет около 2600 ккал. Кроме того, существуют научно разработанные нормы потребления белков, жиров и углеводов, которые составляют 100, 70 и 400 граммов соответственно. Теперь мы можем составить математическую модель нашей задачи.

где d, ..., di — калорийность соответствующего вида продуктов, а 1,..., «7 — содержание белков в единице (100г/100мл) продукта, Ь, ..., bi — содержание жиров в единице продукта, с 1, ..., ci — содержание углеводов в единице продукта.

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

Рис. 48

В самом деле, нам необходимо съедать в день 900 г хлеба ржаного, 93 грамма орехов фундук и 1100 г соленых огурцов и пить при этом только кипяченую воду.

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

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

|22.|Нет. Сначала необходимо привести знаки к одному направлению.

• 123. | Матрица исходной задачи и матрица двойственной получа- ются друг из друга с помощью операции транспортирования.
• 124. |Если экстремальное значение одной задачи — максимум, то экстремальное значение другой — минимум и наоборот.

|25.|Нет (см. Ответ на вопрос 24).

126. | а) F = 12уI + 10)'2 + 9>'з —> min

^в) /*’тах = +°о. Двойственная задача не имеет допустимых решений.

277

Сумма рангов везде одинакова и равна

[28.1 Применяя (/-критерий, находим

11= 11, Сэмп ⁼ 3

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

129. | После проведения ранжирования находим Т_лш = 10. Значения Т_кр и Т_кр2 те же, что и в примере с первым роликом:

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