3. Следствия из теоремы двойственности

Теорема существования. Для того чтобы в задачах I и I* существовали оптимальные векторы и значения функций μ(x) и ν(у) на этих векторах совпадали, т.е. имел место случай 1⁰ теоремы двойственности, достаточно выполнения любого из следующих условий:

α) в основной и двойственной задачах имеются допустимые векторы;

β) в основной задаче имеются допустимые векторы и линейная функция μ(x) на множестве этих векторов ограничена сверху;

γ) в двойственной задаче имеются допустимые векторы и линейная функция ν(у) на множестве этих векторов ограничена снизу;

δ) в основной задаче существует оптимальный вектор;

ε) в двойственной задаче существует оптимальный вектор.

Признак оптимальности. Достаточные признаки оптимальности в краткой и развернутой формах являются так же необходимыми.

4. Упражнения

1. Заданы задачи ЛП. Записать двойственные к ним задачи.

Задача 1.1. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.2. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.3. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.4. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.5. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.6. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.7. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1. 8. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.9. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.10. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.11. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.12. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.13. Минимизировать , на множестве векторов , удовлетворяющих

;

Задача 1. 14. Максимизировать , на множестве векторов , удовлетворяющих

;

Задача 1.15. Минимизировать , на множестве векторов , удовлетворяющих

;

II. В следующих задачах проверить, какой из указанных векторов является оптимальным.

Задача 2.1. Максимизировать на множестве векторов , удовлетворяющих следующим условиям:

Задача 2.2. Максимизировать на множестве векторов , удовлетворяющих условиям:

Задача 2.3. Максимизировать на множестве векторов , удовлетворяющих условиям:

Задача 2.4. Максимизировать на множестве векторов удовлетворяющих условиям:

Задача 2.5. Максимизировать на множестве векторов удовлетворяющих условиям:

Задача 2.6. Исследовать на оптимальность вектор для задачи:

Максимизировать на множестве векторов , удовлетворяющих следующим условиям:

Задача 2.7. Исследовать на оптимальность вектор х = (1,2,1,2,0,0) для задачи:

Максимизировать на множестве векторов , удовлетворяющих условиям:

III. На основании графического анализа исследовать следующие задачи и, в случае разрешимости, найти экстремальное решение целевой функции

Задача 3.1. Максимизировать на множестве векторов , удовлетворяющих условиям:

Задача 3.2. Максимизировать на множестве векторов х = ( ), удовлетворяющих условиям:

Задача 3.3. Максимизировать на множестве векторов , удовлетворяющих условиям:

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

Задача 4.1. На хлебокомбинате для изготовления хлебопродуктов двух видов (Хлеб Бородинский и Булка «К чаю») используется мука двух сортов, сахар и отруби. В таблице 3 указаны нормы расходов муки, сахара и отрубей, а иакже цена единицы каждого продукта, имеющегося в распоряжении комбината.

Таблица 3

Ресурсы	Нормы затрат ресурсов на ед. товара		Общее количество ресурсов
	Бородинский хлеб	Булка «К чаю»
Мука
I сорт	0,8	0,6	150
II сорт	0,35	0,3	200
Сахар (кг)	0,17	0,3	220
Отруби (кг)	0,32	0	150
Цена за ед. товара	10	8	-

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

Задача 4.2. Сельскохозяйственное предприятие выращивает культуры двух сортов, А и В. Для выращивания каждого сорта необходимы удобрения трёх видов, I, II и III. Однако количество каждого вида удобрений ограничено.

Прибыли от продажи единицы первого сорта – 80 р, второго – 70р. Необходимо составить план выращивания культур при котором общая прибыль от продажи будет максимальной.

В таблице 4 приведены расходы каждого вида удобрений на единицу каждого сорта:

Таблица 4

Вид удобрений	Сорт культуры		Затраты удобрений
	А	В
I	2	1,5	60
II	1,5	4	60
III	3	1	75
Выручка	80	70

Задача 4.3.Мебельная фабрика выпускает книжные полки и шкафы .Их производство ограничено наличием необходимых ресурсов(древесно-стружечных плит(ДСП),высококачественных досок (ВД)и стекла).

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

Таблица 5

Виды ресурсов	Виды продукции		Запасы ресурсов
	Полки	Шкафы
ДСП	3	2	27
ВД	2	4	28
Стекло	2	3	23
Прибыль:	4	7

Задача 4.4. Стальные прутья необходимо разрезать на заготовки длиной 45, 35 и 50 см. Требуемое количество заготовок данного вида составляет соответственно 40, 30 и 20 шт. Возможные варианты разреза и величина отходов при каждом из них приведены в таблице 6.

Таблица 6

Длина заготовок (см)	Варианты разреза
	I	II
45	2	4
35	5	2
50	2	2
Величина отходов (см)	20	30

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

Задача 4.5. При производстве 2-х видов изделий используется 4 вида сырья. Нормы расхода сырья каждого вида на изготовление единицы изделия приведены в таблице 7. Там же указана прибыль от реализации одного изделия каждого вида и общее количество сырья каждого вида.

Таблица 7

Вид сырья	Нормы расхода сырья		Общее количество сырья
	I	II
1	4	2	200
2	2	8	400
3	4	4	400
Прибыль	3	3

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