48151 (597384), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

– это значения из столбца В, т.е. , , , .

Свободные (небазисные) переменные .

Итак, = (6; 4; 0; 0; 1; 3),

= = 24.

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

При использовании симплексного метода возможны следующие случаи.

1) Если в оценочной строке симплекс-таблицы оценка = 0 соответствует свободной переменной, то это означает, что ЗЛП имеет не единственный оптимальный план.

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

Задания для самостоятельной работы.

Определить оптимальный план задач, используя симплексный метод решения задач линейного программирования:

а)

max

б)

min

Понятие двойственности

1) Симметричные двойственные задачи

Рассмотрим задачу производственного планирования. Пусть предприятие имеет m видов ресурсов объемом единиц. Эти ресурсы должны быть использованы для выпуска n видов продукции. Пусть – норма потребления i-го вида ресурса на производство единицы j-ой продукции; – цена реализации j-ой продукции; – объем производства j-ой продукции, обеспечивающий предприятию максимальную выручку.

План производства следует составить из условия максимизации общей стоимости продукции при ограничениях на использовании ресурсов

,

Или в краткой форме записи математическая модель задачи имеет вид:

(1)

, (2)

, (3)

Задачу (1) – (3) называют исходной.

По исходным данным задачи (1) – (3) сформируем другую экономическую задачу.

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

• покупатель стремится минимизировать их общую стоимость;

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

Эти требования можно записать в виде следующей ЗЛП:

,

Или в краткой форме записи:

(4)

, (5)

, (6)

Полученную задачу (4) – (6) называют двойственной. Переменные называются двойственными оценками, или теневыми ценами.

Задачи (1) – (3) и (4) – (6) называют парой взаимно двойственных симметричных задач, т. к. они обладают следующими свойствами:

1. Если в одной задаче ищется максимум целевой функции, то в другой – минимум.

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

3. В каждой задаче система ограничений задается в виде неравенств, причем все они одного смысла: если задача на max, то все неравенства содержат знаки « », если на min, то все неравенства содержат знаки « ».

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

5. Число неравенств в системе ограничений одной задачи равно числу переменных другой задачи.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Примечание: Понятие «прямой» и «двойственной» задач условно.

2) Построение модели двойственной задачи

Используя свойства (1–6), покажем на конкретном примере построение двойственной задачи.

Пример. Пусть исходная задача имеет вид:

,

Нужно составить к ней двойственную.

Решение. Запишем расширенную матрицу системы ограничений и транспонируем ее.

	1	–1	2	2			1	2	5	11	2
	2	1	–3	4		АТ=	–1	1	–1	1	3
А =	5	–1	1	3			2	–3	1	2	1
	11	1	2	1			2	4	3	1	min
	2	3	1	max

Теперь запишем двойственную задачу по А^Т с переменными , .

, .

Пример. К заданной задаче записать двойственную:

Решение. Так как задача на min, то все неравенства должны иметь знаки « ». С этой целью второе ограничение умножим на (–1); при этом знак неравенства изменится на противоположный. Теперь задача будет иметь вид:

,

Запишем матрицы А и А^Т.

	1	1	1			1	–2	5
А =	–2	–3	–5		АТ=	1	–3	2
	5	2	min			1	–5	max

Двойственная задача:

, .

3) Применение теорем двойственности к анализу оптимальных решений пары симметричных двойственных задач

Рассмотрим следующую задачу. Предприятие планирует выпускать 3 вида продукции – П₁, П₂, П₃. Для этого оно располагает объемами ресурсов 3-х видов Р₁, Р₂, Р₃. Затраты каждого ресурса на изготовление единицы продукции и цена единицы продукции приведены в таблице:

Пj Рi	П1	П2	П3	Объем
Р1	4	2	1	180
Р2	3	1	1	210
Р3	1	2	5	244
Цена	10	14	12

Требуется:

1. построить модель исходной и двойственной задач;

2. решить исходную задачу симплексным методом;

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

4. дать экономический анализ основным и дополнительным переменным оптимальных решений обеих задач;

5. в ответе записать оптимальные решения обеих задач и значения их целевых функций; указать наиболее дефицитный ресурс и наиболее убыточный вид продукции.

Решение. 1. Построим модель исходной задачи

, .

Здесь х₁, х ₂, х₃ – план выпуска продукции.

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

, .

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

Запишем ее канонический вид:

, .

х ₄, х₅, х₆ – дополнительные и они же базисные переменные. Начальный опорный план (0; 0; 0; 180; 210; 244).

Базис		В		10		14		12		0		0		0
	0	180		4		2		1		1		0		0	90
	0	210		3		1		1		0		1		0	210
	0	244		1		2		5		0		0		1	122
			0		–10		–14		–12		0		0	0		таб. 1

Базис		В	10	14	12	0	0	0
	14	90	2	1	0,5	0,5	0	0	180
	0	120	1	0	0,5	–0,5	1	0	240
	0	64	–3	0	4	–1	0	1	16
		1260	18	0	–5	7	0	0	таб. 2
	14	82	2,375	1	0	0,625	0	–0,125
	0	80	1,375	0	0	0,125	1	–0,625
	12	16	–0,75	0	1	–0,25	0	0,25
		1340	14,25	0	0	5,75	0	1,25	таб. 3

Так как все оценки , то получен оптимальный план:

Характеристики

Список файлов книги