Лабораторная работа №3 по "Основам теории систем" (Теория двойственности в задачах линейного программирования)

  • Просмотров 3165
  • Скачиваний 485
  • Размер файла 192
    Кб

Лабораторная работа № 3 Телешовой Елизаветы, гр. 726, Теория двойственности в задачах линейного программирования. Задача: Для изготовления определенного сплава из свинца, цинка и олова используется сырье из тех же металлов, отличающееся составом и стоимостью. Сырье Содержание в процентах Компоненты 1 2 3 4 5 Свинец 10 10 40 60 70 Цинк 10 30 50 30 20 Олово 80 60 10 10 10 Стоимость, у. е. 4 4,5 5,8 6 7,5 Определить, сколько нужно взять сырья каждого вида,

чтобы изготовить с минимальной себестоимостью сплав, содержащий олова не более 30%, цинка не менее 10%, свинца не более 40%. Решение задачи: Пусть хi – доля сырья i-го вида в единице полученного сплава. Тогда функция цели (себестоимость единицы сплава в у.е.) запишется следующим образом: Система ограничений будет иметь вид: (1). Запишем систему в каноническом виде: (2). Решим поставленную задачу методом искусственного базиса. Для этого

составим расширенную задачу: (3). Составим вспомогательную целевую функцию: из первого ограничения, а из третьего получаем: ; ; Тогда: Запишем начальную симплекс-таблицу: 4 4,5 5,8 6 7,5 0 0 0 M M Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 В M X9 1 1 1 1 1 0 0 0 1 0 1 0 X6 0,8 0,6 0,1 0,1 0,1 1 0 0 0 0 0,3 M X10 0,1 0,3 0,5 0,3 0,2 0 -1 0 0 1 0,1 0 X8 0,1 0,1 0,4 0,6 0,7 0 0 1 0 0 0,4 F -4 -4,5 -5,8 -6 -7,5 0 0 0 0 0 0 FM 1,1 1,3 1,5 1,3 1,2 0 -1 0 0 0 1,1 Оптимальная симплекс-таблица будет иметь вид: 4 4,5 5,8 6 7,5 0 0 0 M M Св Б.П. X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 В 4,5 X2 1,4 1 0 0 0 2 0 0 -0,2 0

0,4 0 X8 0,12 0 0 0,2 0,3 0,6 0 1 -0,46 0 0,12 5,8 X3 -0,4 0 1 1 1 -2 0 0 1,2 0 0,6 0 X7 0,12 0 0 0,2 0,3 -0,4 1 0 0,54 -1 0,32 F -0,02 0 0 -0,2 -1,7 -2,6 0 0 -6,06 0 5,28 FM 0 0 0 0 0 0 0 0 -1 -1 0 Полученное решение будет оптимальным, поскольку все оценки неположительные. Запишем оптимальное решение: и оптимальное значение целевой функции: Экономически полученное решение интерпретируется следующим образом: для получения единицы сплава минимальной себестоимости необходимо взять 40% сырья №2 и 60% сырья №3. При

этом сплав содержит ровно 30% олова, более 20% (точнее, 42%) цинка и менее 40% (28%) свинца. Минимальная себестоимость единицы сплава составляет 5,28 у.е. Математическая модель и экономический смысл двойственной задачи. Задача, двойственная к исходной, строится следующим образом: 1) Исходная задача – на минимум, следовательно, двойственная задача – на максимум. 2) Матрица коэффициентов системы ограничений будет представлять собой