Решение задач по экономике (Вариант 4)

Для прямой задачи линейного программирования составить двойственную. Найти оптимальные решения задач.

Решение

1) Составим математическую модель двойственной задачи. Так как прямая задача является задачей максимизации, то двойственная задача будет задачей минимизации. Система ограничений прямой задачи состоит из двух ограничений. Следовательно, в двойственной задаче будут две переменные . Составляем систему ограничений двойственной задачи. Матрица коэффициентов при неизвестных в неравенствах двойственной задачи получается транспонированием матрицы коэффициентов прямой задачи, неравенства меняются на противоположные, а свободные члены совпадают с коэффициентами целевой функции прямой задачи. Если переменная прямой задачи х_i ≥ 0, то i-е условие системы ограничений двойственной задачи является неравенством. Если j-е соотношение прямой задачи является неравенством, то соответствующая переменная у_j ≥ 0. Запишем систему ограничений прямой задачи в стандартном виде, т.е. в задаче на максимум все ограничения вида ≤: Система ограничений прямой задачи записана в стандартном виде, т.е. в задаче на максимум все ограничения вида ≤. Поэтому в двойственной задаче на минимум все ограничения будут вида  ≥. Следовательно, система ограничений двойственной задачи имеет вид: Коэффициентами в целевой функции двойственной задачи будут свободные члены в системе ограничений прямой задачи. Записываем математическую модель двойственной ЗЛП: Математическая модель двойственной задачи составлена. 2) Решим двойственную задачу графическим методом. Построим множество допустимых решений или, что то же самое, область допустимых решений. Построим каждую прямую и определим полуплоскости, заданные неравенствами (рис. 1). Построим уравнение  по двум точкам.

	у1	у2
Первая точка	0	6
Вторая точка	12	0

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

	у1	у2
Первая точка	1	2
Вторая точка	0,5	1

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

	у1	у2
Первая точка	1	0,5
Вторая точка	2	1

  Определим полуплоскость, задаваемую неравенством:  в полуплоскости выше прямой. Рис. 1. Область допустимых решений Обозначим границы области многоугольника решений. При анализе рис. 1 можем сделать вывод, что областью допустимых решений (ОДР) является незамкнутая область, обозначенная точками ABCD. Рассмотрим целевую функцию задачи: Построим прямую, отвечающую значению функции : Вектор-градиент , составленный из коэффициентов  целевой функции, указывает направление максимизации . Начало вектора – точка (0; 0), конец – точка (-1; 4). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией (рис. 2). Рис. 2. Прямая целевой функци Прямая   пересекает область в точке С. Так как точка С получена в результате пересечения прямых, заданных уравнениями  и , то ее координаты удовлетворяют уравнениям этих прямых. Решаем систему уравнений: Решив систему уравнений, получили: у₁ = 6;                 у₂ = 3. Найдем минимальное значение целевой функции: Ответ. Таким образом, оптимальное решение двойственной задачи:   и оптимальное значение целевой функции двойственной задачи . 3) По решению двойственной задачи найдем оптимальное решение исходной. Рассмотрим вторую теорему двойственности (теорему о «дополняющей нежесткости»):  Пусть  – допустимое решение прямой задачи, а   – допустимое решение двойственной задачи. Для того, чтобы они были оптимальными решениями соответствующих взаимодвойственных задач, необходимо и достаточно, чтобы выполнялись следующие соотношения: Это условия «дополняющей нежесткости». Из них следует: если какое-либо неравенство системы ограничений одной из задач не обращается в тождество оптимальным планом этой задачи, то соответствующая компонента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента оптимального плана одной из задач положительна, то соответствующее ограничение в двойственной задаче ее оптимальным планом должно обращаться в тождество, то есть: Если , то . Если , то Подставим оптимальное решение двойственной задачи в систему ограниченной математической модели: Первое и третье ограничения двойственной задачи выполняются как равенства. Это означает, что согласно второй теореме двойственности х₁ ≠ 0 и х₃ ≠ 0. Второе ограничение выполняется как строгое неравенство, поэтому    х₂ = 0. Поскольку в оптимальном плане двойственной задачи у₁>0 и у₂>0, то первое ограничение в прямой задаче будет равенством. Таким образом, при применении теорем двойственности решение прямой задачи сводится к решению уравнений при следующих условиях: Таким образом, оптимальное решение прямой задачи можно записать так: x₁ = 0,5;              x₂ = 0;                  x₃ = 1,5. Таким образом, видим, что основной принцип двойственности выполняется: . Ответ. Оптимальное решение прямой задачи: ; .