Реферат: Транспортная задача линейного программирования 2

--PAGE_BREAK--
Теорема. Если в оптимальном плане

<img width=«209» height=«25» src=«ref-2_680354862-343.coolpic» v:shapes="_x0000_i1110">                  (7) 

М-задачи (4)-(6) все искусственные переменные <img width=«45» height=«23» src=«ref-2_680355205-136.coolpic» v:shapes="_x0000_i1111">  <img width=«73» height=«21» src=«ref-2_680347758-163.coolpic» v:shapes="_x0000_i1112">, то план <img width=«120» height=«23» src=«ref-2_680355504-221.coolpic» v:shapes="_x0000_i1113"> является оптимальным планом исходной задачи (1)-(3).

Для того чтобы решить задачу с ограничениями, не имеющими предпочтительного вида, вводят искусственный базис и решают расширенную М-задачу, которая имеет начальный опорный план <img width=«180» height=«41» src=«ref-2_680355725-403.coolpic» v:shapes="_x0000_i1114">

Решение исходной задачи симплексным методом путем введения искусственных переменных <img width=«19» height=«23» src=«ref-2_680351276-100.coolpic» v:shapes="_x0000_i1115"> называется сим­плексным методом с искусственным базисом.

Если в результате применения симплексного метода к расширенной задаче получен оптимальный план, в кото­ром все искусственные переменные <img width=«48» height=«24» src=«ref-2_680356228-143.coolpic» v:shapes="_x0000_i1116">, то его первые nкомпоненты дают оптимальный план исходной задачи.
Теорема. Если в оптимальном плане М-задачи хотя бы одна из искусственных переменных отлична от нуля, то исходная задача не имеет допустимых планов, т. е. ее условия несовместны.
3.1 Признаки оптимальности.

Теорема.Пусть исходная задача решается на мак­симум. Если для некоторого опорного плана все оценки <img width=«19» height=«23» src=«ref-2_680356371-103.coolpic» v:shapes="_x0000_i1117"> <img width=«57» height=«25» src=«ref-2_680354011-156.coolpic» v:shapes="_x0000_i1118">неотрицательны, то такой план оптимален.

Теорема.Если исходная задача решается на мини­мум и для некоторого опорного плана все оценки <img width=«19» height=«23» src=«ref-2_680356371-103.coolpic» v:shapes="_x0000_i1119"> <img width=«57» height=«25» src=«ref-2_680354011-156.coolpic» v:shapes="_x0000_i1120"> неположительны, то такой план оптимален.
§4. Понятие двойственности.

Понятие двойственности рассмотрим на примере зада­чи оптимального использования сырья. Пусть на предпри­ятии решили рационально использовать отходы основного производства. В плановом периоде появились отходы сырья mвидов в объемах<img width=«17» height=«23» src=«ref-2_680356889-100.coolpic» v:shapes="_x0000_i1121">единиц <img width=«77» height=«21» src=«ref-2_680356989-164.coolpic» v:shapes="_x0000_i1122">. Из этих отходов, учитывая специализацию предприятия, можно наладить выпуск nвидов неосновной продукции. Обозна­чим через <img width=«19» height=«25» src=«ref-2_680357153-100.coolpic» v:shapes="_x0000_i1123"> норму расхода сырья i-го вида на единицу j-й <img width=«73» height=«21» src=«ref-2_680357253-161.coolpic» v:shapes="_x0000_i1124"> продукции, <img width=«16» height=«25» src=«ref-2_680357414-93.coolpic» v:shapes="_x0000_i1125"> — цена реализации единицы j-й продукции (реализация обеспечена). Неизвестные величи­ны задачи: <img width=«19» height=«25» src=«ref-2_680357507-97.coolpic» v:shapes="_x0000_i1126"> — объемы выпуска j-й продукции, обеспечи­вающие предприятию максимум выручки.

Математическая модель задачи:

                    <img width=«207» height=«23» src=«ref-2_680357604-322.coolpic» v:shapes="_x0000_i1127">          (1)

                    <img width=«196» height=«99» src=«ref-2_680357926-972.coolpic» v:shapes="_x0000_i1128">         (2)

                     <img width=«45» height=«25» src=«ref-2_680352443-140.coolpic» v:shapes="_x0000_i1129">  <img width=«57» height=«25» src=«ref-2_680354011-156.coolpic» v:shapes="_x0000_i1130">                                  (3)

Предположим далее, что с самого начала при изучении вопроса об использовании отходов основного производст­ва на предприятии появилась возможность реализации их некоторой организации. Необходимо установить прикидочные оценки (цены) на эти отходы. Обозначим их <img width=«83» height=«23» src=«ref-2_680359194-163.coolpic» v:shapes="_x0000_i1131">.

Оценки должны быть установлены исходя из следующих требований, отражающих несовпадающие интересы предприятия и организации:

1)     общую стоимость отходов сырья покупающая организация стремится мини­мизировать;

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

Эти требования форма­лизуются в виде следующей ЗЛП.

Требование 1 покупающей организации – минимизация покупки: <img width=«209» height=«23» src=«ref-2_680359357-339.coolpic» v:shapes="_x0000_i1132">           (4)

Требование 2 предприятия, реализующего отходы сырья, можно сформулировать в виде системы ограничений. Предприятие откажется от выпуска каждой единицы продукции первого вида, если <img width=«199» height=«23» src=«ref-2_680359696-312.coolpic» v:shapes="_x0000_i1133">, где левая часть означает выручку за сырьё идущее на единицу продукции первого вида; правая – её цену.

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

<img width=«215» height=«99» src=«ref-2_680360008-1015.coolpic» v:shapes="_x0000_i1134">         (5)

По смыслу задачи оценки не должны быть отрицательными:

<img width=«157» height=«23» src=«ref-2_680361023-270.coolpic» v:shapes="_x0000_i1135">                          (6)

Переменные <img width=«17» height=«23» src=«ref-2_680361293-95.coolpic» v:shapes="_x0000_i1136">  <img width=«77» height=«21» src=«ref-2_680356989-164.coolpic» v:shapes="_x0000_i1137"> называют двойственными оценками или объективно обусловленными оценками.

Задачи (1)-(3) и (4)-(6) называют парой взаимно двойственных ЗПЛ.

Между прямой и двойственной задачами можно установить следующую взаимосвязь:

1.      Если прямая задача на максимум, то двойственная к ней — на минимум, и наоборот.

2.      Коэффициенты <img width=«16» height=«23» src=«ref-2_680361552-92.coolpic» v:shapes="_x0000_i1138"> целевой функции прямой задачи являются свободными членами ограничений двойственной задачи.

3.      Свободные члены <img width=«17» height=«23» src=«ref-2_680356889-100.coolpic» v:shapes="_x0000_i1139"> ограничений прямой задачи являются коэффициентами целевой функции двойст­венной.

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

5.      Если прямая задача на максимум, то ее система ограничений представляется в виде неравенств типа <img width=«13» height=«16» src=«ref-2_680361744-88.coolpic» v:shapes="_x0000_i1140">. Двойственная задача решается на минимум, и ее система ограничений имеет вид неравенств типа <img width=«13» height=«16» src=«ref-2_680361832-87.coolpic» v:shapes="_x0000_i1141">.

6.      Число ограничений прямой задачи равно числу пере­менных двойственной, а число ограничений двойствен­ной — числу переменных прямой.

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

Теорема. Для любых допустимых планов <img width=«96» height=«23» src=«ref-2_680361919-191.coolpic» v:shapes="_x0000_i1142"> и <img width=«99» height=«23» src=«ref-2_680362110-192.coolpic» v:shapes="_x0000_i1143">прямой и двойственной ЗЛП справедливо неравенство <img width=«77» height=«21» src=«ref-2_680362302-188.coolpic» v:shapes="_x0000_i1144">, т.е.

<img width=«140» height=«32» src=«ref-2_680362490-453.coolpic» v:shapes="_x0000_i1145">  (7) – основное неравенство теории двойственности.

Теорема. (критерий оптимальности Канторовича)

Если для некоторых допустимых планов <img width=«19» height=«20» src=«ref-2_680362943-96.coolpic» v:shapes="_x0000_i1146"> и <img width=«19» height=«24» src=«ref-2_680363039-99.coolpic» v:shapes="_x0000_i1147"> пары двойственных задач выполняется неравенство <img width=«92» height=«24» src=«ref-2_680363138-202.coolpic» v:shapes="_x0000_i1148">, то <img width=«19» height=«20» src=«ref-2_680362943-96.coolpic» v:shapes="_x0000_i1149"> и <img width=«19» height=«24» src=«ref-2_680363039-99.coolpic» v:shapes="_x0000_i1150"> являются оптимальными планами соответствующих задач.

Теорема. (малая теорема двойственности)

Для су­ществования оптимального плана любой из пары двойст­венных задач необходимо и достаточно существование допустимого плана для каждой из них.
§5. Основные теоремы двойственности

и их экономическое содержание

Теорема.

Если одна из двойственных задач имеет оптимальное решение, то и другая имеет оптимальное решение, причем экстремальные значения целевых функ­ций равны: <img width=«92» height=«24» src=«ref-2_680363138-202.coolpic» v:shapes="_x0000_i1151">. Если одна из двойственных задач неразрешима вследствие неограниченности целевой функции на множестве допустимых решений, то система ограничений другой задачи противоречива.

Экономическое содержание первой теоремы двойствен­ности состоит в следующем: если задача определения оптимального плана, максимизирующего выпуск продук­ции, разрешима, то разрешима и задача определения оценок ресурсов. Причем цена продукции, полученной при реализации оптимального плана, совпадает с суммар­ной оценкой ресурсов. Совпадение значений целевых функций для соответствующих планов пары двойственных задач достаточно для того, чтобы эти планы были опти­мальными. Это значит, что план производства и вектор оценок ресурсов являются оптимальными тогда и только тогда, когда цена произведенной продукции и суммарная оценка ресурсов совпадают. Оценки выступают как инструмент балансирования затрат и результатов. Двойст­венные оценки, обладают тем свойством, что они гаранти­руют рентабельность оптимального плана, т. е. равенство общей оценки продукции и ресурсов, и обусловливают убыточность всякого другого плана, отличного от опти­мального. Двойственные оценки позволяют сопоставить и сбалансировать затраты и результаты системы.
Теорема. (о дополняющей нежесткости ) 

Для того, чтобы планы <img width=«19» height=«20» src=«ref-2_680362943-96.coolpic» v:shapes="_x0000_i1152"> и <img width=«19» height=«24» src=«ref-2_680363039-99.coolpic» v:shapes="_x0000_i1153"> пары двойственных задач были оптимальны, необходимо и достаточно выполнение условий:

<img width=«221» height=«32» src=«ref-2_680363932-521.coolpic» v:shapes="_x0000_i1154">         (1)

<img width=«221» height=«32» src=«ref-2_680364453-517.coolpic» v:shapes="_x0000_i1155">         (2)

Условия (1), (2) называются условиями допол­няющей нежесткости. Из них следует: если какое-либо ограничение одной из задач ее оптимальным планом обра­щается в строгое неравенство, то соответствующая компо­нента оптимального плана двойственной задачи должна равняться нулю; если же какая-либо компонента опти­мального плана одной из задач положительна, то соответ­ствующее ограничение в двойственной задаче ее опти­мальным планом должно обращаться в строгое равенство.

Экономически это означает, что если по некоторому оптимальному плану <img width=«19» height=«20» src=«ref-2_680362943-96.coolpic» v:shapes="_x0000_i1156"> производства расход i-го ресурса строго меньше его запаса <img width=«17» height=«23» src=«ref-2_680356889-100.coolpic» v:shapes="_x0000_i1157">, то в оптимальном плане соответствующая двойственная оценка единицы это­го ресурса равна нулю. Если же в некотором оптимальном плане оценок его i-я компонента строго больше нуля, то в оптимальном плане производства расход соответствую­щего ресурса равен его запасу. Отсюда следует вывод: двойственные оценки могут служить мерой дефицитности ресурсов. Дефицитный ресурс (полностью используемый по оптимальному плану производства) имеет положитель­ную оценку, а ресурс избыточный (используемый не полно­стью) имеет нулевую оценку.
Теорема .(об оценках).Двойственные оценки пока­зывают приращение функции цели, вызванное малым из­менением свободного члена соответствующего ограниче­ния задачи математического программирования, точнее

<img width=«171» height=«48» src=«ref-2_680365166-389.coolpic» v:shapes="_x0000_i1158">          (3)
§6. Примеры экономических задач
5.1 Задача о наилучшем использовании ресурсов.Пусть некоторая производственная единица (цех, завод, объеди­нение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресур­сов, может выпускать nразличных видов продукции (то­варов), известных под номерами, обозначаемыми индек­сом j<img width=«56» height=«25» src=«ref-2_680365555-155.coolpic» v:shapes="_x0000_i1159">. Ее  будем обозначать <img width=«23» height=«25» src=«ref-2_680365710-111.coolpic» v:shapes="_x0000_i1160">. Предприятие при производстве этих видов продукции должно ограни­чиваться имеющимися видами ресурсов, технологий, дру­гих производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингре­диентами <img width=«21» height=«23» src=«ref-2_680365821-106.coolpic» v:shapes="_x0000_i1161">. Пусть их число равно m; припишем им индекс i  <img width=«59» height=«25» src=«ref-2_680365927-157.coolpic» v:shapes="_x0000_i1162">. Они ограничены, и их количества равны соответственно <img width=«83» height=«23» src=«ref-2_680366084-178.coolpic» v:shapes="_x0000_i1163"> условных единиц. Таким обра­зом, <img width=«135» height=«23» src=«ref-2_680366262-242.coolpic» v:shapes="_x0000_i1164">  — вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпуск­ной цене товара, его прибыльности, издержкам произ­водства, степени удовлетворения потребностей и т. д. При­мем в качестве такой меры, например, цену реализации

<img width=«17» height=«25» src=«ref-2_680366504-93.coolpic» v:shapes="_x0000_i1165"><img width=«56» height=«25» src=«ref-2_680366597-153.coolpic» v:shapes="_x0000_i1166">, т. е. <img width=«149» height=«25» src=«ref-2_680366750-244.coolpic» v:shapes="_x0000_i1167">—вектор цен. Известны также технологические коэффициенты <img width=«19» height=«25» src=«ref-2_680357153-100.coolpic» v:shapes="_x0000_i1168">, кото­рые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов <img width=«19» height=«25» src=«ref-2_680357153-100.coolpic» v:shapes="_x0000_i1169"> называют технологической и обо­значают буквой А. Имеем  <img width=«59» height=«25» src=«ref-2_680367194-164.coolpic» v:shapes="_x0000_i1170">. Обозначим через <img width=«136» height=«25» src=«ref-2_680367358-235.coolpic» v:shapes="_x0000_i1171">план производства, показывающий, какие виды товаров <img width=«109» height=«25» src=«ref-2_680367593-220.coolpic» v:shapes="_x0000_i1172"> нужно произво­дить и в каких количествах, чтобы обеспечить предприя­тию максимум объема реализации при имеющихся ре­сурсах.

Так как <img width=«17» height=«25» src=«ref-2_680366504-93.coolpic» v:shapes="_x0000_i1173"> — цена реализации единицы j'-й продукции, цена реализованных <img width=«19» height=«25» src=«ref-2_680357507-97.coolpic» v:shapes="_x0000_i1174"> единиц будет равна <img width=«32» height=«25» src=«ref-2_680368003-117.coolpic» v:shapes="_x0000_i1175">, а общий объем реализации<img width=«133» height=«23» src=«ref-2_680368120-226.coolpic» v:shapes="_x0000_i1176">

Это выражение — целевая функция, которую нужно мак­симизировать.

Так как <img width=«35» height=«25» src=«ref-2_680368346-124.coolpic» v:shapes="_x0000_i1177"> — расход i-го ресурса на производство <img width=«19» height=«25» src=«ref-2_680357507-97.coolpic» v:shapes="_x0000_i1178"> единиц j-й продукции, то, просуммировав расход i-горесурса на выпуск всех nвидов продукции, получим общий расход этого ресурса, который не должен превосхо­дить <img width=«17» height=«23» src=«ref-2_680368567-101.coolpic» v:shapes="_x0000_i1179"><img width=«59» height=«25» src=«ref-2_680365927-157.coolpic» v:shapes="_x0000_i1180"> единиц:

<img width=«203» height=«25» src=«ref-2_680368825-329.coolpic» v:shapes="_x0000_i1181">

Чтобы искомый план <img width=«160» height=«25» src=«ref-2_680369154-263.coolpic» v:shapes="_x0000_i1182">был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы  <img width=«19» height=«25» src=«ref-2_680357507-97.coolpic» v:shapes="_x0000_i1183"> выпуска продукции:

<img width=«44» height=«25» src=«ref-2_680369514-139.coolpic» v:shapes="_x0000_i1184"> <img width=«56» height=«25» src=«ref-2_680365555-155.coolpic» v:shapes="_x0000_i1185">.

Таким образом, модель задачи о наилучшем использовании ресурсов примет вид:

<img width=«123» height=«32» src=«ref-2_680369808-372.coolpic» v:shapes="_x0000_i1186">                 (1)

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

<img width=«99» height=«32» src=«ref-2_680370180-339.coolpic» v:shapes="_x0000_i1187">  <img width=«59» height=«25» src=«ref-2_680365927-157.coolpic» v:shapes="_x0000_i1188">     (2)

<img width=«44» height=«25» src=«ref-2_680369514-139.coolpic» v:shapes="_x0000_i1189">  <img width=«56» height=«25» src=«ref-2_680365555-155.coolpic» v:shapes="_x0000_i1190">                      (3)

Так как переменные <img width=«19» height=«25» src=«ref-2_680357507-97.coolpic» v:shapes="_x0000_i1191"> входят в функцию <img width=«33» height=«21» src=«ref-2_680371067-122.coolpic» v:shapes="_x0000_i1192"> и систему ограничений только в первой степени, а показатели <img width=«60» height=«25» src=«ref-2_680371189-161.coolpic» v:shapes="_x0000_i1193"> являются постоянными в планируемый период, то (1)-(3) – задача линейного программирования.
5.2 Задача о смесях.

В различных отраслях народного хозяйства возникает проблема составления таких рабочих смесей на основе исходных материалов, которые обеспе­чивали бы получение конечного продукта, обладающего определенными свойствами. К этой группе задач относятся задачи о выборе диеты, составлении кормового рациона в животноводстве, шихт в металлургии, горючих и сма­зочных смесей в нефтеперерабатывающей промышлен­ности, смесей для получения бетона в строительстве и т. д.  Высокий уровень затрат на исходные сырьевые материалы и необходимость повышения эффективности производства выдвигает на первый план следующую задачу: получить продукцию с заданными свойствами при наименьших за­тратах на исходные сырьевые материалы.

5.3 Задача о раскрое материалов.

Сущность задачи об оптимальном раскрое состоит в разработке таких техно­логически допустимых планов раскроя, при которых полу­чается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму. Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.

5.4 Транспортная задача.

Рассмотрим простейший ва­риант модели транспортной задачи, когда речь идет о рациональной перевозке некоторого однородного продукта от производителей к потребителям; при этом имеется ба­ланс между суммарным спросом потребителей и возмож­ностями поставщиков по их удовлетворению. Причем по­требителям безразлично, из каких пунктов производства будет поступать продукция, лишь бы их заявки были пол­ностью удовлетворены. Так как от схемы прикрепления потребителей к поставщикам существенно зависит объем транспортной работы, возникает задача о наиболее рацио­нальном прикреплении, правильном направлении перево­зок грузов, при котором потребности полностью удовлетворяются, вся продукция от поставщиков вывозится, а затраты на транспортировку минимальны.

5.5 Задача о размещении заказа.

Речь идет о задаче рас­пределения заказа (загрузки взаимозаменяемых групп оборудования) между предприятиями (цехами, станками, исполнителями) с различными производственными и тех­нологическими характеристиками, но взаимозаменяемыми в смысле выполнения заказа. Требуется составить план размещения заказа (загрузки оборудования), при кото­ром с имеющимися производственными возможностями заказ был бы выполнен, а показатель эффективности до­стигал экстремального значения.    продолжение
--PAGE_BREAK--
§7. Анализ задачи об оптимальном использовании сырья.
Исходя из специализации и своих технологических возможностей  предприятие может выступать четыре вида продукции. Сбыт любого количества обеспечен. Для изготовления этой продукции используются трудовые ресурсы, полуфабрикаты и станочное оборудование. Общий объём ресурсов, расход каждого ресурса за единицу продукции, приведены в таблице 1. Требуется определить план выпуска, доставляющий предприятию максимум прибыли. Выполнить после оптимизационный анализ решения и параметров модели.



Ресурсы

Выпускаемая продукция

Объём

Ресурсов

<img width=«21» height=«23» src=«ref-2_680371350-106.coolpic» v:shapes="_x0000_i1194">

<img width=«23» height=«23» src=«ref-2_680371456-109.coolpic» v:shapes="_x0000_i1195">

<img width=«21» height=«24» src=«ref-2_680371565-109.coolpic» v:shapes="_x0000_i1196">

<img width=«23» height=«23» src=«ref-2_680371674-109.coolpic» v:shapes="_x0000_i1197">

<img width=«16» height=«23» src=«ref-2_680371783-99.coolpic» v:shapes="_x0000_i1198">

Трудовые ресурсы, чел-ч

4

2

2

8

4800

<img width=«17» height=«23» src=«ref-2_680371882-100.coolpic» v:shapes="_x0000_i1199">

Полуфабрикаты, кг

2

10

6

0

2400

<img width=«17» height=«24» src=«ref-2_680371982-100.coolpic» v:shapes="_x0000_i1200">

Станочное оборудование, станко-ч

1

0

2

1

1500

Цена единицы продукции, р.

65

70

60

120

 

Решение.

Пусть <img width=«83» height=«24» src=«ref-2_680372082-171.coolpic» v:shapes="_x0000_i1201"> — объёмы продукции <img width=«103» height=«24» src=«ref-2_680372253-221.coolpic» v:shapes="_x0000_i1202">планируемый к выпуску; <img width=«15» height=«17» src=«ref-2_680342942-91.coolpic» v:shapes="_x0000_i1203"> — сумма ожидаемой выручки.

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

<img width=«240» height=«125» src=«ref-2_680372565-1372.coolpic» v:shapes="_x0000_i1204">

Математическая модель двойственной задачи:

<img width=«229» height=«24» src=«ref-2_680373937-402.coolpic» v:shapes="_x0000_i1205">

<img width=«148» height=«99» src=«ref-2_680374339-881.coolpic» v:shapes="_x0000_i1206">

<img width=«129» height=«23» src=«ref-2_680375220-219.coolpic» v:shapes="_x0000_i1207">

По условиям примера найти:

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

2.      Оценки ресурсов, используемых при производстве продукции.
Симплексным методом решаем прямую задачу, модель которой составлена выше в таблице1.

После второй итерации все оценки оказались отрицательными, значит, найденный опорный план является оптимальным: <img width=«176» height=«24» src=«ref-2_680375439-332.coolpic» v:shapes="_x0000_i1208">,  <img width=«131» height=«24» src=«ref-2_680375771-248.coolpic» v:shapes="_x0000_i1209">

Основные переменные <img width=«221» height=«25» src=«ref-2_680376019-362.coolpic» v:shapes="_x0000_i1210">показывают, что продукцию<img width=«23» height=«23» src=«ref-2_680376381-109.coolpic» v:shapes="_x0000_i1211">и <img width=«24» height=«23» src=«ref-2_680376490-109.coolpic» v:shapes="_x0000_i1212"> выпускать нецелесообразно, а продукции <img width=«24» height=«24» src=«ref-2_680376599-110.coolpic» v:shapes="_x0000_i1213"> следует произвести 400 ед., <img width=«24» height=«23» src=«ref-2_680376709-109.coolpic» v:shapes="_x0000_i1214"> — 500 ед. 

Дополнительные переменные <img width=«16» height=«23» src=«ref-2_680376818-100.coolpic» v:shapes="_x0000_i1215">и <img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1216"> показывают, что ресурсы используются полностью <img width=«91» height=«25» src=«ref-2_680377019-197.coolpic» v:shapes="_x0000_i1217">, а вот равенство <img width=«63» height=«25» src=«ref-2_680377216-163.coolpic» v:shapes="_x0000_i1218"> свидетельствует о том, что 200 единиц продукции <img width=«17» height=«24» src=«ref-2_680371982-100.coolpic» v:shapes="_x0000_i1219"> осталось неиспользованным.


Номера ит.

БП

Сб

<img width=«23» height=«24» src=«ref-2_680377479-107.coolpic» v:shapes="_x0000_i1220">

<img width=«19» height=«23» src=«ref-2_680343033-96.coolpic» v:shapes="_x0000_i1221">

<img width=«20» height=«23» src=«ref-2_680377682-96.coolpic» v:shapes="_x0000_i1222">

<img width=«19» height=«24» src=«ref-2_680377778-96.coolpic» v:shapes="_x0000_i1223">

<img width=«20» height=«23» src=«ref-2_680377874-97.coolpic» v:shapes="_x0000_i1224">

<img width=«20» height=«24» src=«ref-2_680377971-97.coolpic» v:shapes="_x0000_i1225">

<img width=«20» height=«24» src=«ref-2_680378068-97.coolpic» v:shapes="_x0000_i1226">

<img width=«20» height=«24» src=«ref-2_680378165-95.coolpic» v:shapes="_x0000_i1227">

65

70

60

120

0

0

0

0

<img width=«20» height=«24» src=«ref-2_680377971-97.coolpic» v:shapes="_x0000_i1228">

0

4800

4

2

2

8

1

0

0

<img width=«20» height=«24» src=«ref-2_680378068-97.coolpic» v:shapes="_x0000_i1229">

0

2400

2

10

6

0

0

1

0

<img width=«20» height=«24» src=«ref-2_680378165-95.coolpic» v:shapes="_x0000_i1230">

0

1500

1

0

2

1

0

0

1

<img width=«44» height=«25» src=«ref-2_680378549-124.coolpic» v:shapes="_x0000_i1231">

0

-65

-70

-60

-120

0

0

0

1

<img width=«20» height=«23» src=«ref-2_680377874-97.coolpic» v:shapes="_x0000_i1232">

120

600

1/2

1/4

1/4

1

1/8





<img width=«20» height=«24» src=«ref-2_680378068-97.coolpic» v:shapes="_x0000_i1233">

0

2400

2



6





1



<img width=«20» height=«24» src=«ref-2_680378165-95.coolpic» v:shapes="_x0000_i1234">

0

900

1/2

-1/4

7/4



-1/8



1

<img width=«44» height=«25» src=«ref-2_680378549-124.coolpic» v:shapes="_x0000_i1235">

72000

-5

-40

-30



15





2

<img width=«20» height=«23» src=«ref-2_680377874-97.coolpic» v:shapes="_x0000_i1236">

120

500

5/12

-1/6



1

1/8

-1/24



<img width=«19» height=«24» src=«ref-2_680377778-96.coolpic» v:shapes="_x0000_i1237">

60

400

1/3

5/3

1





1/6



<img width=«20» height=«24» src=«ref-2_680378165-95.coolpic» v:shapes="_x0000_i1238">



200

-1/12

-19,6





-1/8

-7/24

1

<img width=«44» height=«25» src=«ref-2_680378549-124.coolpic» v:shapes="_x0000_i1239">

84000

5

10





15

5




Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи – двойственные оценки. В канонической форме прямой задачи переменные <img width=«84» height=«24» src=«ref-2_680379498-172.coolpic» v:shapes="_x0000_i1240">  — являются свободными, а дополнительные переменные <img width=«64» height=«24» src=«ref-2_680379670-149.coolpic» v:shapes="_x0000_i1241"> — базисными. В канонической форме двойственной задачи свободными будут переменные <img width=«67» height=«24» src=«ref-2_680379819-153.coolpic» v:shapes="_x0000_i1242"> — а базисными <img width=«89» height=«24» src=«ref-2_680379972-178.coolpic» v:shapes="_x0000_i1243">

Соответствие между переменными примет вид

<img width=«131» height=«72» src=«ref-2_680380150-599.coolpic» v:shapes="_x0000_i1244">    

Учитывая это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана <img width=«137» height=«24» src=«ref-2_680380749-270.coolpic» v:shapes="_x0000_i1245">  — двойственные оценки.

minf= maxZ=84000.

Запишем это неравенство в развернутой форме:

48000*15 + 2400*5 + 1500*0 = 65*0 + 70*0 + 60*400 + 120*500

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

При оптимальном плане оценка ресурсов, затраченных на выпуск продукции, совпадает с оценкой произведенной продукции.  

Теперь  установим степень дефицитно­сти используемых ресурсов и обоснуем рентабельность оптимального плана.

Мы нашли оптимальный план <img width=«176» height=«24» src=«ref-2_680375439-332.coolpic» v:shapes="_x0000_i1246">выпуска продукции. При этом плане третье ограничение прямой задачи выполняется как строгое неравенство:

0+2-400+500= 1300< 1500. Это означает, что расход ресурса <img width=«17» height=«24» src=«ref-2_680371982-100.coolpic» v:shapes="_x0000_i1247"> мень­ше его запаса, т. е. ресурс <img width=«17» height=«24» src=«ref-2_680371982-100.coolpic» v:shapes="_x0000_i1248"> избыточный. Именно поэтому в оптималь­ном плане <img width=«137» height=«24» src=«ref-2_680380749-270.coolpic» v:shapes="_x0000_i1249"> двойственной задачи оценка <img width=«19» height=«25» src=«ref-2_680381821-104.coolpic» v:shapes="_x0000_i1250"> этого ресурса равна нулю.

А вот оценки <img width=«19» height=«24» src=«ref-2_680381925-104.coolpic» v:shapes="_x0000_i1251"> и <img width=«20» height=«24» src=«ref-2_680382029-105.coolpic» v:shapes="_x0000_i1252"> ресурсов <img width=«16» height=«23» src=«ref-2_680376818-100.coolpic» v:shapes="_x0000_i1253"> и <img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1254"> выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограни­чения по этим ресурсам выполняются как строгие равен­ства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.

Поскольку 15>5, ресурс <img width=«16» height=«23» src=«ref-2_680376818-100.coolpic» v:shapes="_x0000_i1255"> считается более дефицитным, чем ресурс <img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1256">.

На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в опти­мальный план продукция <img width=«23» height=«23» src=«ref-2_680376381-109.coolpic» v:shapes="_x0000_i1257">и <img width=«24» height=«23» src=«ref-2_680376490-109.coolpic» v:shapes="_x0000_i1258">: первое и второе ограничения двой­ственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.

Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции <img width=«23» height=«23» src=«ref-2_680376381-109.coolpic» v:shapes="_x0000_i1259"> и <img width=«24» height=«23» src=«ref-2_680376490-109.coolpic» v:shapes="_x0000_i1260">, превышают оценки единицы этой продукции. Понятно, что такую продукцию выпу­скать предприятию невыгодно. Что же касается продукции <img width=«24» height=«24» src=«ref-2_680376599-110.coolpic» v:shapes="_x0000_i1261"> и <img width=«24» height=«23» src=«ref-2_680376709-109.coolpic» v:shapes="_x0000_i1262"> <img width=«100» height=«25» src=«ref-2_680383191-227.coolpic» v:shapes="_x0000_i1263">,то выпуск ее оправдан, поскольку оценка израсходо­ванных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.

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

Рассмотрим возможность дальней­шего совершенствования оптимального ассортимента выпускаемой про­дукции.

Выше установлено, что ресурсы <img width=«16» height=«23» src=«ref-2_680376818-100.coolpic» v:shapes="_x0000_i1264"> и <img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1265"> являются дефицитными. В связи с этим на основе теоремы (об оценках) можно утверждать, что на каждую единицу ресурса <img width=«16» height=«23» src=«ref-2_680383619-99.coolpic» v:shapes="_x0000_i1266">, введенную дополнительно в производ­ство, будет получена дополнительная выручка <img width=«29» height=«23» src=«ref-2_680383718-120.coolpic» v:shapes="_x0000_i1267">, численно равная <img width=«19» height=«24» src=«ref-2_680383838-101.coolpic» v:shapes="_x0000_i1268">.В самом деле, при <img width=«49» height=«23» src=«ref-2_680383939-143.coolpic» v:shapes="_x0000_i1269">получаем <img width=«149» height=«24» src=«ref-2_680384082-278.coolpic» v:shapes="_x0000_i1270">. По тем же причинам каждая дополнительная единица ресурса<img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1271">обеспечит прирост <img width=«32» height=«23» src=«ref-2_680384461-123.coolpic» v:shapes="_x0000_i1272"> выручки, равный 5 р. Теперь становится понятно, почему ресурс <img width=«19» height=«23» src=«ref-2_680376918-101.coolpic» v:shapes="_x0000_i1273">считается более дефицитным по сравнению с ресурсом <img width=«16» height=«23» src=«ref-2_680376818-100.coolpic» v:shapes="_x0000_i1274">: он может содействовать получению большей выручки.

Что же касается избыточного ресурса <img width=«17» height=«24» src=«ref-2_680371982-100.coolpic» v:shapes="_x0000_i1275">    продолжение
--PAGE_BREAK--