Проверка задачи на разрешимость

Методические указания для лабораторных занятий

Транспортные задачки. Способ потенциалов.

Задачки о назначениях

Направление подготовки 080200 Менеджмент

Профиль подготовки (бакалавриат)

Производственный менеджмент

Квалификация (степень) выпускника

Бакалавр

Уфа 2012

УДК 519.86

ББК 65.23

Л 12

Рекомендовано к изданию методической комиссией экономического факультета (протокол № ___от __________ 2010 г.)

Составитель: доцент Шатова В.С.

Рецензент: ст. педагог кафедры информатики и ИТ Саитова Э.С.

Ответственный за выпуск:

зав Проверка задачи на разрешимость.кафедрой статистики и информационных систем в экономике

д.э.н., доктор Рафикова Н.Т.

ОГЛАВЛЕНИЕ

Введение

1 Цель и задачки………………………………………….………………….. 4

2 Методика решения транспортной задачки линейного программирования

способом потенциалов………………………………..…………….…………5

2.1 Последовательность решения задачки………………………………..…5

2.1.1 Проверка задачки на разрешимость………………………………. 5

2.1.2 Построение матрицы задачки…………………………………… .. 6

2.1.3Решение задачки способом потенциалов…………..….…….…… 6

2.1.4Реализация способа потенциалов…………………………………7

2.1.5Экономический смысл решения…………………………………14

3 Вопросы для самоконтроля……………………………………………… .15

Библиографический Проверка задачи на разрешимость перечень………………………………………….……...16

ВВЕДЕНИЕ

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

Общая постановка задачки формулируется последующим образом:
имеется m поставщиков с припасами Ai единиц груза и n потребителей с по­-
требностями в грузах Вj). Известны расстояния от каждого поставщика до
каждого потребителя: С i Проверка задачи на разрешимость j (где i - номер поставщика, j - номер потребите-
ля). Найти, от какого поставщика до какого потребителя и сколько
единиц груза нужно перевезти, чтоб вывезти весь груз от всех поставщи-
ков, удовлетворить потребности всех потребителей и при всем этом общие за­
растраты на транспортировку могли быть наименьшими, т.е. составить опти-.
мальный Проверка задачи на разрешимость план перевозок.

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

1 ЦЕЛЬ И Задачки

Цель: Освоить методику решения транспортных задач линейного программирования способом потенциалов.

Задачки: 1 Научиться математически формулировать задачки распределительного типа.

2 Уяснить метод способа потенциалов.

3 Решить транспортную задачку способом Проверка задачи на разрешимость потенциалов.

4 Сконструировать короткие выводы по результатам решения задачки.

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

2 МЕТОДИКА РЕШЕНИЯ ТРАНСПОРТНОЙ Задачки ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Способом ПОТЕНЦИАЛОВ

Разглядим простой пример экономической задачки о перевозках.

Условие задачки. На 3-х Проверка задачи на разрешимость пасеках пчелосовхоза имеется 560 пчелосемей, при этом на первой пасеке - 200, 2-ой - 150 и третьей - 210 пчелосемей. Требуется отвезти пчелосемьи для опыления сельскохозяйственных культур на четыре точки: 1-ая точка вмещает 150 пчелосемей, 2-ая -190, 3-я - 100, 4-ая - 120 пчелосемей. Найти, от какой пасеки до какой точки и сколько пчелосемей нужно перевезти, чтоб общие издержки на их Проверка задачи на разрешимость, перевозки были наименьшими. Расстояния от пасек до точек известны (табл.1).

Таблица I - Расстояния от пасек до точек, км.

Пасеки Точки
I
II
III

Последовательность решения задачки

Проверка задачки на разрешимость

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

A1 + A Проверка задачи на разрешимость2+ A3 = B1 + B2 + B3+В4 (1)

(либо в сокращенной записи ( Ai = Bj).

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

В нашей задачке: ,

наличие пчелосемей на всех пасеках: Ai = 200 + 150 + 210 =560; потребность всех точек: Bj=150+190 + 100 + 120 = 560.

Таким макаром Ai = Bj =560, т.е: задачка закрытая Проверка задачи на разрешимость. Способом потенциалов решаются только закрытые задачки.

Приобретенное число (560) запишем в правую нижнюю угловую клеточку матрицы задачки (табл. 2).

Примечание 1. Если суммарные припасы поставщиков превосходят сум­марное потребности потребителей либо напротив, суммарные потребности потребителей больше суммарных припасов поставщиков, т.е.

Ai > Bj либо Ai < Bj

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

Ai - Bj,

либо дополнительная строчка, в какой припас груза равен разности:

Bj - Ai

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

Переход от открытой модели к закрытой значит приведение моде­ли транспортной задачки к канонической форме.


proverki-ubep-v-zheleznodorozhnoj-administracii-zamglavi-podozrevayut-v-vimogatelstve.html
proverochnaya-rabota-3-uchebno-metodicheskoe-posobie-prednaznacheno-dlya-pedagogov-aspirantov-studentov-zanimayushihsya.html
proverochnaya-rabota-po-povesti-a-s-pushkina-kapitanskaya-dochka-povestvovanie-v-povesti-vedetsya-ot-lica.html