Выбери формат для чтения
Загружаем конспект в формате docx
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Практическое занятие посвящено примерам различных форм записи экономико-математических моделей в виде ЗЛП.
Приведем к канонической форме рассмотренную ранее задачу производственного планирования (о кондитерской фабрике). В этой задаче обе переменные неотрицательны, но остальные три ограничения представляют собой неравенства. Следовательно, необходимо ввести три дополнительные переменные. Обозначим их соответственно х3, х4 и х5. Тогда задача примет вид:
max 108х1 + 140х2
0,8х1 + 0,5х2+ х3 = 800
0,2х1 + 0,4х2+ х4 = 600
0,01х1 + 0,1х2 + х5 = 120
х1-5 0
Каков экономический смысл новых переменных? Каждая из них показывает, на сколько левая часть может быть меньше правой, т.е. на сколько расход ресурса может быть меньше, чем его запас. Таким образом, дополнительная переменная в задаче производственного планирования представляет собой неизрасходованный остаток ресурса:
х3 – неизрасходованный остаток сахарного песка, т;
х4 - неизрасходованный остаток патоки, т;
х5 - неизрасходованный остаток фруктового пюре, т.
Рассмотрим запись и такой задачи в матричной форме:
С = (108; 140; 0; 0; 0); B = ; A = ; X = ;.
До приведения к канонической форме модель производственного планирования (задача о кондитерской фабрике) имела стандартную форму:
max 108х1 + 140х2
0,8х1 + 0,5х2 800
0,2х1 + 0,4х2 600
0,01х1 + 0,1х2 120
х1,2 0
Запишем ее в матричной форме:
С = (108; 140); B = ; A = ; X = ;.
Рассмотрим несколько других примеров.
Возьмем задачу на max, содержащую три ограничения на три переменных:
max х1 + 2х2 + х3
3х1 + х2 - х3 8
х1 - 2х2 + 4х3 = 5
2х1 + 2х2 + х3 10
х1,2 0
Приведем эту задачу к канонической форме. Отметим, что на знак переменной х3 никаких ограничений не накладывается. Поэтому заменим неограниченную по знаку переменную на разность двух неотрицательных (х3 = х3` - х3``; х3`, х3`` 0). Кроме того, в задаче присутствуют два неравенства, поэтому введем две дополнительные переменные х4 и х5. С их помощью преобразуем первое и последнее ограничения. Задача в канонической форме примет вид:
max х1 + 2х2 + х3` - х3``
3х1 + х2 - х3` + х3``+ х4 = 8
х1 - 2х2 + 4х3` - 4х3``= 5
2х1 + 2х2 + х3` - х3``- х5 = 10
х1,2,4,5, х3`, х3`` 0
Запишем эту задачу в канонической форме в матричной форме. Отметим, что в задаче теперь шесть переменных. Следовательно, вектора С и Х будут включать по шесть компонент, а в матрице А будет шесть столбцов. В первых двух столбцах будут стоять коэффициенты при переменных х1 и х2, в третьем и четвертом – при х3` и х3``, а в двух последних – при дополнительных переменных. Итак, введем следующие обозначения:
С = (1; 2; 1; -1; 0; 0); B = ; A = ; X = .
Матричная форма записи примет вид: .
Приведем эту же задачу:
max х1 + 2х2 + х3
3х1 + х2 - х3 8
х1 - 2х2 + 4х3 = 5
2х1 + 2х2 + х3 10
х1,2 0
- к стандартной форме на минимум.
При этом потребуется точно такая же замена переменной
(х3 = х3` - х3``; х3`, х3`` 0). Целевую функцию необходимо минимизировать, поэтому умножим выражение в целевой функции на (-1). Чтобы все ограничения системы имели вид неравенств со знаком , необходимо обе части первого ограничения умножить на (-1) (тогда поменяется знак). Второе ограничение (уравнение) заменим на два неравенства («равно» - это «не больше» и «не меньше» одновременно; и в неравенстве со знаком «не больше» надо тоже умножить на (-1) обе части и поменять знак). Задача в стандартной форме примет вид:
min -х1 - 2х2 - х3` + х3``
-3х1 - х2 + х3` - х3`` -8
х1 - 2х2 + 4х3` - 4х3`` 5
-х1 + 2х2 - 4х3` + 4х3`` -5
2х1 + 2х2 + х3` - х3`` 10
х1-2, х3`, х3`` 0
Запишем эту задачу в стандартной форме в матричной форме:
С = (-1; -2; -1; 1); B = ; A = ; X = .
Матричная форма записи примет вид:.