П.1.2. Графическое решение задачи ЛП

Задача 1.2.1. Найти область допустимых решений (ОДР) системы неравенств и определить координаты угловых точек ОДР.

Задача 1.2.2. Найти область возможных решений (ОВР) и область допустимых решений (ОДР) системы неравенств:

Задача 1.2.3.. Найти область возможных решений (ОВР) и область допустимых решений (ОДР) системы неравенств:

Задача 1.2.4. Найти область возможных решений (ОВР) и область допустимых решений (ОДР) системы неравенств:

Задача 1.2.5. Простейшая диета состоит из телятины и хлеба. Содержание в 100 г продукта калорий и холестерина дано в таблице 1.2.5.

табл. 1.2.5, а

Таблица 1.2.5, б

Для приведенных данных:

1. Составьте математическую модель задачи.

2. Найдите графически оптимальное решение задачи.

Задача 1.2.6. Цех выпускает два вида смесей из цемента и песка. Процентное содержание цемента и песка в смесях, прибыль от продажи 1 т смеси, запасы цемента и песка и максимальное потребление каждой смеси даны в таблицах 1.2.6.

Для приведенных ниже данных:

1. Составьте математическую модель задачи.

2. Найдите графически оптимальное решение задачи.

Таблица 1.2.6, а

Таблица 1.2.6, б

Таблица 1.2.6, в

Таблица 1.2.6, г

Задача 1.2.7. Собственные средства банка в сумме с депозитами составляют 100 млн. долларов. Эти средства размещаются в кредитах (x млн. долларов) и неликвидных активах (y млн. долларов). Поэтому Часть этих средств (x млн. долларов), причем не менее 30 млн. долларов, должна быть размещена в кредитах. Кредиты являются неликвидными активами банка с доходностью 20%. Доходность ликвид­ных бумаг меньше и составляет 10%. Средства y млн. долларов, вложенные в ликвидные ценные бумаги, должны составлять не менее 30% от всей суммы средств , размещенных в кредитах и в ликвид­ных ценных бумагах. Цель банка состоит в получении максимальной прибыли от кредитов и ценных бумаг Распреде­лить средства банка и найти наибольшую прибыль.

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

(а)

(

(б)

.

(в)

(г)

Задача 1.2.9. Имеет ли решение задача линейного программирования:

Ответ обоснуйте с помощью графического решения. Как изменится решение, если в условии заменить max на min?

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

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

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

(Указание: приведите матрицу системы к разрешенному виду и выразите все переменные через свободные).

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

(Указание: приведите матрицу системы к разрешенному виду и выразите все переменные через свободные).

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

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

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

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

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

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

(а)

(б)

(в)

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

Задача 1.3.1.

а)

б)

в)

г)

д)

1. Определите вид задачи ЛП.

2. Приведите задачу к симплексной форме.

3. Решите симплекс-методом.

4. Решите графически.

Задача 1.3.2.

1. Определите вид задачи ЛП.

2. Приведите задачу к симплексной форме.

3. Решите симплекс-методом.

4. Решите графически.

Задача 1.3.3.

1. Определите вид задачи ЛП.

2. Приведите задачу к симплексной форме.

3. Решите симплекс-методом.

4. Решите графически.

Задача 1.3.4.

1. Определите вид задачи ЛП.

2. Приведите задачу к симплексной форме.

3. С помощью симплекс-метода определите, имеет ли решение данная задача.

Задача 1.3.5.

Задача 1.3.10.

Задача 1.3.11. Для производства изделий трех видов A, B и C используется три типа производственного оборудования: фрезерное, токарное и шлифоваль­ное. Нормы затрат времени на одно изделие, общий фонд рабочего времени (в станко-часах) для каждого типа оборудования, а так же прибыль от реализации одного изделия указаны в таблице.

а). Найти максимальную прибыль и какой-либо оптимальный план выпуска изделий, её обеспечивающий (найти ).

б). Найти все оптимальные планы.

Задача 1.3.12.

Задача 1.3.13.

П.1.4. Двойственная задача линейного
программирования. Условие устойчивости

Задача.1.4.1. Составьте задачи двойственные к следующим:

а)

б)

в)

г)

Д)

Задача 1.4.2. Для данных задач составить двойственные и найти решения исходной и двойственной задач (используя симплекс-метод).

(а)

(б)

(в)

(г)

Задача 1.4.3. Найти оптимальное решение задач с помощью второй теоремы двойственности.

(а)

(б)

(в)

Задача 1.4.4. Для производства 3-х видов продукции используется 2 вида сырья А и В. Нормы расхода сырья, его запаса и прибыль от реализации единицы продукции приведены в таблице 1.4.4.

Таблица 1.4.4

Выполните следующие задания:

1. Составьте модель исходной задачи ЛП.

2. Запишите модель двойственной задачи ЛП.

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

4. Найдите максимальное значение прибыли по 1-ой теореме двойственности.

5. Сформулируйте 2-ую теорему двойственности для данной задачи.

6. Найдите оптимальное решение исходной задачи по теореме двойственности.

7. Решите исходную задачу симплекс-методом.

8. Выпишите матрицу устойчивости исходной задачи.

9. Пусть изменения запасов сырья А и В равны 12 и 10 соответственно. Проверьте выполнение условия устойчивости.

10. Найдите новое решение задачи при измененных данных.

Задача 1.4.5.

Для задачи 1.3.1. выполните задания:

1. Составьте двойственную задачу.

2. Опираясь на вид графического решения, найдите двойственные оценки по теореме двойственности.

3. Используя решение задачи симплекс-методом, найдите матрицу устойчивости и выпишите условие устойчивости.

а) б) в) г)

5. Найдите новое решение задачи с помощью матрицы устойчивости.

Задача 1.4.6. Для производства изделий трех видов A, B и C используется три типа производственного оборудования: фрезерное, токарное и шлифоваль­ное. Нормы затрат времени на одно изделие, общий фонд рабочего времени (в станко-часах) для каждого типа оборудования, а так же прибыль от реализации одного изделия указаны в таблице.

а). Найти максимальную прибыль и оптимальный план выпуска изделий, её обеспечивающий (найти ).

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

в). Найти двойственные оценки.

г). Найти матрицу устойчивости.

д). Выписать условие устойчивости двойственных оценок.

е). Найти интервалы устойчивости.

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

Найти двойственные оценки.

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

.

Найти двойственные оценки.

Задача 1.4.9.

Известно оптимальное решение задачи линейного про­граммирования

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

Задача 1.4.10.

Известно оптимальное решение следующей задачи ли­нейного программирования

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

Задача 1.4.11.

В результате решения однородной задачи вида

где и , симплекс-методом была получена заключительная симплекс-таб­лица:

		–2

1) Если при некотором изменении свободных членов выполнено условие устойчивости двойственных оценок, то какие значения может прини­мать ?

2) Будет ли выполнено условие устойчивости двойственных оценок, если свободные члены и изменятся на величины и ?

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

Задача 1.4.12.

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

Численные данные по вариантам приведены в таблице 1.4.12.2. Дополнительные ограничения даны в таблице 1.4.12.3.

Кроме ограничений на сырье имеются статистически обоснованные ограничения на спрос х₁ и х₂. Восемь вариантов таких ограничений занумерованных римскими цифрами I, II,..., VIII приведены в 1-ом столбце таблицы 1.4.12.3. В каждом из вариантов I-VIII имеется три подварианта 1-3 конкретных числовых значений коэффициентов, входящих в эти ограничения. (столбцы 1, 2, 3 таблицы 1.4.12.3.). Таким образом, всего имеется 24 варианта задачи о ресурсах.

Таблица №1.4.12.1

Сырье	Расход сырья на ед. продукции	Запасы сырья	Изменения запаса сырья
A	a1	a2	Amax	A
В	b1	b2	Bmax	B
Прибыль	c1	c2

Таблица №1.4.12.2

№		с1	с2	а1	а2	в1	в2	Аmax	Вmax	A	B
	I, 1									1/2	-2
	I, 2									-2
	I, 3										-3
	II, 1									-2
	II, 2									-2
	II, 3									-3
	III, 1									-2
	III, 2
	III, 3
	IV, 1									-2
	IV, 2										-3
	IV, 3
	V, 1									1/2	-2
	V, 2									-1
	V, 3										-1
	VI, 1										-1
	VI, 2									-1
	VI, 3									-1
	VII, 1									-1
	VII, 2
	VII, 3
	VIII, 1									-1
	VIII, 2										-1
	VIII, 3

Таблица № 1.4.12.3

I:	K   S	6, 5	6, 5
II:	K   S
III:	P   Ap
IV:	Q   Aq	1, 5
V:	K   S	6, 5	6, 5
VI:	K   S
VII:	P   Ap
VIII:	Q   Aq	1, 5

Выполните следующие задания.

1. В соответствии с порядковым номером полученного вами варианта задания, по первым двум столбцам таблицы 1.4.12.2. определите римскую цифру (от I до VIII) Вашего варианта дополнительных ограничений и арабскую цифру (от 1до 3) Вашего подварианта числовых данных.

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

1) введите переменные,

2) определите целевую функцию,

3) запишите ограничения на сырье,

4) выпишите дополнительные ограничения на спрос,

5) запишите целиком, полученную модель задачи ЛП,

6) подставьте числовые данные Вашего варианта.

3. Решите полученную задачу ЛП графически.

4. Решите задачу симплекс-методом.

5. Составьте двойственную задачу ЛП.

6. Определите двойственные оценки по теореме двойственности. Сравните с индексной строкой последней симплекс-таблицы.

7. Проверьте условие устойчивости двойственных оценок.

8. Найдите новое оптимальное решение при измененных данных с помощью матрицы устойчивости.

9. Найдите интервалы устойчивости двойственных оценок при изменении каждого сырья в отдельности.