назад Оглавление вперед


[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]


26

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

Для изготовления единицы продукции вида 1 расходуется ресурсов первого вида, а ресурсов второго вида, а,, ресурсов /-го вида. Поэтому для того чтобы удовлетворить требованиям продавца (предприятие № 1), затраты на ресурсы, используемые для изготовления одной единицы продукции первого вида, должны быть не менее ее цены с\. Иными словами, необходимо выполнение неравенства следующего вида:

Аналогично можно представить ограничения по всем остальным видам продукции 2,3,...,77. Экономико-математическая модель и содержательная интерпретация получаемой таким образом задачи представлена в правой части табл. 4.1

Таблица 4.1

Исходная задача (I)

Двойственная задача (II)

F = qjfi+22+ ->тах (4.1) при ограничениях:

2 = ЬуУх+Ь2У2- + Ьу-тт при ограничениях:

(4.4)

а„х + a„jc, +... + а.х„ < I

(4.2)

И условие неотрицательности

X, >0, >0, х„>0 (4.3)

составить такой план выпуска продукции, при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов

аХ2Уха22У2-- + ш2Уш 2

.\пУ\+2пУ2+-+п,пУп,Сп

И условие неотрицательности

у >0> У2>0,-; у>0 (4.6)

найти такой набор цен ресурсов Y = [у,у2,...,у„)у при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации продукции

Цены ресурсов yi,..,y в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл их названий состоит в том, что в отличие от цен на полученную продукцию, которые достаточно точно могут прогнозироваться, цены ресурсов у,...,у являются

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



Рассмотрим задачи линейного программирования I и II, представленные в табл. 4.1. Эти задачи обладают следующими характеристиками:

1.В первой задаче определяется максимум линейной целевой функции, во второй - минимум.

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

3.Каждая из задач задана в стандартной форме, при этом в задаче максимизации все неравенства вида «<», а в задаче минимизации все неравенства вида «>».

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

Для задачи I А =

Для задачи П. А =

12 22

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

6.Условие неотрицательности переменных имеются в обеих задачах. Задачи (I и II) линейного программирования, обладающие указанными

характеристиками, назьгоаются симметричными взаимодвойственными задачами, В данной главе будем называть их просто двойственными задачами. Задачу (I) еще называют исходной или прямой паре двойственных задач. Исходя из описанных характеристик двойственных задач можно предложить следующее правило формирования двойственной задачи:

1.Привести все неравенства системы к одному виду: если в исходной задаче ищут максимум целевой функции, то все неравенства системы ограничений приводятся к виду «<», а если минимум - к виду «>», для чего неравенства, не удовлетворяющие требованиям, умножают на -1.

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



3.Сформировать матрицу , транспонированную к матрице А.

4.Сформировать двойственную задачу на основании полученной матрицы А[ и условия неотрицательности переменных.

Используя указанную последовательность преобразований, рассмотрим пример формирования двойственной задачи. Пусть исходная (ее также еще назьгоают прямой) задача линейного программирования состоит в определении максимума целевой функции

F = -х, + 32

max

при ограничениях:

-32 >1

+4x2 X, - Х2 < 3 Xi +Х2 >15

X, >0, Х2 >0.

Решение:

1.Так как исходная задача на максимум, то обе части перврго и четвертого неравенства умножим на-1. Получим:

-2xi+3x2<-l -Xi +4x2 <14 Xj - Х2 < 3 -Xj -Х2 <-15.

2.Составим расширенную матрицу системы:

3. Найдем матрицу Al, транспонированную к матрице А

-2 -1 1 -1 -Л 3 4-1-1 3 -1 14 3 -15 Z

А1 =

[Старт] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [ 26 ] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117] [118] [119] [120] [121] [122] [123] [124] [125] [126] [127] [128] [129] [130] [131] [132] [133] [134] [135] [136] [137] [138] [139] [140] [141] [142] [143] [144] [145] [146] [147]