Помощь по Теле2, тарифы, вопросы

Тесты для текущего контроля знаний

1. Любая экономико – математическая модель задачи линейного программирования состоит из:

A. целевой функции и системы ограничений

B. целевой функции, системы ограничений и условия неотрицательности переменных

C. системы ограничений и условия неотрицательности переменных

D. целевой функции и условия неотрицательности переменных

A. целевая функция

B. система уравнений

C. система неравенств

D. условие неотрицательности переменных

3. Оптимальное решение задачи математического программирования – это

A. допустимое решение системы ограничений

B. любое решение системы ограничений

C. допустимое решение системы ограничений, приводящее к максимуму или минимуму целевой функции

D. максимальное или минимальное решение системы ограничений

4. Система ограничений называется стандартной, если она содержит

A. все знаки

B. все знаки

C. все знаки

D. все знаки

5. Задача линейного программирования решается графическим способом, если в задаче

A. одна переменная

B. две переменные

C. три переменные

D. четыре переменные

6. Неравенство вида описывает

B. окружность

C. полуплоскость

D. плоскость

7. Максимум или минимум целевой функции находится

A. в начале координат

B. на сторонах выпуклого многоугольника решений

C. внутри выпуклого многоугольника решений

D. в вершинах выпуклого многоугольника решений

8. Каноническим видом ЗЛП называется такой ее вид, в котором система ограничений содержит знаки

A. все знаки

B. все знаки

C. все знаки

D. все знаки

9. Если ограничение задано со знаком «>=», то дополнительная переменная вводится в это ограничение с коэффициентом

B. -1

10. В целевую функцию дополнительные переменные вводятся с коэффициентами

C. 0

A. количество ресурса с номером i, необходимого для изготовления 1 единицы продукции j – го вида

B. неиспользованные ресурсы i - го вида

C. прибыль от реализации 1 единицы продукции j – го вида

D. количество продукции j – го вида

12. Разрешающий столбец при решении ЗЛП на max целевой функции выбирается исходя из условия

A. наибольшее положительное значение коэффициента Cj целевой функции

B. наименьшее положительное значение коэффициента Cj целевой функции

C. наибольшее отрицательное значение коэффициента Cj целевой функции

D. любой столбец коэффициентов при неизвестных

13. Значение целевой функции в таблице с оптимальным планом находится

A. на пересечении строки коэффициентов целевой функции со столбцом коэффициентов при х1

B. на пересечении строки коэффициентов целевой функции со столбцом b

C. в столбце коэффициентов при хn

D. на пересечении строки коэффициентов целевой функции со столбцом первоначального базиса

14. Искусственные переменные в систему ограничений в каноническом виде вводятся с коэффициентом

A. 1

15. Оптимальность плана в симплексной таблице определяется

A. по столбцу b

B. по строке значений целевой функции

C. по разрешающей строке

D. по разрешающему столбцу

16. Дана задача линейного программирования

B. 1

17. Дана задача линейного программирования

Количество искусственных переменных для этой задачи равно

C. 2

18. Если исходная ЗЛП имеет вид

тогда ограничения двойственной задачи

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

19. Если исходная ЗЛП имеет вид

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

20. Коэффициентами при неизвестных целевой функции двойственной задачи являются

A. коэффициенты при неизвестных целевой функции исходной задачи

B. свободные члены системы ограничений исходной задачи

C. неизвестные исходной задачи

D. коэффициенты при неизвестных системы ограничений исходной задачи

21. Если исходная ЗЛП была на максимум целевой функции, то двойственная задача будет

A. тоже на максимум

B. либо на максимум, либо на минимум

C. и на максимум, и на минимум

D. на минимум

22. Связь исходной и двойственной задач заключается в том, что

A. надо решать обе задачи

B. решение одной из них получается из решения другой

C. из решения двойственной задачи нельзя получить решения исходной

D. обе имеют одинаковые решения

23. Если исходная ЗЛП имеет вид

тогда целевая функция двойственной задачи

A. имеют вид

B. имеют вид

C. имеют вид

D. имеют вид

24. Если исходная ЗЛП имеет вид

то количество переменных в двойственной задаче равно

B. 2

25. Модель транспортной задачи закрытая,

A. если

26. Цикл в транспортной задаче – это

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

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

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

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

27. Потенциалами транспортной задачи размерности (m*n) называются m+n чисел ui и vj, для которых выполняются условия

A. ui+vj=cij для занятых клеток

B. ui+vj=cij для свободных клеток

C. ui+vj=cij для первых двух столбцов распределительной таблицы

D. ui+vj=cij для первых двух строк распределительной таблицы

28. Оценками транспортной задачи размерности (m+n) называются числа

yij=cij-ui-vj, которые вычисляются

A. для занятых клеток

B. для свободных клеток

C. для первых двух строк распределительной таблицы

D. для первых двух столбцов распределительной таблицы

29. При решении транспортной задачи значение целевой функции должно от итерации к итерации

A. увеличиваться

B. увеличиваться или не меняться

C. увеличиваться на величину любой оценки

D. уменьшаться или не меняться

30. Число занятых клеток невырожденного плана транспортной задачи должно быть равно

C. m+n-1

31. Экономический смысл целевой функции транспортной задачи

A. суммарный объем перевозок

B. суммарная стоимость перевозок

C. суммарные поставки

D. суммарные потребности

Федеральное агентство по образованию

Государственное бюджетное образовательное учреждение

высшего профессионального образования

«Омский государственный технический университет»

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

по дисциплине « ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ »

на тему « МЕТОДЫ ОПТИМИЗАЦИИ И ИССЛЕДОВАНИЕ ОПЕРАЦИЙ »

вариант 7

Выполнил:

студент заочного отделения

4-го курса группы ЗА-419

ФИО: Кужелев С. А.

Проверила:

Девятерикова М. В.

Омск – 2012 г.
^

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

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Шаг 1. Построение допустимой области

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

Первое ограничение модели имеет вид . Заменив в нем знак ≤ на знак =, получаем уравнение. На рис. 1.1 оно определяет прямую (1), которая разбивает плоскость на две полуплоскости, в данном случае выше линии и ниже нее. Чтобы выбрать, какая из них удовлетворяет неравенству , подставим в него координаты любой точки, не лежащей на данной прямой (например, начало координат х 1 = 0, х 2 = 0). Так как получаем верное выражение (20 0 + 6 0 = 0 ≤15), то неравенству удовлетворяет полуплоскость, содержащая начало координат (помечена стрелкой). В противном случае другая полуплоскость.

Аналогично поступаем с остальными ограничениями задачи. Пересечение всех построенных полуплоскостей с первым квадрантом образует ABCD (см. рис. 1). Это и есть допустимая область задачи.

Шаг 2. Построение линии уровня Линия уровня целевой функции - это множество точек плоскости, в которых целевая функция принимает постоянное значение. Такое множество задается уравнением f ( x ) = const . Положим, например, const = 0 и построим линию у ровня f ( x ) = 0 , т.е. в нашем случае прямую 7x 1 + 6x 2 = 0.

Данная прямая проходит через начало координат и перпендикулярна вектору . Этот вектор является градиентом целевой функции в точке (0,0). Градиент функции - это вектор значений частных производных данной функции в рассматриваемой точке. В случае задачи ЛП частные производные целевой функции равны коэффициентам C i, j = 1 , ..., n .

Градиент показывает направление наискорейшего роста функции. Перемещая линию уровня целевой функции f ( x ) = const . перпендикулярно направлению градиента, найдем последнюю точку, в которой она пересекается с областью. В нашем случае это точка D, которая и будет точкой максимума целевой функции (см. рис. 2)

Она лежит на пересечении прямых (2 ) и (3 ) (см. рис. 1 ) и задает оптимальное решение.

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

^ Шаг 3. Определение координат точки максимума (минимума) и оптимального значения целевой функции

Чтобы найти координаты точки C, необходимо решить систему, состоящую из соответствующих прямым уравнений (в данном случае из уравнений 2 и 3 ):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

Получим оптимальное решение = 1,33.

^ Оптимальное значение целевой функции f * = f (х*) = 7 * 0 + 6 * 1,33 = 7,8

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

Рассмотрим задачу линейного программирования с двумя переменными и :
(1.1) ;
(1.2)
Здесь , есть произвольные числа. Задача может быть как на нахождение максимума (max), так и на нахождение минимума (min). В системе ограничений могут присутствовать как знаки , так и знаки .

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

Графический метод решения задачи (1) следующий.
Вначале мы проводим оси координат и и выбираем масштаб. Каждое из неравенств системы ограничений (1.2) определяет полуплоскость, ограниченную соответствующей прямой.

Так, первое неравенство
(1.2.1)
определяет полуплоскость, ограниченную прямой . С одной стороны от этой прямой , а с другой стороны . На самой прямой . Чтобы узнать, с какой стороны выполняется неравенство (1.2.1), мы выбираем произвольную точку, не лежащую на прямой. Далее подставляем координаты этой точки в (1.2.1). Если неравенство выполняется, то полуплоскость содержит выбранную точку. Если неравенство не выполняется, то полуплоскость расположена с другой стороны (не содержит выбранную точку). Заштриховываем полуплоскость, для которой выполняется неравенство (1.2.1).

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

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

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

Если хотя бы одно неравенство не выполняется, то выбираем другую точку. И так далее, пока не будет найдены одна точка, координаты которой удовлетворяют системе (1.2).

Нахождение экстремума целевой функции

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

Теперь мы можем искать экстремум целевой функции
(1.1) .

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

Таким образом, чтобы найти максимальное значение целевой функции, надо провести прямую, параллельную прямой (3), максимально удаленную от нее в сторону возрастания значений , и проходящую хотя бы через одну точку ОДР. Чтобы найти минимальное значение целевой функции, надо провести прямую, параллельную прямой (3) и максимально удаленную от нее в сторону убывания значений , и проходящую хотя бы через одну точку ОДР.

Если ОДР неограниченна, то может возникнуть случай, когда такую прямую провести нельзя. То есть как бы мы ни удаляли прямую от линии уровня (3) в сторону возрастания (убывания) , то прямая всегда будет проходить через ОДР. В этом случае может быть сколь угодно большим (малым). Поэтому максимального (минимального) значения нет. Задача решений не имеет.

Рассмотрим случай, когда крайняя прямая, параллельная произвольной прямой вида (3), проходит через одну вершину многоугольника ОДР. Из графика определяем координаты этой вершины. Тогда максимальное (минимальное) значение целевой функции определяется по формуле:
.
Решением задачи является
.

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

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

Условие задачи

Фирма выпускает платья двух моделей А и В. При этом используется ткань трех видов. На изготовление одного платья модели А требуется 2 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. На изготовление одного платья модели В требуется 3 м ткани первого вида, 1 м ткани второго вида, 2 м ткани третьего вида. Запасы ткани первого вида составляют 21 м, второго вида - 10 м, третьего вида - 16 м. Выпуск одного изделия типа А приносит доход 400 ден. ед., одного изделия типа В - 300 ден. ед.

Составить план производства, обеспечивающий фирме наибольший доход. Задачу решить графическим методом.

Решение

Пусть переменные и означают количество произведенных платьев моделей А и В, соответственно. Тогда количество израсходованной ткани первого вида составит:
(м)
Количество израсходованной ткани второго вида составит:
(м)
Количество израсходованной ткани третьего вида составит:
(м)
Поскольку произведенное количество платьев не может быть отрицательным, то
и .
Доход от произведенных платьев составит:
(ден. ед.)

Тогда экономико-математическая модель задачи имеет вид:

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 7) и (10,5; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 10) и (10; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (8; 0).

Заштриховываем область, чтобы точка (2; 2) попала в заштрихованную часть. Получаем четырехугольник OABC.

(П1.1) .
При .
При .
Проводим прямую через точки (0; 4) и (3; 0).

Далее замечаем, что поскольку коэффициенты при и целевой функции положительны (400 и 300), то она возрастает при увеличении и . Проводим прямую, параллельную прямой (П1.1), максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку четырехугольника OABC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

.
То есть, для получения наибольшего дохода, необходимо изготовить 8 платьев модели А. Доход при этом составит 3200 ден. ед.

Пример 2

Условие задачи

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

Решение

Решаем графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 6) и (6; 0).

Строим прямую .
Отсюда .
При .
При .
Проводим прямую через точки (3; 0) и (7; 2).

Строим прямую .
Строим прямую (ось абсцисс).

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

Заштриховываем область по границам построенных прямых, чтобы точка (4; 1) попала в заштрихованную часть. Получаем треугольник ABC.

Строим произвольную линию уровня целевой функции, например,
.
При .
При .
Проводим прямую линию уровня через точки (0; 6) и (4; 0).
Поскольку целевая функция увеличивается при увеличении и , то проводим прямую, параллельную линии уровня и максимально удаленную от нее в сторону возрастания , и проходящую хотя бы через одну точку треугольника АВC. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.

Решение задачи: ;

Ответ

Пример отсутствия решения

Условие задачи

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

Решение

Решаем задачу графическим методом.
Проводим оси координат и .

Строим прямую .
При .
При .
Проводим прямую через точки (0; 8) и (2,667; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (0; 3) и (6; 0).

Строим прямую .
При .
При .
Проводим прямую через точки (3; 0) и (6; 3).

Прямые и являются осями координат.

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

Заштриховываем область, чтобы точка (3; 3) попала в заштрихованную часть. Получаем неограниченную область, ограниченную ломаной ABCDE.

Строим произвольную линию уровня целевой функции, например,
(П3.1) .
При .
При .
Проводим прямую через точки (0; 7) и (7; 0).
Поскольку коэффициенты при и положительны, то возрастает при увеличении и .

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

Ищем минимум. Проводим прямую, параллельную прямой (П3.1) и максимально удаленную от нее в сторону убывания , и проходящую хотя бы через одну точку области ABCDE. Такая прямая проходит через точку C. Из построения определяем ее координаты.
.
Минимальное значение целевой функции:

Ответ

Максимального значения не существует.
Минимальное значение
.

Найти графическим методом максимум целевой функции

F = 2x 1 + 3x 2 ® max

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

Решение с помощью таблиц Excel

Вначале построим на листе Excel решение системы неравенств.

Рассмотрим первое неравенство .

Построим граничную прямую по двум точкам. Прямую обозначим (L1)(или Ряд1). Координаты х 2 считаем по формулам:

Для построения выбираем точечную диаграмму

Выбираем данные для прямой

Изменяем название прямой:

Выбираем макет диаграммы. Изменяем название осей координат:

Прямая (L1) на графике:

Решение строгого неравенства можно найти с помощью единственной пробной точки, не принадлежащей прямой (L1). Например, с помощью точки (0; 0)Ï(L1).

0 + 3×0 < 18 или 0 < 18 .

Неравенство является верным, следовательно решением неравенства (1) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L1).

Затем решаем неравенство (2) .

Построим граничную прямую 2 по двум точкам. Прямую обозначим (L2).

Прямая (L2) на графике:

Решение строгого неравенства 2 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L2). Например, с помощью точки (0; 0)Ï(L2).

При подстановке координат точки (0; 0), получаем неравенство

2×0 + 0 < 16 или 0 < 16 .

Неравенство является верным, следовательно решением неравенства (2) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L2).

Затем решаем неравенство (3) .

Построим граничную прямую по двум точкам. Прямую обозначим (L3).

Прямая (L3) на графике:

Решение строгого неравенства 2 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L3). Например, с помощью точки (0; 0)Ï(L3).

При подстановке координат точки (0; 0), получаем неравенство

Неравенство является верным, следовательно решением неравенства (3) будет та полуплоскость, в которой пробная точка расположена (на рисунке ниже прямой L3).

Затем решаем неравенство (4) .

Построим граничную прямую по двум точкам. Прямую обозначим (L4).

На листе Excel добавляем данные

Прямая (L4) на графике:

Решение строгого неравенства 3х 1 < 21 можно найти с помощью единственной пробной точки, не принадлежащей прямой (L4). Например, с помощью точки (0; 0)Ï(L4).

При подстановке координат точки (0; 0), получаем неравенство

Неравенство является верным, следовательно, решением неравенства (4) будет та полуплоскость, в которой пробная точка расположена (на рисунке левее прямой L4).

Решением двух неравенств (5) и (6)

является 1-ая четверть, ограниченная координатными прямыми и .

Система неравенств решена. Решением системы неравенств (1) – (6) в данном примере является выпуклый многоугольник в левом нижнем углу рисунка, ограниченный прямыми L1, L2, L3, L4 и координатными прямыми и . Убедиться, что многоугольник выбран правильно, можно подстановкой пробной точки, например (1; 1) в каждое неравенство исходной системы. При подстановке точки (1; 1) получаем, что все неравенства, в том числе естественные ограничения, верные.

Рассмотрим теперь целевую функцию

F = 2x 1 + 3x 2 .

Построим линии уровня для значений функции F = 0 и F = 12 (числовые значения выбраны произвольно). На листе Excel добавляем данные

Линии уровней на графике:

Построим вектор направлений (или градиент) {2; 3}. Координаты вектора совпадают с коэффициентами целевой функции F .

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

Базисным столбцам соответствуют единичные столбцы.

Расчет остальных значений таблицы:

«БП – Базисный План»:

; ;

«х1»: ; ;

«х5»: ; .

Значения индексной строки неотрицательны, следовательно получаем оптимальное решение: , ; .

Ответ: максимальную прибыль от реализации изготовленной продукции, равную 160/3 ед., обеспечивает выпуск только продукции второго типа в количестве 80/9 единиц.

Задание № 2

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

Т.к. последняя цифра шифра равна 8, то А=2; В=5.

Т.к. предпоследняя цифра шифра равна 1, то следует выбрать задачу № 1.

Решение:

1) Начертим область, которую задает система неравенств.

Эта область – треугольник АВС с координатами вершин: А(0; 2); В(4; 6) и С(16/3; 14/3).

Уровни целевой функции представляют собой окружности с центром в точке (2; 5). Квадраты радиусов будут являться значениями целевой функции. Тогда по рисунку видно, что минимальное значение целевой функции достигается в точке Н, максимальное – либо в точке А, либо в точке С.

Значение целевой функции в точке А: ;

Значение целевой функции в точке С: ;

Значит, наибольшее значение функции достигается в точке А(0; 2) и равно 13.

Найдем координаты точки Н.

Для этого рассмотрим систему:

ó

ó

Прямая является касательной к окружности, если уравнение имеет единственное решение. Квадратное уравнение имеет единственное решение, если дискриминант равен 0.

Тогда ; ; - минимальное значение функции.

2) Составим функцию Лагранжа для нахождение минимального решения:

При x 1 =2.5; x 2 =4.5 получим:

ó

Система имеет решение при , т.е. достаточные условия экстремума выполняются.

Составим функцию Лагранжа для нахождение максимального решения:

Достаточные условия экстремума:

При x 1 =0; x 2 =2 получим:

ó ó

Система также имеет решение, т.е. достаточные условия экстремума выполняются.

Ответ: минимум целевой функции достигается при ; ; максимум целевой функции достигается при ; .

Задание № 3

Двум предприятиям выделяются средства в количестве d единиц. При выделении первому предприятию на год x единиц средств оно обеспечивает доход k 1 x единиц, а при выделении второму предприятию y единиц средств, оно обеспечивает доход k 1 y единиц. Остаток средств к концу года для первого предприятия равен nx , а для второго my . Как распределить все средства в течение 4-х лет, чтобы общий доход был наибольшим? Задачу решить методом динамического программирования.

i=8, k=1.

A=2200; k 1 =6; k 2 =1; n=0.2; m=0.5.

Решение:

Весь период длительностью 4 года разбиваем на 4 этапа, каждый из которых равен одному году. Пронумеруем этапы начиная с первого года. Пусть Х k и Y k – средства, выделенные соответственно предприятиям А и В на k – том этапе. Тогда сумма Х k + Y k =а k является общим количеством средств, используемых на k – том этапе и оставшиеся от предыдущего этапа k – 1. на первом этапе используются все выделенные средства и а 1 =2200 ед. доход, который будет получен на k – том этапе, при выделении Х k и Y k единиц составит 6Х k + 1Y k . пусть максимальный доход, полученный на последних этапах начиная с k – того этапа составляет f k (а k) ед. запишем функциональное уравнение Беллмана, выражающее принцип оптимальности: каково бы не было начальное состояние и начальное решение последующее решение должно быть оптимальным по отношению к состоянию, получаемому в результате начального состояния:

Для каждого этапа нужно выбрать значение Х k , а значение Y k =а k – х k . С учетом этого найдем доход на k – том этапе:

Функциональное уравнение Беллмана будет иметь вид:

Рассмотрим все этапы, начиная с последнего.

(т.к. максимум линейной функции достигается в конце отрезка при х 4 = а 4);