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

, т. е.  —вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i–го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах.

Так как  - цена реализации единицы j'-й продукции, цена реализованных единиц будет равна , а общий объем реализации

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

Так как  - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц:

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

  .

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

                 (1)

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

       (2)

                        (3)

Так как  переменные входят в функцию и систему ограничений только в первой степени, а показатели являются постоянными в планируемый период, то (1)-(3) – задача линейного программирования. 

5.2 Задача о смесях.

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

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

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

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

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

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

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

§7. Анализ задачи об оптимальном использовании сырья. 

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

 
 

Решение.

Пусть - объёмы продукции планируемый к выпуску; - сумма ожидаемой выручки.

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

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

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

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

 

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

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

Основные  переменные показывают, что продукцию и выпускать нецелесообразно, а продукции следует произвести 400 ед., - 500 ед. 

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

 
 
 

Выпишем из таблицы2. Компоненты оптимального плана двойственной задачи – двойственные оценки. В канонической форме прямой задачи переменные - являются свободными, а дополнительные переменные - базисными. В канонической форме двойственной задачи свободными будут переменные - а базисными

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

    

Учитывая  это соответствие, выпишем из индексной строки последней итерации компоненты искомого плана - двойственные оценки.

min f = max Z =84000.

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

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

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

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

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

Мы нашли  оптимальный план выпуска продукции. При этом плане третье ограничение прямой задачи выполняется как строгое неравенство:

0+2-400+500= 1300< 1500. Это означает, что расход  ресурса меньше его запаса, т. е. ресурс избыточный. Именно поэтому в оптимальном плане двойственной задачи оценка этого ресурса равна нулю.

А вот  оценки и ресурсов и выражаются положительными числами 15 и 5, что свидетельствует о дефицитности этих ресурсов: они при оптимальном плане используются полностью. В самом деле, ограничения по этим ресурсам выполняются как строгие равенства: 4.0+2.0+2.400+8.500=4800, 2-0+10.0+6.400=2400.

Поскольку 15>5, ресурс считается более дефицитным, чем ресурс .

На основе теоремы (о дополняющей нежесткости) нетрудно объяснить, почему не вошла в оптимальный план продукция и : первое и второе ограничения двойственной задачи выполняются как строгие неравенства: 4-15+2-5+0>65, 2-15+10*5>70.

Это означает, что оценки ресурсов, расходуемых на изготовление единицы продукции и , превышают оценки единицы этой продукции. Понятно, что такую продукцию выпускать предприятию невыгодно. Что же касается продукции и , то выпуск ее оправдан, поскольку оценка израсходованных ресурсов совпадает с оценкой произведенной продукции: 2*15+ +6*5+2*0=60, 8*15+0=120.

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

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

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

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

Выясним экономический смысл оценок продукции , , , .

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

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

Что же касается продукции  и являющейся, как установлено выше, убыточной, а потому и не вошедшей в оптимальный план, то для ее оценок и получаем:

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

§8. Программа и расчеты. 

{Программа  составлена для решения задачи  линейного программирования